D - Project Planning 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 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

出力

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

入力例 1

3 3
2 3 4

出力例 1

2

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

入力例 2

4 2
1 1 3 4

出力例 2

4

入力例 3

4 3
1 1 3 4

出力例 3

2

Score : 400 points

Problem Statement

KEYENCE has N departments, where A_i employees belong to the i-th department (1 \leq i \leq N). No employee belongs to multiple departments.

The company is planning cross-departmental projects. Each project will be composed of exactly K employees chosen from K distinct departments.

At most how many projects can be made? No employee can participate in multiple projects.

Constraints

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^{12}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

Print the maximum possible number of projects.

Sample Input 1

3 3
2 3 4

Sample Output 1

2

There can be two projects, each composed of three employees from distinct departments.

Sample Input 2

4 2
1 1 3 4

Sample Output 2

4

Sample Input 3

4 3
1 1 3 4

Sample Output 3

2