You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

我是幽灵。
穿过悲惨之城，我落荒而逃。
穿过永世凄苦，我远走高飞。

沿着阿尔诺河的堤岸，我夺路狂奔，气喘吁吁……左转上了卡斯特拉尼大街，一直朝北而行，始终隐蔽在乌菲兹美术馆的阴影之下。

但他们还是穷追不舍。

他们的脚步声越来越响，这些追捕者冷酷无情，不达目的绝不善罢甘休。

这么多年来，他们一直尾随着我。他们锲而不舍，是的我只能活在地下……被迫呆在炼狱之中……就像冥府的恶魔，时刻忍受地狱的煎熬。

我是幽灵。

如今浮生尘世，我举目北望，却看不到通往救赎的捷径——那高耸的亚平宁山脉挡住了黎明的第一缕阳光。

题目描述

罗伯特 · 兰登在洗下但丁死亡面具上的丙烯石膏后，在背面发现了一行字：

哦，有着稳固智慧的人啊，
请注意这里的含义
就藏在晦涩的序列面纱之下。

下面有一行由 $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$。

【数据范围】

本题开启捆绑测试。

对于 $100\%$ 的数据，$1\le n,k\le10^7$，$a_i\in \{-1,0,1\}$。保证 $k\le$ 序列中 $0$ 的个数。

本题标程使用优化后的输入输出，在 O2 优化下最大点用时约 $350$ ms，足以通过此题。如果您自认为您的程序复杂度正确，却超出时间限制，请使用更优的输入输出方式，或者优化常数。