Задача №3143. Перевес багажа
Впервые в жизни Петя летит на международную олимпиаду по программированию. Петя так волновался, что взял с собой множество вещей и теперь во время регистрации на рейс его чемодан не принимают, так как у него превышение разрешенной массы багажа.
У Пети в чемодане лежат N предметов, каждый предмет имеет свой вес Wi килограмм и ценность Ai рублей, причем оказалось так, что для любого предмета выполняется следующее неравенство:
W1 + W2 + … + Wi-1 ≤ Wi
Пете сообщили, что у него перевес чемодана в M килограмм, поэтому ему придется оставить в аэропорту какие-то предметы с суммарной массой не меньше M. При этом Петя хочет понести минимальный урон, а поэтому оставленные предметы должны иметь наименьшую возможную стоимость.
Требуется написать программу, которая подсчитает минимальную возможную стоимость оставленных предметов.
В первой строке задаётся количество предметов в багаже у Пети N (1 ≤ N ≤ 50) и какой у Пети перевес чемодана в килограммах M (1 ≤ M ≤ 1018). Во второй строке задаются N целых неотрицательных чисел – вес всех вещей Wi, сумма чисел не превышает 1018. В третьей строке заданы N целых неотрицательных чисел – ценность всех вещей Ai , все числа не превышают 109.
В выходной файл требуется вывести минимальную суммарную стоимость предметов, которые Петя будет вынужден оставить в аэропорту.
Ввод | Вывод |
|
|
|
|