保龄球

题目描述

你一个人去保龄球馆去打保龄球。总共有k个球可用。每个球的宽度为w。在你前方有n个球棒要打。这n球棒紧密的排成一行，且第i个球棒宽度为1，价值为x_i。你的每个球恰能击中第a个~第a+w-1个的球棒（如果此球棒存在的话）。球棒被打到就倒了，且互不影响。你可以向任意方向击球，甚至球的一部分可以越过最左、最右边球棒所构成的边界。求最大价值。

 

---

输入格式

文件第一行是三个整数n,k,w。以下n行是n个整数，第I个代表x_i。

 

---

输出格式

仅一行，为最大价值。

 

---

样例输入

9 2 3
2
8
5
1
9
6
9
3
2
 

---

样例输出

39

 

---

提示

100%的数据满足1≤n≤10000，1≤w≤100，1≤k≤500；

---

题目来源

CCC2007