242005 - 展品分批检测

题目描述

学校科技展有n件展品等待检测,已经按照登记顺序编号为1至n。检测室只能按照这个顺序处理展品,不能交换展品的先后顺序。

老师需要把全部展品分成若干批。每批必须由原序列中连续的1至k件展品组成,每件展品必须且只能出现在一批中,不允许空批。

每批检测前需要c分钟准备时间。随后,这批展品同时开始检测。第i件展品单独完成检测需要a_i分钟,所以这一批的检测阶段需要等待本批所有展品都完成,也就是耗时等于本批a_i的最大值。

因此,一批的总耗时为“c + 本批最大检测时间”。一批全部结束后,才能开始下一批的准备;不同批之间不能同时进行。第一批也需要准备,最后一批结束后不再增加额外时间。

请合理分批,使全部展品检测完毕的总耗时最少,输出这个最少总分钟数。

输入

第一行三个整数n、k、c,分别表示展品数量、每批最多的展品数和每批准备时间。

第二行n个整数a_1、a_2、…、a_n,按登记顺序给出各展品的检测时间。

【数据范围】

对全部数据,1 \le k \le n \le 2000,0 \le c \le 1000000,1 \le a_i \le 1000000。答案可能超过32位有符号整数的范围,请使用64位整数保存总时间。

输出

输出一个整数,表示完成全部检测的最少总分钟数。不需要输出分批方案。

样例

输入

4 3 2
1 1 10 10

输出

15

输入

3 2 0
3 8 2

输出

10
说明

【样例解释1】

可以分为[1,1]和[10,10]两批,耗时分别为2+1=3和2+10=12,总计15。也可分为[1]和[1,10,10]得到15。若按每批尽量装满,分为[1,1,10]和[10],则耗时为24,不能达到最少时间。

【样例解释2】

分为[3,8]和[2],总耗时为8+2=10。分为[3]和[8,2]的耗时为11,全部单独检测耗时为13;每批最多2件,不能把三件放入同一批。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 3
通过人数 1
金币数量 4 枚
难度 提高


上一题 下一题