Description

We now need to bring to market Sais stones with a total weight of $Need$ si. The seller wants to compute the maximum revenue obtainable by merging the $1$ si units in some way. However, there is a complication: the market is near the Zhencheng Grand Hall (the center of Zhencheng Ocean), and the seller needs to rent boats to deliver the Sais stones there (we do not count the cost for the seller himself to travel). There are ten types of boats available for rent, with carrying capacities from $1$ si to $10$ si, and each boat type has a different rental price, as shown in the table below.

Due to the strong Sais force near the Zhencheng Grand Hall, it is impossible to perform any operation on the Sais stones there. After the seller transports the Sais stones over, they can only be sold as pre-merged pieces. Assume the seller does not return and that all these Sais stones can be sold. Now the seller wants to calculate the total profit (let total profit = total revenue from Sais stones − total boat rental cost). Please design a program to find an optimal plan to obtain the maximum total profit.

Input Format

The input consists of two lines.

• The first line contains a single number $Need$ (the total amount of Sais stones, unit: si).
• The second line contains ten numbers $a_{1}\ ...\ a_{10}$ (the market prices, in yuan, for Sais stones of weights $1$ si to $10$ si, respectively).

Output Format

Output a single line containing one integer, the maximum total profit.

11
1 6 11 17 23 27 33 35 38 43

32

7
1 5 14 18 20 28 31 34 39 42

21

Hint

• Sample explanation:

  Merge $11$ units of $1$ si Sais stones into one $4$ si stone and one $7$ si stone, and rent two boats with capacities $4$ si and $7$ si. This is optimal, so the maximum total profit is $32$ yuan.

• Notes:

  For all input numbers, they are integers in the interval $(0, 100000)$.

  It is guaranteed that the maximum total profit is positive.

  In the same line, there is one space between any two numbers.

  The post-contest enhanced version was completed on $2020$-$10$-$13 at$ 19 $:$ 18 $.

Translated by ChatGPT 5