题目描述

庞教授邀请了 $n$ 名教授吃饭。所有教授围坐在一张圆桌旁，顺时针依次编号为 $1,2,\dots,n$。桌上共有 $n$ 盘菜，也按照顺时针顺序编号为 $1,2,\dots,n$。坐在第 $i$ 个座位的教授可以吃到第 $(i \bmod n) + 1$、第 $i$、以及第 $((i+n-2) \bmod n) + 1$ 盘菜（即他面前的菜以及左右相邻的两盘菜）。

庞教授准备了 $a$ 盘辣菜和 $n-a$ 盘不辣的菜，他可以自由决定每盘菜是辣还是不辣。每位教授有自己的喜好：$1$ 表示能吃辣，$0$ 表示不能吃辣。一位教授的满意度定义为他能吃到的、符合自己口味的菜的数量（能吃辣的教授吃到辣菜会满意，不能吃辣的教授吃到不辣的菜会满意）。

请你帮庞教授合理安排每盘菜的辣度，使得所有教授的满意度之和最大，并输出这个最大值。

输入格式

第一行包含两个整数 $n$ 和 $a$，分别表示教授的人数（也是菜的数量）和辣菜的数量。

第二行包含 $n$ 个整数，每个整数为 $0$ 或 $1$，表示对应编号教授的喜好（$1$ 能吃辣，$0$ 不能吃辣）。

输出格式

输出一行一个整数，表示最大的满意度总和。

样例

5 2
1 0 1 0 1

13

数据范围与提示

• $3 \le n \le 10^5$
• $1 \le a \le n$

来源

CSPJ-重点算法班