D - Project Planning

Contest Duration: 2021-11-13(Sat) 12:00 - 2021-11-13(Sat) 13:40 (local time) (100 minutes) Back to Home

D - Project Planning Editorial

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$

出力

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

入力例 1Copy

Copy

3 3
2 3 4

出力例 1Copy

Copy

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

入力例 2Copy

Copy

4 2
1 1 3 4

出力例 2Copy

Copy

入力例 3Copy

Copy

4 3
1 1 3 4

出力例 3Copy

Copy

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 1Copy

Copy

3 3
2 3 4

Sample Output 1Copy

Copy

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

Sample Input 2Copy

Copy

4 2
1 1 3 4

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

4 3
1 1 3 4

Sample Output 3Copy

Copy