問題文

$N$ 個のマスが円周上に並んだすごろくがあり、マスには、時計回りに $1, 2, …, N$ の番号がついています。
また、マスにはそれぞれ数字がかかれており、番号 $i \; (1 \leq i \leq N)$ のマスには $A_i$ がかかれています。

ゲーム開始時点では、あなたの駒はマス $1$ にあり、以下の行動を何回でも行うことができます。

• 時計回りに $1$ マス進むことを駒が立っていたマスにかかれた数字の分だけ繰り返す。

このすごろくは、マス $N$ とマス $1$ の間を通り過ぎるたびにカウントが $1$ 上昇し、ゲーム開始時点でのカウントは $0$ です。

カウントを $K$ 以上にするのに必要な行動の回数の最小値を求めてください。

制約

• $3 \leq N \leq 10^5$
• $1 \leq K \leq 10^9$
• $1 \leq A_i \leq 10^9 \: (1 \leq i \leq N)$
• 入力はすべて整数である。

入力

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

N K
A_1 A_2 ...... A_N

出力

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

入出力例

4 1
1 2 1 2

3

$1$ 回目の行動では、マス $1$ から マス $2$ へと移動します。
$2$ 回目の行動では、マス $2$ から マス $4$ へと移動します。
$3$ 回目の行動では、マス $4$ と マス $1$ の間を通り、マス $2$ へと移動します。
$3$ 回目の行動でカウントが $1$ 以上になったため、$3$ と出力します。

8 5
4 4 6 3 7 5 10 3

8