题目描述

Yoimiya 和云浅在放烟花。在第 $0$ 秒时，烟花位于坐标 $(0,0)$ 处。一个烟花可能走到的位置和它的材料有关。

具体地，烟花的材料可以用一个 $01$ 序列 $s$ 表示，烟花将会在空中燃烧 $|s|$ 秒。对每个 $i=1,2,\cdots,|s|$，设烟花现在的位置为 $(x,y)$：

• 若 $s_i=0$，则烟花在下一秒可能会飞到 $(x,y),(x+1,y),(x+1,y+1)$ 中的一个点。
• 若 $s_i=1$，则烟花在下一秒可能会飞到 $(x,y),(x-1,y),(x-1,y-1)$ 中的一个点。

定义 $f(s)$ 为材料为 $s$ 的烟花最终可能会飞到的点的数目。

Yoimiya 现在有一个长为 $n$ 的 $01$ 序列 $a$，她想用这个序列制造恰好 $k$ 个烟花。具体地，她需要把这个序列划分为互不相交的 $k$ 个区间，且每个 $a_i$ 都至少会被划分到一个区间内；由于燃放烟花会带来污染，这个划分方案的污染度就定义为每一段的 $f$ 值之和。你需要帮她找到污染度最小的划分方案。

形式化地，你需要找到 $k$ 个区间 $[l_1,r_1],\cdots,[l_k,r_k]$ 满足：

• $l_1=1,r_k= n$
• $\forall 1\le i\le k,l_i\le r_i$
• $\forall 1\le i\le k-1,r_i+1=l_{i+1}$

要求最小化 $\sum_{i=1}^kf(a[l_i\cdots r_i])$，其中 $a[p\cdots q]$ 表示序列 $(a_p,a_{p+1},\cdots,a_q)$。

输入格式

第一行两个正整数 $n,k$。

接下来一行 $n$ 个数 $a_1,\cdots,a_n$ 表示序列 $a$，保证 $a_i\in\{0,1\}$。

输出格式

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

样例 $1$ 输入

6 3
0 0 1 0 1 1

样例 $1$ 输出

19

样例 $1$ 解释

最优方案是将 $a$ 划分为 $a_1=(0,0),a_2=(1,0),a_3=(1,1)$，可以验证：

• $f(a_1)=f(a_3)=6$
• $f(a_2)=7$

其中以 $a_2$ 为材料的烟花能够到达的点是：

• $(-1,-1),(-1,0),(0,-1),(0,0),(0,1),(1,0),(1,1)$

以 $a_1$ 为材料的烟花能够到达的点是：$(0,0),(1,0),(1,1),(2,0),(2,1),(2,2)$。

测试点约束

对于 $100\%$ 的数据，$1\le k\le n\le 2\times 10^5,a_i\in\{0,1\}$。各子任务的约束如下表所示：