#3185. 无限积木

无限积木

题目限制

1000 ms 256 M

题目描述

你有一堆积木,高度从 1188 不等,你可以从中选择一些出来,将它们叠放在一起,你希望最终的总高度不超过 HH 。问最高能够摆放多高?

输入格式

第一行包含一个整数 HH0H1e180\le H\le 1e18 )。 第二行共 88 个数字,分别表示高度从 1188 的积木数量 c[i]c[i]c[i]1e16c[i]\le 1e16

输出格式

输出能够摆放的最大高度。

数据范围

对于 44%44\% 的数据, 0H1000 \le H \le 100

对于 67%67\% 的数据, 0H200000 \le H \le 20000

对于 100%100\% 的数据, 0H1018,0c[i]10160 \le H \le 10^{18}, 0 \le c[i] \le 10^{16}

输入样例 1

10
1 2 3 4 5 6 7 8

输出样例 1

10