e-olymp
Məsələlər

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

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

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

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

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

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

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

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

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
6
2 4 1 2
7 2 5 1
Çıxış verilənləri #1
1
3
4