配点 : $400$ 点

問題文

キーエンスには $N$ 個の部署があり、$i\,(1 \leq i \leq N)$ 番目の部署には $A_i$ 人の社員が所属しています。異なる部署に同じ社員が所属していることはありません。

キーエンスは、部署をまたいだ全社横断プロジェクトを計画しています。$1$ つのプロジェクトは $K$ 個の相異なる部署から $1$ 人ずつ選出して作り、ちょうど $K$ 人から構成されるようにします。

プロジェクトは最大でいくつ作れますか？ただし、$1$ 人が複数のプロジェクトに参加することはできません。

制約

• $1 \leq K \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^{12}$
• 入力は全て整数

入力

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

$N$ $K$

$A_1$ $A_2$ $\ldots$ $A_N$

出力

プロジェクトの個数の最大値を出力せよ。

3 3
2 3 4

2

$3$ 個の部署それぞれから $1$ 人ずつ選出したプロジェクトを $2$ つ作ることができます。

4 2
1 1 3 4

4

4 3
1 1 3 4

2