Дано N
предметов массой m1, …, mN
и стоимостью c1, …, cN
соответственно.
Ими наполняют рюкзак, который выдерживает вес не более M
. Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.
Входные данные:
- в первой строке вводится натуральное число N
, не превышающее 100 и натуральное число M
, не превышающее 10000;
- во второй строке вводятся N
натуральных чисел mi
, не превышающих 100;
- в третьей строке вводятся N
натуральных чисел сi
, не превышающих 100.
Выходные данные: выведите номера предметов (числа от 1 до N), которые войдут в рюкзак наибольшей стоимости (по одному номеру в строке).
Примеры
№ |
Входные данные |
Выходные данные |
1 |
4 6
2 4 1 2
7 2 5 1
|
1
3
4 |