#abc227d. [abc227_d]Project Planning

[abc227_d]Project Planning

問題文

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

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

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

制約

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

入力

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

NN KK A1A_1 A2A_2 ldots\\ldots ANA_N

出力

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


入力例 1

3 3
2 3 4

出力例 1

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


入力例 2

4 2
1 1 3 4

出力例 2


入力例 3

4 3
1 1 3 4

出力例 3