/ 
Time Limit: 2 sec / Memory Limit: 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