До Нового Года осталось \textbf{N} дней. Все начинают готовится к празднику. Исключением не стала близлежащая местная школа, в которой преподаёт Маргарита Изольдовна. Под этот Новый Год она решила подготовить много конкурсов и украсить зал. Так как конкурсы сильно изматывали участников, то, следовательно, им необходимо было утолить жажду. Было решено закупить \textbf{K} литров воды. Поскольку зал еще не готов и времени осталось мало, то она попросила помощи у своего лучшего ученика. Он должен был купить необходимое количество сладкой воды на выделеные деньги. Как вы догадались речь шла об Изе. Маргарите Изольдовне неважно, вернет ли Изя сдачу, или нет, и в чём принесёт воду, главное - чтобы её было достаточно. С приближением праздников, владельцы магазинов начали творить неведомые вещи, а именно: менять цены каждый день. Поэтому иногда было выгодно в один день купить бутылку с водой, а на другой день продать по полной стоимости. Изя сразу догадался, что на этом можно немного подзаработать. Ваша задача состоит в том, чтобы узнать сколько денег может заработать Изя, если известно, что каждый день можно выполнять не более одного из таких действий: \begin{itemize} \item купить одну бутылку с водой; \item перепродать бутылку с водой; \item сдать бутылку, воду оставив себе. \end{itemize} \InputFile В первой строке вводится три числа \textbf{N}, \textbf{M}, \textbf{K}, где \textbf{N} --- количество дней до праздника, \textbf{M} --- деньги, которые дала учительница (\textbf{М} ≤ \textbf{100000000}), \textbf{K} (\textbf{K} ≤ \textbf{250}) --- количество воды, которые нужно купить Изе. Во второй строке задано \textbf{N} натуральных чисел \textbf{w_i} ≤ \textbf{10000} (стоимость бутылки воды на \textbf{i}-ый день). В третьей строке задано \textbf{N} натуральных чисел \textbf{c_i} ≤ \textbf{10000} (стоимость пустой бутылки на \textbf{i}-ый день). \OutputFile В выходной файл выведите максимальную сумму денег, которую может заработать Изя. Если задание учительницы выполнить невозможно, то вывести \textbf{-1}.