问题说明

有n个球瓶等距排成一排，从左到右的编号分别为 1,2,...,n。每个球瓶都有一个分值（可能为负数），第i个球瓶的分值为ai。
给你K个保龄球，每个球的直径为w。也就是说，每个球可以击倒一个长度为w的区间内的所有球瓶。当然，每个球只能投出一次。
每当用球击倒一个球瓶，他就会得到相应的分值,在某个球瓶被击倒后，球瓶原来的位置会留出空位。另外，球瓶1的左边、球瓶n的右边都有足够的空位。
投出的保龄球可以经过空位，空位上原有的球瓶失效，即不会得到相应的分值。当然，保龄球可以不击倒任何球瓶()。
想知道，你投完所有保龄球后，你最多可以得到多少分？

输入格式

共两行。

第一行3个正整数n,k，分别表示球瓶数量、球的数量、球的直径。

第二行n个整数a1,a2,...,an，表示每个球瓶的分值。

输出格式

一行一个整数，表示能得到的最大的分值。

 对于100%数据，1<=n<=10000,1<=k<=500  |ai|<=1000

9 3 3
2 8 -5 3 5 8 4 8 -6

38

来源/分类