题目描述

暑期快到了，C++1234 班的小 y 又开始了每天的抽象发言。小 y 将要在群里发言 $n$ 天，第 $i$ 天小 y 计划发的消息数是 $a_i$ 条，但是如果小 y 这一天发的消息数量超过 $m$，班主任将会禁言他 $k$ 天，也就是在 $(i+1,i+2,...,min(n,i+k))$ 这些天他无法发言。

在每一天，小 y 都会选择是否完成当天的计划 (如果完成第 $i$ 天的计划他会发 $a_i$ 条消息，否则发 $0$ 条)，现在 小 y 希望你来帮助他计算这 $n$ 天最多共能发多少条消息？

输入格式

输入的第一行为三个正整数，$n,k,m$ ($1≤n≤10^5,1≤k<n,1≤a_i,m≤10^9$)。

输入的第二行为 $n$ 个正整数，表示每一天计划发的消息数。

输出格式

输出一个整数，表示最多能发的消息总数。

5 2 12
8 10 15 23 5

41

7 2 15
16 15 5 16 2 16 1

38

提示