Ready to fight for the Potyczki Algorytmiczne 2021 t-shirts? We usually distribute them to participants who placed between 1st and 256th in the B+C division ranking, where we compare contestants primarily by looking at the sum of points scored for tasks from division B and division C, and in the event of a tie, we also take into account the exact distribution of points for individual tasks.
Sometimes we are able to make an exception and distribute even more than 256 t-shirts, as we would like to satisfy an additional condition stating that if participant A scored at least as many points as participant B and participant B receives a t-shirt, then participant A will also receive one, regardless of the exact distribution of points.
In practice, it is not always possible to satisfy the aforementioned additional condition, as it could mean that we would have to distribute many more t-shirts than we planned. This is one of the reasons why we encourage contestants to try to score points wherever they can, by also submitting solutions with non-optimal time complexity (which can often count for a partial number of points, even if not explicitly stated in the problem description). This smooths out the ranking and makes everyone involved happy (especially the organizers).
If $n$ participants took part in the competition, the organizers would like to distribute at least $k$ t-shirts, and the participants scored $a_1, a_2, a_3, \dots, a_n$ points respectively, how many t-shirts would the organizers have to distribute at a minimum to also satisfy the additional condition?
Input
The first line of input contains two integers $n$ and $k$ ($1 \le k \le n \le 2000$), representing the number of participants and the minimum number of t-shirts the organizers want to distribute, respectively.
The second line contains a sequence of $n$ integers $a_1, a_2, a_3, \dots, a_n$ ($1 \le a_i \le 120$), where $a_i$ denotes the number of points scored by the $i$-th contestant.
Output
The output should contain a single integer representing the minimum number of t-shirts the organizers must distribute to satisfy the additional condition.
Examples
Input 1
5 3 75 90 120 75 40
Output 1
4
Note
Explanation of the example: The organizers could not distribute exactly three t-shirts, for example by giving them to participants numbered 2, 3, and 4, because then the first participant would be wronged (since they scored no fewer points than the fourth participant, and unlike them, did not receive a t-shirt, so the additional condition would not be met). The solution is to give t-shirts to all contestants except the last one.
Subtasks
In some test groups, the condition $k = 1$ holds, meaning the organizers want to distribute at least one t-shirt.