Firefighters and grannies (1) P18110

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 \le g \le n \le 20$, 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 reasonable backtracking.