Дано
N предметов массой
m1, …, mN и стоимостью
c1, …, cN соответственно.
Ими наполняют рюкзак, который выдерживает вес не более
M. Какую наибольшую стоимость могут иметь предметы в рюкзаке?
Входные данные
В первой строке вводится натуральное число
N, не превышающее 100 и натуральное число
M, не превышающее 10000. Во второй строке вводятся
N натуральных чисел
mi, не превышающих 100. Во третьей строке вводятся
N натуральных чисел
сi, не превышающих 100.
Выходные данные
Выведите наибольшую стоимость рюкзака.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 597
18
16
|
16
|
|
2
|
2 27
30 35
3 9
|
0
|