У вас есть набор предметов, у каждого из которых есть какой-то целочисленный вес не более \(8\). Вы называете подмножество набора предметов хорошим, если суммарный вес предметов в подмножестве не превосходит \(W\).
Посчитайте максимально возможный вес хорошего подмножества набора предметов. Обратите внимание, что пустое множество и исходный набор предметов тоже являются подмножествами исходного набора.
В первой строке записано одно целое число \(W\) (\(0 \le W \le 10^{18}\)) — максимально возможный вес хорошего подмножества.
Вторая строка описывает набор предметов, который у вас есть. Она содержит \(8\) целых чисел \(cnt_1\), \(cnt_2\), ..., \(cnt_8\) (\(0 \le cnt_i \le 10^{16}\)), где \(cnt_i\) — количество предметов веса \(i\) в наборе.
Выведите одно целое число — максимальный вес хорошего подмножества.
10 1 2 3 4 5 6 7 8
10
0 0 0 0 0 0 0 0 0
0
3 0 4 1 0 0 9 8 3
3
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач