题目内容

小塔有一个长度为$n$的数组$a$，下标从$1$开始，一个好数组要求任意连续的$k$个元素的总和不超过$sum$。

现在可以执行任意次修改，每次修改选择一个下标$i(1≤i≤n)$，令$a_i=a_i-1$，注意$a$不能是负数。

最少执行几次操作，才能使得数组成为一个好数组。

输入描述

第一行三个整数

$n$ $k$ $sum(1≤k≤n≤2×10^5, 1≤sum≤10^{13})$，含义和题目描述一致。

第二行包含$n$个整数$a_i(0≤a_i≤10^9)$，表示数组。

输出描述

输出一行一个整数，表示最少操作次数。

样例1

输入

5 3 10
9 7 3 6 5

输出

10

说明

修改为$[9,1,0,5,5]$，只需要操作$10$次。