题目描述

Sashka 很擅长运动。她非常喜欢在 Hemus 高速公路上跑步，这条高速公路长度为 $N$ 千米。

Sashka 经过不同的千米路段会获得不同的愉悦值：经过第 $i$ 千米时，她会获得 $a_i$ 的愉悦值。

Sashka 有一架私人直升机，可以把她送到第 $l$ 千米的起点；她跑完之后，直升机会在第 $r$ 千米的终点接她。若选择区间 $[l,r]$，其中 $1\le l\le r\le N$，她获得的总愉悦值为

对 Sashka 来说，长度至少为 $L$ 千米的路线才有趣，否则太没有挑战性。她会恰好跑 $K$ 次，每次选择一对不同的端点 $(l,r)$，并且要求

她希望最大化这 $K$ 次跑步获得的总愉悦值之和。

请编写程序 running，求出最大可能总愉悦值。

输入格式

第一行包含三个正整数 $N,K,L$。

第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

输出格式

输出一行一个整数，表示最大可能总愉悦值。

数据范围

• $1\le N,K\le 300000$；
• $1\le L\le N$；
• $|a_i|\le 10^6$；
• 保证长度至少为 $L$ 的不同路线数量不少于 $K$。

子任务

某个子任务得分，要求通过该子任务以及所有依赖子任务中的全部测试点。

样例 1

输入

4 4 2
3 2 -6 8

输出

18

解释

长度在 $2$ 到 $4$ 之间的所有路线为：

• $1\to 2$，愉悦值为 $5$；
• $2\to 3$，愉悦值为 $-4$；
• $3\to 4$，愉悦值为 $2$；
• $1\to 3$，愉悦值为 $-1$；
• $2\to 4$，愉悦值为 $4$；
• $1\to 4$，愉悦值为 $7$。

最优选择 $K=4$ 条路线，愉悦值之和为 $7+5+4+2=18$。

样例 2

输入

2 1 2
2 -1

输出

1

解释

唯一可能路线为 $1\to 2$，愉悦值为 $1$。

样例 3

输入

11 21 4
-462 143 441 -637 723 -884 -360 603 -546 -740 -892

输出

-10124