問題文

$1,2, \dots ,N$ の番号が付いた $N$ 種類の鉱石がそれぞれ $A_{1},A_{2}, \dots ,A_{N}$ 個あります。

錬金術師のコアさんは、これらに対して「次の $2$ 種類の操作のうちどちらか一方を自由に選び、これを実行する」
という行為を $0$ 回以上好きな回数だけ行います。

• $1 \leq i < j \leq N$ を満たす整数の組 $(i,j)$ を $1$ つ選び、 鉱石 $i$ を $1$ 個消費して鉱石 $j$ を $1$ 個生成する。

• 鉱石 $1,2, \dots ,N$ を $M$ 個ずつ消費して金塊を $1$ 個生成する。

このとき、コアさんは金塊を最大でいくつ生成できますか？

制約

• $1 \leq N \leq 2 \times 10^{5}$

• $1 \leq M \leq 10^{9}$

• $0 \leq A_{i} \leq 10^{9}$ $(1 \leq i \leq N)$

• 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$ $M$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$

• $1$ 行目には $N$ と $M$ がこの順に半角スペース区切りで与えられる

• $2$ 行目には $A_{1},A_{2},\dots,A_{N}$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力し、最後に改行してください。

サンプル

4 3
5 3 1 3

1

10 2
9 8 7 6 5 4 3 2 1 0

2

7 10
0 100 100 100 100 100 100

0