У вас есть набор предметов, у каждого из которых есть какой-то целочисленный вес не более \(8\). Вы называете подмножество набора предметов хорошим, если суммарный вес предметов в подмножестве не превосходит \(W\).
Посчитайте максимально возможный вес хорошего подмножества набора предметов. Обратите внимание, что пустое множество и исходный набор предметов тоже являются подмножествами исходного набора.
Выходные данные
Выведите одно целое число — максимальный вес хорошего подмножества.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
1 2 3 4 5 6 7 8
|
10
|
|
2
|
0
0 0 0 0 0 0 0 0
|
0
|
|
3
|
3
0 4 1 0 0 9 8 3
|
3
|