← 返回题目列表

Codeforces · 1132/E

E. 背包

中文机器翻译题面 查看原题

您有一组项目,每个项目的权重不大于 $$$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