题目描述

仓库里有 $n$ 个包裹，必须按照编号 $1,2,\ldots,n$ 的顺序装车，不能改变相对顺序。

一次装车可以把连续的若干个尚未装车的包裹作为一个批次，批次大小不能超过 $K$。

第 $i$ 个包裹的重量为 $a_i$。若某个批次包含区间 $[l,r]$，其费用为

其中 $P$ 是每启动一个批次都要支付的固定费用。

你需要把全部包裹划分成若干个连续批次，求最小总费用。

输入格式

第一行三个整数 $n,K,P$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示最小总费用。

样例

5 3 10
1 3 2 4 2

37

数据范围

• $1\le n\le 5000$；
• $1\le K\le \min(n,500)$；
• $0\le P\le 10^9$；
• $0\le a_i\le 10^9$。