Problem F
Hired Help

Viv’s shoe repair company has seen a spike in demand. Today, she has a backlog of shoes that need repairs. So Viv wants to hire some people to assist with the extra work. According to labour laws, each employee is not allowed to repair more than a certain number of shoes (say $K$) each day. Each shoe takes $1$ minute to repair: no more, no less. Each shoe also has a deadline: if it is not repaired by the deadline then the customer gets mad and takes their business elsewhere.

Viv believes everyone should put in an honest day’s work. If an employee fixes fewer than $K$ shoes today then Viv would prefer to not have hired them at all. In fact, she believes in this so strongly that she would prefer to lose business from clients than have an employee not complete their quota.

Help Viv determine the maximum number of employees she can hire so: a) each employee can repair $K$ shoes before their deadlines, and b) each shoe is (of course) repaired by at most one employee.

Input

Input begins with a line consisting of two integers $N$ ($1 \leq N \leq 10^5$) and $K$ ($1 \leq K \leq N$) where $N$ is the number of shoes that need to be repaired and $K$ is as described above.

Then a second line follows containing $N$ space-separated integers $d_1, \ldots , d_ N$ ($1 \leq d_ i \leq 10^9$ for each $1 \leq i \leq N$) describing the deadlines for the repairs. That is, if the repair of shoe $i$ is not completed within at most $d_ i$ minutes of the start of the day then client $i$ will take their business elsewhere.

Note, the days can be much longer on Viv’s planet than ours.

Output

Output a single integer $M$ on a single line indicating the maximum number of employees such that it is possible to allocate $K$ shoes to each employee and each employee can complete their assigned repairs before their respective deadlines, assuming all employees start working on their list of assigned jobs at the start of the day.

6 3
1 1 2 2 1 2

0

6 3
3 1 3 2 1 2

2

6 3
3 1 2 2 1 2

1