Дима, Инна и Сережа собрались в комнате. Правильно, кое-кто лишний. Чтобы поднять Сереже настроение и вдохновить его на прогулку, Инна решила что-нибудь приготовить.
В холодильнике Димы и Сережи есть n фруктов. Каждый фрукт имеет две характеристики: вкусность и калорийность. Инна решила приготовить свежий фруктовый салат, поэтому она хочет выбрать несколько фруктов из холодильника для салата. Инна руководствуется следующим принципом при выборе фруктов: отношение суммарной вкусности выбранных фруктов к суммарной калорийности должно быть равно k. Другими словами 
, где aj — вкус j-го выбранного фрукта, а bj — его калорийность.
Инна еще не выбрала фрукты, она задумалась: чему равна максимальная суммарная вкусность выбранных фруктов, если она строго будет придерживаться своего принципа? Помогите Инне решить эту кулинарную задачу, ведь на кону семейное счастье!
Инна очень любит Диму, поэтому хочет сделать салат минимум из одного фрукта.
Выходные данные
Если Инна никак не сможет выбрать фрукты для салата, в единственной строке выведите -1. Иначе выведите единственное целое число — максимально возможную сумму вкусностей выбранных фруктов.
Примечание
В первом тестовом примере можно получить суммарную вкусность фруктов 18, выбрав фрукт номер 1 и фрукт номер 2, тогда суммарная калорийность будет равна 9. Выполняется 
, что и требует Инна.
Во втором тестовом примере невозможно так выбрать фрукты, чтобы требование Инны выполнилось.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
10 8 1
2 7 1
|
18
|
|
2
|
5 3
4 4 4 4 4
2 2 2 2 2
|
-1
|