Description

庞教授邀请了 $n$ 位教授参加他的宴会。教授们坐在一个圆桌周围。对于所有 $i$，从 $1$ 到 $n$，教授 $i$ 坐在教授 $(i \bmod n) + 1$ 和 $((i + n - 2)\bmod n) + 1$ 旁边。

庞教授准备了 $n$ 道菜。桌子上有 $n$ 个位置。位置 $i$ 在教授 $i$ 的前面。教授 $i$ 只能接触到放在位置 $i$、$(i \bmod n) + 1$ 和 $((i + n - 2)\bmod n) + 1$ 处的菜。庞教授将在每个位置上放置一道菜。

在这些菜中，有 $a$ 道是辣的，$n-a$ 道是不辣的。有些（可能为 $0$）教授不能吃辣的食物。如果一位教授可以吃辣的食物，他/她的满意度水平是他/她可以接触到的菜的数量（无论是辣的还是不辣的）。如果一位教授不能吃辣的食物，他/她的满意度水平是他/她可以接触到的不辣的菜的数量。

庞教授知道每位教授是否可以吃辣的食物。请帮助他安排桌子上的菜，使得所有教授的满意度水平之和最大化。输出最大的总和。

Input Format

第一行包含两个整数 $n, a$ ($3\le n\le 10^5, 0\le a\le n$)。

第二行包含 $n$ 个整数 $b_1, \ldots, b_n$。$b_i$ 是 $0$ 或 $1$。$b_i=1$ 表示教授 $i$ 可以吃辣的食物。$b_i=0$ 表示教授 $i$ 不能吃辣的食物。

Output Format

输出一行一个整数，表示答案。

翻译来自于：ChatGPT

5 2
1 0 1 0 1

13