e-olymp
Competitions

Knapsack - Рюкзак

Рюкзак с массами

Дано n предметов массой m1, m2, ..., mn и стоимостью c1, c2, ..., cn соответственно.

Ими наполняют рюкзак, который выдерживает вес не более m. Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.

Входные данные

В первой строке задано натуральное число m, не превышающее 10000.

Во второй строке заданы n (n100) натуральных чисел mi, не превышающих 100.

В третьей строке заданы n натуральных чисел ci, не превышающие 100.

Выходные данные

Выведите номера предметов (числа от 1 до n), которые войдут в рюкзак наибольшей стоимости.

Time limit 1 second
Memory limit 128 MiB
Input example #1
6
2 4 1 2
7 2 5 1
Output example #1
1
3
4