P3983 Sais Stone (Post-contest Enhanced Version)

```cpp 白露横江，水光接天，纵一苇之所如，凌万顷之茫然。——苏轼 ``` Zhencheng Ocean recently needs to purchase a large number of Sais stones. You may ask: what is a Sais stone? First, let’s learn about “Sais” (赛斯). It is a unit of weight, and we use $ si $ as its unit symbol. For example, $ 1 $ Sais is $ 1 $ si. A Sais stone has the following property: originally, it exists as separate pieces of $ 1 $ si each. After being refined with a “Natural Gun,” it will merge with other refined Sais stones. Once merged to a suitable weight, it is “passivated” so it will no longer merge with other Sais stones. If merged incorrectly, it can be cut apart with a “Diamond Knife” (interestingly, you can only cut it into integer Sais weights). A Sais stone’s weight must be an integer number of Sais, and the price differs for different integer weights of Sais stones.

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**.

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 a single line containing one integer, the maximum total profit.

- 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