您想要为毕业作品训练神经网络模型。数据集中有 $$$n$$$ 个图像,第 $$$i$$$ 个图像的大小为 $$$a_i$$$ 字节。
您没有任何强大的远程服务器来训练此模型,因此您必须在本地计算机上进行训练。但有一个问题:数据集的总大小对于您的机器来说太大了,因此您决定删除一些图像 - 尽管您不想使数据集太弱,因此您只能从中删除不超过 $$$k$$$ 图像。请注意,您只能删除图像,不能更改它们的顺序。
您希望以最佳方式删除这些图像,因此您想出了一个指标(毕竟您是数据科学家)来衡量删除结果。考虑删除最多 $$$k$$$ 图像后的数组 $$$b_1, b_2, \ldots, b_m$$$ ($$$n - k \le m \le n$$$)。该数组中的数据将以 $$$x$$$ 连续元素块的形式上传到机器。更准确地说:
- 索引从 $$$1$$$ 到 $$$x$$$ ($$$b_1, b_2, \ldots, b_x$$$) 的元素属于第一个块;
- 索引从 $$$x + 1$$$ 到 $$$2x$$$ ($$$b_{x + 1}, b_{x + 2}, \ldots, b_{2x}$$$) 的元素属于第二个块;
- 索引从 $$$2x + 1$$$ 到 $$$3x$$$ ($$$b_{2x + 1}, b_{2x + 2}, \ldots, b_{3x}$$$) 的元素属于第三个块;
- 等等。
总共会有 $$$cnt = \left\lceil\frac{m}{x}\right\rceil$$$ 块。请注意,如果 $$$m$$$ 不能被 $$$x$$$ 整除,则最后一个块包含的元素少于 $$$x$$$ ,这没问题。
设 $$$w(i)$$$ 为第 $$$i$$$ 块的总大小,即该块内图像大小的总和。例如,第一个块 $$$w(1)$$$ 的大小为 $$$b_1 + b_2 + \ldots + b_x$$$,第二个块 $$$w(2)$$$ 的大小为 $$$b_{x + 1} + b_{x + 2} + \ldots + b_{2x}$$$。
您提出的指标值是结果数据集块的最大块大小。换句话说,指标的值为 $$$\max\limits_{i=1}^{cnt} w(i)$$$。
您不想让机器过载太多,因此您必须以最小化上述指标值的方式删除最多 $$$k$$$ 个图像。
输入
输入的第一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$x$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le k, x \le n$$$) — 分别是数据集中的图像数量、可以删除的最大图像数量以及每个块的长度(可能除了最后一个块)。
输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 图像的大小。
输出
打印一个整数:从数据集中删除不超过 $$$k$$$ 图像后问题陈述中描述的指标的最小可能值。
示例
输入 #1
5 5 4 1 1 5 4 5
输出 #1
0
输入 #2
5 2 4 6 1 5 5 6
输出 #2
11
输入 #3
6 1 4 3 3 1 3 1 2
输出 #3
8
输入#4
6 1 3 2 2 1 2 2 1
输出#4
5
注意
在第一个示例中,您可以删除整个数组,因此答案为 $$$0$$$。
在第二个示例中,可以删除 $$$a$$$ 的第一个和最后一个元素,得到 $$$b = [1, 5, 5]$$$。第一个(也是唯一的)块的大小是 $$$11$$$。所以答案是$$$11$$$。
在第三个示例中,删除$$$a$$$的第二个元素,得到$$$b = [3, 1, 3, 1, 2]$$$。第一个块的大小为 $$$8$$$,第二个块的大小为 $$$2$$$。所以答案是$$$8$$$。
在第四个例子中,可以保持数组$$$a$$$不变,得到$$$b = [2, 2, 1, 2, 2, 1]$$$。第一个块的大小为$$$5$$$,第二个块的大小也是如此。所以答案是$$$5$$$。