Maximizing Banquet Satisfaction

Prof. Pang invited \( n \) professors to his banquet. The professors are seated at a round table; for every \( i \) from \( 1 \) to \( n \), professor \( i \) sits adjacent to professor \( (i \bmod n) + 1 \) and professor \( ((i+n-2) \bmod n) + 1 \).

There are \( n \) dishes prepared and exactly one dish is placed at each of the \( n \) positions on the table. Position \( i \) is in front of professor \( i \). Professor \( i \) can access the dishes placed at positions \( i \), \( (i \bmod n)+1 \), and \( ((i+n-2) \bmod n)+1 \).

Among the dishes, exactly \( a \) are spicy while the remaining \( n-a \) are not spicy. Some professors, possibly none, are unable to have spicy food. If a professor can have spicy food, his/her satisfaction level is 3 (since he/she can taste all the dishes available). If a professor cannot have spicy food, his/her satisfaction level is equal to the number of non-spicy dishes among the three accessible positions.

Prof. Pang knows for each professor whether they can have spicy food or not. Help him arrange the dishes on the table so that the sum of the professors' satisfaction levels is maximized. Output this maximum sum.

Note: All formulas are in \( \LaTeX \) format.

inputFormat

The first line contains two integers \( n \) and \( a \) (where \( 0 \le a \le n \)), denoting the number of professors (and dishes) and the number of spicy dishes respectively.

The second line contains \( n \) space-separated integers. Each integer is either 1 or 0. If the \( i^{th} \) integer is 1, it means professor \( i \) can have spicy food; if it is 0, it means professor \( i \) cannot have spicy food.

outputFormat

Output a single integer: the maximum possible sum of all professors' satisfaction levels.

sample

3 1
1 0 1

8