Five for week 16 (2013-2014)
И вода прокормить может!
До Нового Года осталось N дней. Все начинают готовится к празднику. Исключением не стала близлежащая местная школа, в которой преподаёт Маргарита Изольдовна. Под этот Новый Год она решила подготовить много конкурсов и украсить зал. Так как конкурсы сильно изматывали участников, то, следовательно, им необходимо было утолить жажду. Было решено закупить K литров воды. Поскольку зал еще не готов и времени осталось мало, то она попросила помощи у своего лучшего ученика. Он должен был купить необходимое количество сладкой воды на выделеные деньги. Как вы догадались речь шла об Изе. Маргарите Изольдовне неважно, вернет ли Изя сдачу, или нет, и в чём принесёт воду, главное - чтобы её было достаточно.
С приближением праздников, владельцы магазинов начали творить неведомые вещи, а именно: менять цены каждый день. Поэтому иногда было выгодно в один день купить бутылку с водой, а на другой день продать по полной стоимости. Изя сразу догадался, что на этом можно немного подзаработать.
Ваша задача состоит в том, чтобы узнать сколько денег может заработать Изя, если известно, что каждый день можно выполнять не более одного из таких действий:
купить одну бутылку с водой;
перепродать бутылку с водой;
сдать бутылку, воду оставив себе.
Input data
В первой строке вводится три числа N, M, K, где N — количество дней до праздника, M — деньги, которые дала учительница (М ≤ 100000000), K (K ≤ 250) — количество воды, которые нужно купить Изе.
Во второй строке задано N натуральных чисел wi ≤ 10000 (стоимость бутылки воды на i-ый день).
В третьей строке задано N натуральных чисел ci ≤ 10000 (стоимость пустой бутылки на i-ый день).
Output data
В выходной файл выведите максимальную сумму денег, которую может заработать Изя. Если задание учительницы выполнить невозможно, то вывести -1.
Examples
3 10 1 5 2 6 2 1 1
9