水果打包

题面

1. 有一批水果需要打包, 数量为 $n$ 个, 每个水果都有体积 $t$;
2. 每个果篮最多放 $m$ 个水果;
3. 每个果篮的价格为 $k * \lfloor(u + v) / 2\rfloor + s$, $k$ 为果篮中水果数量, $u, v$ 分别为果篮中水果的最大/最小体积, $s$ 为常数;
4. 水果必须按照顺序放入果篮;
5. 要求使用果篮的总价格最小;

输入

1. 第一行为水果数量 n, 每个果篮的最大水果数量 $m$, 常数 $s$, $1 \le n, m, s \le 10^5$;
2. 第二行为 $n$ 个水果的体积 $t_i$, $1 \le t_i \le 10^3$;

6 4 3
1 4 5 1 4 1

输出

一行, 为使用果篮的最小总价格.

21