题目描述

你一个人去保龄球馆去打保龄球。总共有 $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\le n\le 10^4$，$1\le w\le 100$，$1\le k\le 500$。