Firefighters and grannies (1) P18110


Statement
 

pdf   zip

thehtml

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 ≤ 20, 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 reasonable backtracking.

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