配点: 100 点
你知道 Juicy Orange Industry 公司吗?这家公司的业务是栽培并出货美味的橙子。在这里简称为 JOI 公司。
在 JOI 公司,收获的 N 橙子装箱并运输。工厂里的橙子排列在传送带上,从传送带的前面按顺序放置。 它们的编号最大为 1 它们的编号最大为 N 。橙子有各种大小。 i (1 \leqq i \leqq N) 的大小是 A_i 。从
将这些橙子分成几个盒子,从前面按顺序包装。只有连续编号的橙子才能装在一个盒子里。
一盒最多可容纳 它最多可填充 M 个橙子。将多个橙子装入一个盒子的成本是通过计算可装入盒子的最大橙子的尺寸来计算的。 a、一个盒子装的最小橙子的尺寸 b,一个盒子要装的橙子数量 当 s 时, 可以使用K + s \times (a - b) 找到它。在这里,K 是盒子的成本,并且是所有盒子的共同值。
我们希望通过准备适当数量的盒子并适当地包装所有橙子来尽可能降低装箱的总成本。
課題
给定传送带上排列的橙子的信息、一个盒子中可以包装的最大橙子数量以及包装盒子的成本,编写一个程序,找出包装盒子的总成本的最小值。
入力
从标准输入读取以下输入。 在
- 1 行中,3 整数 N, M, K 以空格作为分隔符。这是一个橙子 有 N 个橙子,一箱最多可装橙子数为 M 盒子的成本是 K 。
- 继续 N 行 i 行目 (1 \leqq i \leqq N) 是一个整数 写入 A_i 。这是橙色的 i 的大小是 A_i 。
出力
包装总成本的最小值是输出到标准输出。 输出为 1 行。
制限
所有输入数据满足以下条件。
- 1 \leqq N \leqq 20\,000.
- 1 \leqq M \leqq 1\,000.
- 0 \leqq K \leqq 1\,000\,000\,000.
- 1 \leqq A_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
- M \leqq N.
小課題
小課題 1 [20 点]
- N \leqq 20 满意。
小課題 2 [50 点]
满足以下条件。
- N \leqq 2\,000.
- M \leqq 100.
小課題 3 [30 点]
没有其他限制。
入力例 1
6 3 6 1 2 3 1 2 1
出力例 1
21
1 盒子里的橙色 橙色来自 1 从橙色 3 最多 装满了 3 橙子, 如果包装2 盒子里的橙色 橙色来自 4 从橙色 6 最多 装满了 3 橙子,总包装成本为 (6 + 3 \times (3 - 1)) + (6 + 3 \times (2 - 1)) = 21 变为。
无论你如何包装,包装总成本为 由于它永远不会小于 21 , 输出21 。 准备
入力例 2
16 4 12 3 10 13 10 19 9 12 16 11 2 19 9 13 2 13 19
出力例 2
164
11 个盒子,从前面按顺序填写每个盒子。 包装 1 個,3 個,1 個,1 個,3 個,1 個,1 個,2 個,1 個,1 個,1 橙子可最大限度地降低装箱的总成本。
入力例 3
16 6 14 19 7 2 15 17 7 14 12 3 14 5 10 17 20 19 12
出力例 3
177
入力例 4
10 1 1000000000 1 1 1 1 1 1 1 1 1 1
出力例 4
10000000000
答案是 32 请注意,它不一定落在有符号整数的范围内。