求助站外题

G老师给你体积 $1 - 8$ 的一些物品，每种体积的物品有一定的数量。现在有一个容积为 $W$ 的超大背包，现在你要选一些物品装入背包，现在需要你求出最大的能得到的物品总体积。

输入的第一行包括一个整数。$W(0 \leq W \leq 10^{18})$ 输入的第二行，包括 8 个整数 $cnt_i(0 \leq cnt_i \leq 10^{16})$，表示体积为的物品的数量。

输出一个整数，表示最大可以得到的体积和。