Description

In City A, there is a huge circular plaza. To green the environment and purify the air, the municipal government decided to plant a ring of trees along the outer edge of the circular plaza.

After receiving the order, the parks department initially planned $n$ planting positions, numbered clockwise from $1$ to $n$. Each position has an aesthetic value $A_i$, and if a tree is planted there, you gain this $A_i$ value. However, due to poor soil fertility in City A, two trees must not be planted at adjacent positions (positions $i$ and $i+1$ are adjacent; note that positions $1$ and $n$ are also adjacent).

Finally, the municipal government provided the parks department with $m$ saplings and requires that all of them be planted. Please design a planting plan to maximize the total aesthetic value. If it is impossible to plant all $m$ saplings, output that there is no solution.

Input Format

The first line contains two positive integers $n, m$.

The second line contains $n$ integers, where the $i$-th integer represents $A_i$.

Output Format

Output one integer, the maximum total aesthetic value achievable by the optimal planting plan. If there is no solution, output Error!.

7 3
1 2 3 4 5 6 7

15

7 4
1 2 3 4 5 6 7

Error!

Hint

For all testdata: $m \le n$, $-1000 \le A_i \le 1000$.

Translated by ChatGPT 5