Score : $400$ points

问题描述

KEYENCE 公司拥有 $N$ 个部门，其中第 $i$ 个部门有 $A_i$ 名员工 $(1 \leq i \leq N)$。没有任何一名员工属于多个部门。

公司正在计划跨部门项目。每个项目将由来自 $K$ 个不同部门的恰好 $K$ 名员工组成。

在不让任何员工参与多个项目的情况下，最多可以组建多少个项目？

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:57:11