Почтовые марки
Вы - филателист, и в настоящий момент изучаете серию из 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.