Maximizing Subarray Sum on Modified Sequence

Robert Langdon discovered a mysterious inscription on the back of Dante's death mask. The inscription hints:

Oh, you of steadfast wisdom,

Do pay heed to the meaning here,

Concealed beneath the obscure veil of a sequence.

You are given a sequence of length \(n\) whose elements belong to \(\{-1, 0, 1\}\). The entries with value \(0\) are faded. Fortunately, two clues are provided:

• You must replace exactly \(k\) of the \(0\) entries with \(1\).
• The remaining \(0\) entries must be replaced by \(-1\).

After replacement, the sequence will consist solely of \(1\) and \(-1\). The maximum subarray sum of a sequence \(a\) is defined as \[ \max_{1 \le l \le r \le n} \left(\sum_{i=l}^{r} a_i\right). \]

Your task is to choose the positions among the faded entries (the \(0\)'s) to replace with \(1\) (using exactly \(k\) such replacements), filling the rest with \(-1\), so that the maximum subarray sum of the resulting sequence is maximized. Output that maximum sum.

inputFormat

The first line contains two integers \(n\) and \(k\), where \(n\) is the length of the sequence and \(k\) is the number of \(0\) entries to be replaced with \(1\).

The second line contains \(n\) space-separated integers, each being \(-1\), \(0\), or \(1\), representing the sequence.

outputFormat

Output one integer: the maximum subarray sum obtainable after performing the replacements optimally.

sample

5 1
0 1 -1 0 -1

2