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 i_{j} 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 i_{j}’s.
You can assume 1 ≤ g ≤ n ≤ 3000,
and that all the i_{j}’s are even natural numbers between 2 and 10^{5}.

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++