题目描述

哎呀，这些邻居可真能折腾。他们如此憎恨谢别克，给他设下各种陷阱和麻烦。终于，谢别克做了一个梦。这不是普通的梦，在梦里他可以驱逐家里所有的邻居。

谢别克的房子呈环形，被分隔成若干公寓。房子里总共有 $n$ 套公寓，按顺时针方向编号为 $1$ 到 $n$。对于 $1 \leq i \leq n-1$，编号 $i$ 的公寓的下一套是编号 $i+1$ 的公寓，而编号 $n$ 的公寓的下一套是编号 $1$ 的公寓。在编号为 $i$ 的公寓里居住着 $a_i$ 个邻居。

为了把居民赶出房子，谢别克可以 $k$ 次向某个公寓投掷青蛙。所有青蛙的 威力 是一个 $0$ 到 $4$ 之间的整数，并且对所有青蛙都相同，为 $m$。谢别克不必每次都把青蛙投掷到同一套公寓。当谢别克把青蛙投掷到编号为 $i$ 的公寓时，此刻正在公寓 $i$ 里的邻居会永远逃离房子。同时，沿着顺时针方向接下来 $m$ 套公寓里的邻居会感到害怕，并搬迁到顺时针方向第 $m+1$ 套公寓里。逆时针方向也是如此：逆时针方向前 $m$ 套公寓里的邻居会感到害怕，并搬迁到逆时针方向第 $m+1$ 套公寓里。

也就是说，如果房子有 $7$ 套公寓，青蛙被投掷到编号 $6$ 的公寓，且 $m=1$，那么：

• 第 $6$ 套公寓里的所有人将永远消失。
• 第 $7$ 套公寓里的居民将搬迁到第 $1$ 套公寓。
• 第 $5$ 套公寓里的居民将搬迁到第 $4$ 套公寓。

如果 $m=0$，那么没有人会搬迁，只是第 $i$ 套公寓里的邻居逃离。

下图展示了 $n=8$、$m=2$ 时的三种情况。第一张图展示了每套公寓中邻居的初始数量。第二张图展示了青蛙飞入第 $5$ 号公寓后的邻居数量。第三张图展示了另一只青蛙飞入第 $2$ 号公寓后的分布情况。房子周围写有公寓编号。黄色高亮表示青蛙飞入的公寓。

:::align{center} :::

当然，谢别克希望尽可能多地赶走邻居。但他还不够聪明，所以请求你帮助他，告诉他通过 $k$ 次投掷青蛙最多可以赶走多少邻居。

输入格式

第一行包含三个整数 $n$、$k$ 和 $m$ ($0 \leq m \leq 4,\, 2 \cdot m+3 \leq n \leq 2\,000,\, 1 \leq k \leq n$) —— 分别表示房子里的公寓数量、青蛙投掷次数以及青蛙的威力。

第二行包含 $n$ 个整数 $a_i$ ($0 \leq a_i \leq 1\,000\,000$) —— 各公寓的居民数量。

第三行包含一个整数 $g$ ($0 \leq g \leq 10$) —— 测试点所属区块的编号。

输出格式

在一行中输出一个整数 —— 谢别克最多能赶走的邻居数量。

8 2 2
10 10 6 7 15 8 2 1
0

38

5 2 1
2 4 2 1 7
0

13

提示

评分细则

• （10 分） $m = 0$。
• （10 分） $n \leq 11$。
• （10 分） $m \leq 1$，且前 $m$ 套公寓和后 $m$ 套公寓中无人居住。
• （10 分） $m \leq 2$，且前 $m$ 套公寓和后 $m$ 套公寓中无人居住。
• （10 分） $m \leq 1$，且所有公寓要么空置，要么存在 $m + 1 \leq l \leq r \leq n - m$，使得从 $l$ 到 $r$ 的公寓段中各住着一位邻居，而其他所有公寓空置。
• （10 分） $m \leq 1$，且要么满足区块 5 的条件，要么存在 $m + 1 \leq l_1 \leq r_1 < l_2 \leq r_2 \leq n - m$，使得从 $l_1$ 到 $r_1$ 和从 $l_2$ 到 $r_2$ 的公寓段中各住着一位邻居，其他所有公寓空置，并且 $m + 1 \leq l_2 - r_1$。
• （10 分） $m \leq 1$。
• （10 分） $m \leq 2$。
• （10 分） $m \leq 3$。
• （10 分） 无额外限制。

翻译由 DeepSeek V3 完成