问题
沃尔夫·索斯在丛林中拥有一大片土地。在这片线性土地上, N 树木定期生长。尺寸 i_{th} 树从一端给出为 t_i.
丛林内部一片漆黑,因为树木阻挡了阳光。为了让阳光照进丛林, 沃尔夫·索特考虑削减一些 N 树木(或不砍伐任何人)。更具体地说,树木将按照以下规则砍伐。
- 最多 M 树木可以砍伐(不超过 M).
- 考虑到对周围生态系统的影响,不允许任意砍伐两棵或两棵以上树木 K 连续的树。更准确地说,不存在 i(1≦i≦N-K+1) 这样 2 或更多树木被砍伐 i_{th}, (i + 1)_{th}, ......, (i + K-1)_{th} 树从一端开始。
- 如果沃尔夫·索斯削减 i_{th} 树从一端开始,树的大小 t_i 变为 0.
- 我们想要大小总和的最大值 K 连续的树要尽可能小。也就是说,我们想要最小化
.
由于尺寸 N 树木和 M, K 已给出,当我们对树木进行最优砍伐选择时,请求出连续树木尺寸总和的最大值中的最小值 K 树。
输入
输入将通过以下格式的标准输入给出。
N M K t_1 t_2 : t_N
- 第一行,整数 将给出 N(1≦N≦100,000), M(1≦M≦N), K(1≦K≦N) 。
- 从第二行开始有 N 附加行提供有关树木大小的信息。 i_{th} 行,整数 t_i(1≦t_i≦1,000,000,000) 。
输出
请打印连续尺寸总和的最大值与最小值 K 树木,当我们为一行中的树木做出最佳切割选择时。
在输出末尾打印换行符。
输入示例 1
6 2 3 1 5 6 2 4 3
输出示例 1
7
如果沃尔夫·索斯削减 3_{rd} 和 6_{th} 树,连续的大小总和的最小值与最大值 3 当为 2_{nd}, 3_{rd}, 4_{th} 树。大小的总和是 5+0+2=7.
输入示例 2
10 3 4 3 14 1 5 9 2 6 5 3 5
输出示例 2
17