炸毁燃料库
测试数据来自 system/1499
背景
某天,外星人展开了对地球的侵略,OIer们开始与之周旋。。。
描述
外星人派出了172849个外星人乘着UFO来到地球,curimit神new带领着OIer们奋力抵抗。curimit神new觉得,仅仅抵抗外星人是不行的,因为外星人还有172849架UFO,必须从根源阻止外星人!
于是curimit神new交给小z一个任务:潜入外星人的基地,摧毁外星人的燃料库。
小z拿着curimit神new给他的地图,来到了外星人的基地。
外星人的燃料库由一排N个燃料筒组成,每个燃料筒中装有一些燃料。小z需要用炸弹炸毁燃料筒。有的燃料筒里面有许多燃料,炸毁它价值就比较高。但有的燃料筒里面只有很少的燃料,甚至没有燃料,所以炸毁它价值很低,甚至不值得去炸毁!于是curimit神new对每个燃料筒有一个估价,有正有负。但是外星人也不是没有防范。在燃料库中有172849个外星人在不停的巡逻,如果小z把任意连续M个燃料筒炸毁K个以上,外星人就会察觉,小z就遭殃了!
于是小z希望你能够帮他定出一个方案,在不被外星人察觉的情况下,能够使自己炸毁的燃料筒的估价和最大(如果所有筒的估价都是负的,那么一个不炸的估价和最大,是0)。
格式
输入格式
第一行有三个数,N,M,K。N<=1000,k<=m<=100。描述见题。
第二行有N个整数,绝对值小于1000,第i个数表示curimit神new对第i个燃料筒的估价。
输出格式
一个数,为满足条件的最大估价和。
样例1
样例输入1
9 5 3
2 3 4 2 3 4 2 3 4
样例输出1
20
限制
各个测试点1s
提示
后记:在小z顺利完成任务之后,curimit神new带领的OIer军队也赶跑了外星人,取得了长久的和平。
此题为经典模型。