A257.打保龄球

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

共两行。

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

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

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