Cherimoyor

Time limit1sMemory limit512 MB

Summary

Each day C_i cherimoyas become edible and stay edible for 3 days; eating the k-th fruit in a day gives 11-k points (max 10 per day). Maximize total enjoyment.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

Farah loves the exotic fruit cherimoya. Since it comes from a faraway country, it is sold in Sweden only one day a year! Farah naturally bought several cherimoyas on that day.

The cherimoyas are ripe to different degrees. Some have just become ripe that same day, while others become edible later.

More precisely, each cherimoya fruit is edible for a total of 3 days. We say the fruit becomes edible on that day. Before that you cannot eat it, and after the three days it must be thrown away.

Farah wants to get as much as possible out of the cherimoya season. She wants to maximize her enjoyment, which is calculated as follows: on a given day she gets 10 enjoyment points for the first cherimoya, then 9 for the second, 8 for the third, and so on. She can never eat more than 10 cherimoyas in a day.

Write a program that, given how many cherimoyas become edible each day, determines the most enjoyment points Farah can get during this year's cherimoya season.

Input

You first receive an integer $N$ , followed by $N$ integers $C\_i$ . So there are a total of $N+2$ days on which eating cherimoyas is relevant. No individual integer is greater than 30.

Output

Print one line with a single integer. This integer is the maximum enjoyment points Farah can get with the best eating strategy.

Constraints

For test cases worth up to $60$ points, $N$ is at most 5. For full points, your program must handle $N$ at most 15.

Examples3

Example 1
Input
```
3
18 0 2
```
Expected output
```
155
```
Example 2
Input
```
8
3 0 1 2 0 0 3 6
```
Expected output
```
144
```
Example 3
Input
```
2
30 30
```
Expected output
```
220
```