Firefighters and grannies (2) P65894

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

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