# Firefighters and grannies (2) P65894

Statement

html

The firefighters of a distant country want to protect the grannies inside n schools. All the schools are in a row on a street, numbered in order from 1 to n. At each school j there are ij grannies. The firefighters can form g groups, and each group can only go to a single school. If a group goes to school j, it protects all the grannies there. In addition, it also indirectly protects half the grannies in school j−1, assuming that it exists and that it is not already fully protected by another group; and similarly with school j+1.

What is the maximum number of grannies that can be protected?

Input

Input consists of several cases, each one with g and n, followed by the ij’s. You can assume 1 ≤ gn ≤ 3000, and that all the ij’s are even natural numbers between 2 and 105.

Output

For every case, print how many grannies can be protected.

Hint

The expected solution for this problem is a dynamic programming code with two mutual recurrences and cost O(g · n).

Public test cases
• Input

```1 1  100000
1 2  10 20
1 3  10 80 20
1 3  10 20 80
3 3  10 20 80
3 9  4 8 2 4 8 8 6 2 8
9 9  2 2 2 2 2 2 2 2 2
```

Output

```100000
25
95
90
110
36
18
```
• Information
Author
Salvador Roura
Language
English
Translator
Salvador Roura
Original language
Catalan
Other languages
Catalan
Official solutions
C++
User solutions
C++