学校科技展有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]和[10,10]两批,耗时分别为2+1=3和2+10=12,总计15。也可分为[1]和[1,10,10]得到15。若按每批尽量装满,分为[1,1,10]和[10],则耗时为24,不能达到最少时间。
分为[3,8]和[2],总耗时为8+2=10。分为[3]和[8,2]的耗时为11,全部单独检测耗时为13;每批最多2件,不能把三件放入同一批。