eolymp
bolt
Try our new interface for solving problems
Məsələlər

Почтовые марки

Почтовые марки

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Вы - филателист, и в настоящий момент изучаете серию из n почтовых марок. Каждая из марок этой серии уникальна; какие-то из них уже принадлежат вам, а какие-то вы можете приобрести. Для каждой марки известны её стоимость (сколько долларов вы отдадите за покупку этой марки, или же за сколько долларов вы сможете её продать) и коллекционная ценность (эта величина зависит от ваших субъективных критериев и не имеет отношения к стоимости марки в долларах). Вы можете продавать любые марки этой серии, которые у вас есть, и покупать марки, которых нет.

Ваша цель на данном этапе - собрать коллекцию почтовых марок этой серии, суммарная коллекционная ценность которой будет не меньше k. Какое минимальное количество долларов придётся потратить, чтобы этой цели достичь?

Giriş verilənləri

В первой строке входного файла заданы через пробел два целых числа n и k (1n32, 1k10^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 - коллекционная ценность почтовых марок.

Çıxış verilənləri

В первой строке выходного файла выведите одно число - минимальное количество долларов, которое необходимо потратить, чтобы получить коллекцию марок с суммарной коллекционной ценностью не меньше k. Если можно добиться такой коллекционной ценности, не тратя дополнительных средств или даже заработав на операциях с марками, выведите 0. Если же такой коллекционной ценности добиться невозможно при любых дополнительных вложениях, выведите -1.

Nümunə

Giriş verilənləri #1
2 13
2 15
0 0
2 21
Çıxış verilənləri #1
15
Giriş verilənləri #2
5 67
9 18 7 6 18
1 0 0 0 1
12 27 10 10 25
Çıxış verilənləri #2
22
Giriş verilənləri #3
4 10
14 14 12 6
0 1 1 1
19 23 20 7
Çıxış verilənləri #3
0
Giriş verilənləri #4
10 811
43 33 14 31 42 37 17 42 40 20
0 0 0 0 0 0 1 0 0 0
116 71 38 77 87 106 48 107 91 41
Çıxış verilənləri #4
-1
Müəllif A.Grinenko, I.Kazmenko
Mənbə CollectingPostmarks, TopCoder SRM 415 Round 1 Div1 500