До Нового Року залишилось \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}.