Nails

Interview

Time limit1sMemory limit128 MB

Summary

Lower at most k nails to match a chosen height and maximize how many nails share that height.

Level: Easy3 of 10
Topics: Sorting, Greedy
Solved: No attempts yet

Problem

Adam is hammering nails into a board. He has already driven some of the nails to their own heights, but he has no time to keep working. Kozik, standing next to him, wants to drive a few more nails so that as many nails as possible end up at the same height.

Kozik can swing the hammer at most $k$ times. His strength and precision are so great that a single strike can drive any nail down to any height he likes between $0$ and the height at which that nail is currently driven. In other words, one strike lowers a chosen nail to any value from $0$ up to its current height.

Input

The first line contains two integers $n$ and $k$ , the number of nails and the maximum number of times Kozik may strike ( $2 \le n, k \le 10^6$ ).

The second line contains $n$ integers $w_1, w_2, \dots, w_n$ ( $0 \le w_i \le 10^9$ ), where $w_i$ is the height at which the $i$ -th nail is currently driven.

Output

Print a single line with the maximum number of nails that can be at the same height after Kozik finishes striking.

Hint

For example, if six nails are driven at heights $2, 3, 3, 3, 4, 5$ and $k = 2$ , Kozik can lower the two nails at heights $4$ and $5$ down to height $3$ , leaving five nails at height $3$ .

Examples2

Example 1
Input
```
6 2
2 3 3 3 4 5
```
Expected output
```
5
```
Example 2
Input
```
5 2
1 2 3 4 5
```
Expected output
```
3
```