Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Рюкзак
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть набор предметов, у каждого из которых есть какой-то целочисленный вес не более $$$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