题目描述

你有一堆积木，高度从 $1$ 到 $8$ 不等，你可以从中选择一些出来，将它们叠放在一起，你希望最终的总高度不超过 $H$ 。问最高能够摆放多高？

输入格式

第一行包含一个整数 $H$ （ $0\le H\le 1e18$ ）。 第二行共 $8$ 个数字，分别表示高度从 $1$ 到 $8$ 的积木数量 $c[i]$ ， $c[i]\le 1e16$ 。

输出格式

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

数据范围

对于 $44\%$ 的数据， $0 \le H \le 100$ ；

对于 $67\%$ 的数据， $0 \le H \le 20000$ ；

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

输入样例 1

10
1 2 3 4 5 6 7 8

输出样例 1

10