| Codeforces Round 214 (Div. 2) |
|---|
| Закончено |
Дима, Инна и Сережа собрались в комнате. Правильно, кое-кто лишний. Чтобы поднять Сереже настроение и вдохновить его на прогулку, Инна решила что-нибудь приготовить.
В холодильнике Димы и Сережи есть n фруктов. Каждый фрукт имеет две характеристики: вкусность и калорийность. Инна решила приготовить свежий фруктовый салат, поэтому она хочет выбрать несколько фруктов из холодильника для салата. Инна руководствуется следующим принципом при выборе фруктов: отношение суммарной вкусности выбранных фруктов к суммарной калорийности должно быть равно k. Другими словами 
, где aj — вкус j-го выбранного фрукта, а bj — его калорийность.
Инна еще не выбрала фрукты, она задумалась: чему равна максимальная суммарная вкусность выбранных фруктов, если она строго будет придерживаться своего принципа? Помогите Инне решить эту кулинарную задачу, ведь на кону семейное счастье!
Инна очень любит Диму, поэтому хочет сделать салат минимум из одного фрукта.
Первая строка входных данных содержит два целых числа n, k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10). Вторая строка входных данных содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 100) — вкусности фруктов. Третья строка входных данных содержит n целых чисел b1, b2, ..., bn (1 ≤ bi ≤ 100) — калорийности фруктов. Фрукт номер i имеет вкусность ai и калорийность bi.
Если Инна никак не сможет выбрать фрукты для салата, в единственной строке выведите -1. Иначе выведите единственное целое число — максимально возможную сумму вкусностей выбранных фруктов.
3 2
10 8 1
2 7 1
18
5 3
4 4 4 4 4
2 2 2 2 2
-1
В первом тестовом примере можно получить суммарную вкусность фруктов 18, выбрав фрукт номер 1 и фрукт номер 2, тогда суммарная калорийность будет равна 9. Выполняется 
, что и требует Инна.
Во втором тестовом примере невозможно так выбрать фрукты, чтобы требование Инны выполнилось.
