P17883 「IXOI R4」BOOF

在 2085 年，人类找到了外星人。 而他们发现外星人也玩音游，于是他们创办了 BOOF（THE BMS OF OTTO FIGHTERS）。 然后你现在作为一个参赛者，你要为一首歌写谱。 外星人们都不想打纵连和叠键呢。

一首歌有 $n$ 个音符，每个音符占一拍。谱面一共有 $k$ 条轨道，每一拍你都可以在任意轨道上放置按键。根据音符的力度，第 $i$ 个音符需要在第 $i$ 拍同时落下 $a_i$ 个键。 玩家不希望出现「纵连」——也就是同一轨道上连续三拍都落键。而连续两拍在同一轨道上落键则称为「叠键」。 为了避开纵连，你可以让最多 $m$ 个音符的实际落键数与要求的 $a_i$ 不一致。在此基础上，你希望尽可能减少叠键的出现：具体来说，你要让相邻两拍之间叠键数量的最大值尽可能小。 请求出这个最小值；如果不存在合法的方案，输出 $-1$。 ## 形式化题意 给定整数 $n,k$ 以及序列 $a_1,\dots,a_n$。你需要构造一个 $n$ 行 $k$ 列的 01 矩阵 $A$，满足： 1. 不存在 $1\le i\le n-2$，$1\le j\le k$ 使得 $A_{i,j}=A_{i+1,j}=A_{i+2,j}=1$（禁止纵连）。 2. 第 $i$ 行中 $1$ 的个数应为 $a_i$，但你最多可以违反这 $n$ 个行约束中的 $m$ 个。 在满足上述条件的前提下，最小化 $$ \max_{1\le i

第一行三个数 $n$，$k$ 和 $m$。 接下来一行 $n$ 个数，第 $i$ 个数表示 $a_i$。

输出一个数，表示答案。

**本题采用捆绑测试。** |Subtask 编号|分数|$n \le$|$k \le$|特殊性质| |:-:|:-:|:-:|:-:|:-:| |$0$|$10$|$10$|$5$|无| |$1$|$20$|$25$|$10^9$|无| |$2$|$5$|$10^6$|$2$|无| |$3$|$20$|$10^6$|$10^9$|$m \le 200$| |$4$|$45$|$10^6$|$10^9$|无| 对于 $100\%$ 的数据，$2\le n\le 10^6$，$1\le m \le n$，$1\le k\le 10^9$，$1\le a_i\le k$。