题目内容

你正在处理一份由 $n$ 个数据项组成的序列，需要将其切分成若干连续的子段进行归档。每个子段最多包含 $m$ 个连续数据项。

定义每个子段的归档代价为：若子段长度为 $k$，子段中数据项的最小值为 $v_{\min}$，最大值为 $v_{\max}$，固定附加常数为 $s$，则该子段的代价为 $k imes \left\lfloor \frac{v_{\min}+v_{\max}}{2} \right\rfloor + s$ 求将整个序列按规定切分后，所有子段的总代价最小是多少。

数据范围：序列长度 $n$ 满足 $1 \le n \le 10^4$，子段最大长度 $m$ 满足 $1 \le m \le n$ 且 $m \le 10^3$，每个数据项的值以及固定常数 $s$ 均为正整数，大小不超过 $10^4$。

输入描述