A94845.赛斯石

题目背景

“白露横江，水光接天，纵一苇之所如，凌万顷之茫然。” —— 苏轼

真程海洋近来需要进购大批赛斯石。首先我们来了解一下赛斯，赛斯是一个重量单位，我们用 $si$ 作为其单位（例如 $1$ 赛斯就是 $1si$）。

赛斯石具有特殊的性质：它原本以 $1si$ 的单体存在，但经过自然枪精化后，可以与其他精化过的赛斯石合并。合并到合适的重量后，将其钝化即可定型。如果合并不当，也可以用金刚刀将其切开（只能切成整数赛斯重量）。不同重量的赛斯石在市场上的价格是不同的。

题目描述

现需上市 $N$ 赛斯重量的赛斯石，卖家希望计算出通过某种合并和运输方案能获得的最大总盈利。

市场位于真程海洋中心（真程大殿附近），卖家需要租船将赛斯石运送过去。目前有 $10$ 种船可供租赁，载重量从 $1si$ 到 $10si$ 不等，每种船的租金如下表所示：

载重 ($si$)	1	2	3	4	5	6	7	8	9	10
租金 (元)	1	3	5	7	9	10	11	14	15	17

由于真程大殿附近存在强烈的赛斯力场，赛斯石运抵后无法进行任何合并或切割操作，只能按照运送前的状态出售。

假设卖家不考虑返程费用，且所有运送的赛斯石均能售出。
总盈利 = 赛斯石的总收益 - 租船所需总费用。
请你设计一个程序，计算最大总盈利。

输入共两行。

第一行包含一个整数 $N$，表示需要上市的赛斯石总量（单位：$si$）。

第二行包含 $10$ 个整数 $a_1, a_2, \dots, a_{10}$，分别表示重量为 $1si$ 到 $10si$ 的赛斯石在市场上的单价（单位：元）。

输出仅一行，包含一个整数，表示最大总盈利。

样例一说明

将 $11si$ 的赛斯石分为一个 $4si$ 和一个 $7si$ 的石头。

• $4si$ 石头售价 $17$ 元，船费 $7$ 元，盈利 $10$ 元。
• $7si$ 石头售价 $33$ 元，船费 $11$ 元，盈利 $22$ 元。
• 总盈利：$10 + 22 = 32$ 元。

数据范围与约定

• 对于所有输入数据，$0 < N \le 100,000$。
• 输入的市场价格均为整数，且都在区间 $(0, 100000)$ 中。
• 保证卖家最大总盈利为正数。