Поштові марки
Ви - філателіст, і в даний момент вивчаєте серію з n поштових марок. Кожна з марок цієї серії унікальна; якісь з них вже належать вам, а якісь ви можете придбати. Для кожної марки відомі її вартість (скільки доларів ви віддасте за придбання цієї марки, або ж за скільки доларів ви зможете її продати) та колекційна цінність (ця величина залежить від ваших суб'єктивних критеріїв і не має відношення до вартості марки в доларах). Ви можете продавати довільні марки цієї серії, які у вас є, і купувати марки, яких немає.
Ваша мета на даному етапі - зіобрати колекцію поштових марок цієї серії, сумарна колекційна ціність якої буде не менше k. Яку мінімальну кількість доларів прийдеться потратити, щоб цієї мети досягти?
Вхідні дані
У першому рядку вхідного файлу задано через пропуск два цілих числа n та k (1 ≤ n ≤ 32, 1 ≤ k ≤ 10^9). У другому рядку задані через пропуск n цілих чисел p_1, p_2, ..., p_n - вартість поштових марок. У третьому рядку задано через пропуск n цілых чисел h_1, h_2, ..., h_n; h_i дорівнює единице, якщо i-та марка вже знаходиться у вас, і нулю у протилежному випадку. Нарешті, у четвертому рядку задані через пропуск n цілих чисел v_1, v_2, ..., v_n - колекційна цінність поштових марок.
Вихідні дані
У першому рядку вихідного файлу виведіть одне число - мінімальну кількість доларів, які необхідно витратити, щоб отримати колекцію марок з сумарною колекційною цінністю не менше k. Якщо можна добитись такої колекційної цінності, не витрачаючи додаткових коштів, або навіть заробивши на операціях з марками, виведіть 0. Якщо ж такої колекційної цінності досягти неможливо при довільних додаткових вкладах, виведіть -1.