Inferno

> 我是幽灵。 > 穿过悲惨之城，我落荒而逃。 > 穿过永世凄苦，我远走高飞。 沿着阿尔诺河的堤岸，我夺路狂奔，气喘吁吁……左转上了卡斯特拉尼大街，一直朝北而行，始终隐蔽在乌菲兹美术馆的阴影之下。 但他们还是穷追不舍。 他们的脚步声越来越响，这些追捕者冷酷无情，不达目的绝不善罢甘休。 这么多年来，他们一直尾随着我。他们锲而不舍，是的我只能活在地下……被迫呆在炼狱之中……就像冥府的恶魔，时刻忍受地狱的煎熬。 > 我是幽灵。 如今浮生尘世，我举目北望，却看不到通往救赎的捷径——那高耸的亚平宁山脉挡住了黎明的第一缕阳光。

罗伯特 · 兰登在洗下但丁死亡面具上的丙烯石膏后，在背面发现了一行字： > 哦，有着稳固智慧的人啊， > 请注意这里的含义 > 就藏在晦涩的序列面纱之下。 下面有一行由 $1,-1$ 组成的长度为 $n$ 的序列。面具经受了岁月的侵蚀，序列中有一些数已经模糊不清。幸运的是，面具下面有给出两条线索： > 你只得往空缺的位置填 $k$ 个 $1$，其余填入 $-1$，需要最大化这个序列的最大子段和。 > > **一个序列的最大子段和定义为，其在一段连续长度的区间内的最大和。形式化地，一个序列 $a$ 的最大子段和即为 $\max\limits_{l=1}^n\max\limits_{r=l}^n\left(\sum\limits_{i=l}^r a_i\right)$。** 罗伯特 · 兰登希望在瘟疫扩散之前找到有关的线索。于是他找到了你。 - - - #### 【形式化题意】 给定一个只包含 $-1,0,1$ 的序列，求出往 $0$ 的位置上填 $k$ 个 $1$，其余填 $-1$ 后最大子段和的最大值。

第一行两个正整数 $n,k$。 接下来一行 $n$ 个整数 $a_i\in\{-1,0,1\}$，其中 $0$ 表示数字模糊不清。

一行一个正整数，表示可能的最大子段和。

5 2
1 0 -1 0 0

2

#### 【样例解释】 一种可行的方案是填入 $\{1,1,-1\}$，最大子段和为 $2$。 #### 【数据范围】 **本题开启捆绑测试。** | $\text{SubTask}$ | 分值 | $n,k\le $ | | :----------: | :----------: | :----------: | | $0$ | $4$ | $20$ | | $1$ | $6$ | $200$ | | $2$ | $10$ | $5\times 10^3$ | | $3$ | $30$ | $5\times 10^5$ | | $4$ | $50$ | $10^7$ | 对于 $100\%$ 的数据，$1\le n,k\le10^7$，$a_i\in \{-1,0,1\}$。保证 $k\le$ 序列中 $0$ 的个数。 **本题标程使用优化后的输入输出，在 O2 优化下最大点用时约 $350$ ms，足以通过此题。如果您自认为您的程序复杂度正确，却超出时间限制，请使用更优的输入输出方式，或者优化常数。**