Задачи
Рюкзак с массами
Рюкзак с массами
Дано $n$ предметов с массой $m_1, m_2, ..., m_n$ и стоимостью $c_1, c_2, ..., c_n$ соответственно.
Ими наполняют рюкзак, который выдерживает вес не более $s$. Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.
\InputFile
Первая строка содержит натуральное число $s\:(s \le 10^4)$ --- вес рюкзака.
Вторая строка содержит $n\:(n \le 100)$ натуральных чисел $m_i\:(m_i \le 100)$ --- веса предметов.
Третья строка содержит $n$ натуральных чисел $c_i\:(c_i \le 100)$ --- стоимости предметов.
\OutputFile
Выведите номера предметов (числа от $1$ до $n$), которые войдут в рюкзак наибольшей стоимости.
Входные данные #1
6 2 4 1 2 7 2 5 1
Выходные данные #1
1 3 4