Rikka 准备举办一场全球性的比赛 RCPC（Rikka 的大学生程序设计竞赛）。

准备比赛非常耗时：Rikka 需要花费 $n$ 天的时间。与此同时，RCPC 的官方 QQ 群里有许多由参赛者、教练甚至吃瓜群众提出的问题。因此，Rikka 决定在 $n$ 天中的某些天忽略 QQ 群。

然而，一直忽略问题可能会让参赛者感到愤怒。在第 1 天开始前，参赛者的愤怒值 $A$ 为 0。在第 $i$ 天开始时，愤怒值会增加 $a_i$。随后：

• 如果 $A$ 严格大于阈值 $T$，参赛者会变得极其愤怒，Rikka 将受到 $2A$ 点攻击。随后，在这一天结束时，$A$ 将被清零；
• 如果 $A$ 不超过 $T$ 且 Rikka 选择忽略问题，这一天什么都不会发生；
• 如果 $A$ 不超过 $T$ 且 Rikka 决定回答问题，同时，如果 Rikka 在过去 $K$ 天（即从第 $i-K$ 天到第 $i-1$ 天）都忽略了问题，参赛者会感受到 Rikka 的辛苦。Rikka 不会受到任何攻击，且在这一天结束时，$A$ 将被清零；
• 否则，即使 Rikka 选择回答问题，参赛者仍会因为 Rikka 回答问题太慢而责怪她，Rikka 将受到 $A$ 点攻击。在这一天结束时，$A$ 将被清零。

你的任务是帮助 Rikka 决定在哪些天回答问题，使得她受到的总攻击值最小。

输入格式

第一行包含三个整数 $n, K$ ($1 \le K < n \le 2 \times 10^5$) 和 $T$ ($1 \le T \le 10^9$)。 第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le T$)。

输出格式

输出一个整数，即最小总攻击值。

样例

输入 1

4 1 5
3 1 4 2

输出 1

3

输入 2

10 2 7
2 7 4 4 1 5 6 7 3 1

输出 2

36

说明

对于第一个样例，一种最优方案是在第 1 天和第 3 天回答问题：

• 第 1 天，愤怒值为 3，因此 Rikka 将受到 3 点攻击。
• 第 2 天，愤怒值为 1，因此什么都不会发生；
• 第 3 天，愤怒值为 5。由于 Rikka 在第 2 天没有回答问题，参赛者会感受到 Rikka 的辛苦，因此什么都不会发生；
• 第 4 天，愤怒值为 2，因此什么都不会发生。