该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

成功，并不是高瞻远瞩。而是你本就站在高处，运筹帷幄，掌控未来。这才是 8848！这才是胸怀天下！顶峰的目标，钛金的气概，真皮的情怀，让我们向成功的人生致敬！

题目描述

现在戴夫又双叒叕在房内举行 ”大喷菇派对“！小 C 怎会放弃这个参与大喷菇派对的机会。但是戴夫还是一如既往的害羞，为了防止小 C 参加大喷菇派对，戴夫在一个长度为 $m$ 的草坪上种下了 $n$ 株坚果，第 $i$ 株坚果的血量为 $h_i$。戴夫的房子位于坐标 $x=0$ 处，而小 C 位于坐标 $x=m$ 处。小 C 会沿着坐标轴反方向，向戴夫家移动。但是会被坚果挡住，如果被第 $i$ 株坚果挡住，需要花 $h_i$ 的时间吃掉这株坚果才可以继续前进。但是：

一些人渴望走的更远、得到更多，这也促使小 C 从普通成为非凡。那就是撑杆跳小 C ！撑杆跳小 C 平时喜欢运动，每日积极训练，现在可以直接翻越坚果。他之前一次训练被小 K 看到了，小 K 当场被震惊。”那简直就是各种高难度动作的缝合怪“ 小 K 这样描述。

小 C 在学校 N 练习了时长两年半的撑杆跳后，终于学会了如何翻越坚果！现在他有一根撑杆，如果当前坐标在 $x$ 使用这根撑杆后，坐标将会变为 $x - k$，即不会被坐标处于 $[x - k + 1, x]$ 的坚果挡住。（注意，如果 $x - k+1$ 小于等于 $0$，小 C 会直接进入疯狂戴夫的家）撑杆只能使用一次，但是由于学会了翻越坚果的艺术，他不像普通的撑杆跳选手，在第一个坚果处就选择使用撑杆，而是可以在任意时刻选择使用撑杆！

小 C 希望花费最少的时间在吃掉坚果上，小 C 当然是绝对聪明的，他也必然知道什么时候使用撑杆最优。所以这次你是疯狂戴夫！你需要种植这 $n$ 株坚果，不妨假设第 $i$ 株坚果种下的坐标为 $x_i$，需要满足 $1 \le x_1 < x_2 < \dots < x_n \le m$ 且 $x_i$ 均为正整数。你现在想知道，如果你按最优的方式种植坚果，小 C 也按最优的方式翻越坚果，你最多可以让小 C 花费多久在吃坚果上？以让你的 ”大喷菇派对“ 举办的尽可能久。

形式化题意：

• 对于一个长度为 $m$ 的非负整数序列，定义其权值为：选择一个长度为 $k$ 的区间，将区间内的数变成 $0$ 后，所有数总和的最小值。
• 给定 $n$ 和 $n$ 个正整数 $h_1,h_2,\cdots,h_n$，你需要选择一个长度为 $n$ 的正整数序列 $x$ 满足 $1 \le x_1 < x_2 < \dots < x_n \le m$。然后根据 $x$ 构造序列 $b$：对于任意 $i(1 \le i \le n)$，$b_{x_i}=h_i$；对于其余位置 $b_i=0$。
• 求 $b$ 的权值的最大值。

输入格式

第一行输入三个正整数 $n, m, k$。

第二行 $n$ 个正整数 $h_1, h_2, \dots, h_n$。

输出格式

一行一个正整数，表示答案

样例

样例输入 #1

6 9 4
1 1 4 5 1 4

样例输出 #1

6

样例解释 #1

方案可能不唯一，一种最优的方案是：$x=\{1,2,3,7,8,9\}$，此时 $b=\{1,1,4,0,0,0,5,1,4\}$，选择长度为 $4$ 的区间 $[6,9]$，$b$ 的权值为 $1+1+4+0+0+0+0+0+0=6$。

样例输入 #2~#7

见下发文件中的 nut2/3/4/5/6/7.in

样例输出 #2~#7

见下发文件中的 nut2/3/4/5/6/7.ans

样例下载点击这里

数据规模与约定

对于所有数据，有：

• $1 \leq k \leq m \leq 10^9$
• $1 \leq n \leq \min(2 \times 10^5, m)$
• $1 \leq h_i \leq 10^9$

子任务 $1(3pts)$：$n=m$

子任务 $2(10pts)$：$n \le 18$

子任务 $3(11pts)$：$n,m \le 40,h_i \le 5$

子任务 $4(12pts)$：$n,m \le 200,h_i \le 5$

子任务 $5(13pts)$：$n,m \le 2000,h_i \le 5$

子任务 $6(22pts)$：$h_i=1$

子任务 $7(29pts)$：无特殊限制