您有一组项目,每个项目的权重不大于 $$$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$$$ 的项目数。
输出
打印一个整数——一组好的物品子集的最大可能重量。
示例
输入 #1
10 1 2 3 4 5 6 7 8
输出 #1
10
输入 #2
0 0 0 0 0 0 0 0 0
输出 #2
0
输入 #3
3 0 4 1 0 0 9 8 3
输出 #3
3