思路:序列上的动态规划

状态

$dp_i$ 表示将前 $i$ 个玩具装入玩具袋中的最小花费。

转移

解题关键:

题目内容

小美开的玩具店生意越来越好，每天都有很多客人前来选购玩具。有一天，他接到了一个大单，客户想购买 $n$ 个玩具，并且要求打包成多个玩具袋。小美精心为客户挑选了 $n$ 个玩具，并且将它们编号为 $1,2,\dots,n$。

然而，小美发现这个订购单还有一个要求：每个玩具袋最多只能装 $m$ 个玩具，并且同一个玩具袋里装的玩具编号必须是连续的。玩具袋的成本与容积成线性关系。

为了解决这个问题，他决定采用样本中点估计的方法来计算玩具袋的容积。具体来说，如果一个玩具袋中装的最大的玩具容积是 $u$，最小的是 $v$，那么这个玩具袋的成本就是 $k \times floor((u+v)/2) +s$，其中 $k$ 是玩具袋中装入玩具的个数，$s$ 是一个常数， $floor(x)$ 是下取整函数，比如 $floor(3.8)=3$ ， $floor(2)=2$

客户并没有规定玩具袋的数量，但是希望玩具袋的成本越小越好，毕竟买玩具就很贵了。请求出小美打包这 $n$ 个玩具所用的最小花费。

输入描述

第一行三个正整数 $n,m,s$ 。意义如题面所示

第二行 $n$ 个正整数 $a_1,a_2,...,a_n$ ，表示每个玩具的体积。

对于全部数据, $1\le n \le 10^4$ ， $1\le m \le 10^3$ ， $m \le n$ ， $1 \le a_i, s \le 10^4$ 。

输出描述

输出一个整数，表示打包这 $n$ 个玩具玩具袋的最小成本。

样例

输入

6 4 3
1 4 5 1 4 1

输出

21

样例解释

前三个玩具装成一个玩具袋，后三个玩具装成一个玩具袋。