問題文

あなたは、$N$ 体のスライムを飼っています。

スライムは横一列に並んでおり、$i$ 番目のスライムの体力は $H_i$ です。

あなたは、以下の $2$ 種類の回復魔法を好きな順番で何度でも行うことができます。

• $1 \leq i \leq N$ を満たす整数 $i$ を選び、$i$ 番目のスライムの体力を $+1$ する。
• $1 \leq i \leq N$ を満たす整数 $i$ を選び、$i$ 番目のスライムの体力を $-1$ する。

あなたの目標は、いずれかの連続する $K$ 匹のスライムについて以下の条件が満たされるようにすることです。

• 体力の最大値 ー 最小値が $D$ 以下である。

目標を達成するために必要な最小の回復魔法の回数を求めてください。

制約

• $2 \leq K \leq N \leq 10^{5}$
• $0 \leq D \leq 10^{9}$
• $0 \leq H_i \leq 10^{9}$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $D$
$H_1$ $H_2$ $\cdots$ $H_N$

出力

問題の答えを一行に出力せよ。

サンプル

5 4 1
1 5 3 9 7

6