A346. 打保龄球

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

共两行。

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

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

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