T-Shirts

The organizers of Potyczki Algorytmiczne 2021 usually hand out T-shirts to contestants ranked 1 to 256 in the B+C division standings. Contestants are ranked by their total points from the B and C division problems, and ties are broken by the exact point distribution across individual problems.

Sometimes the organizers hand out more than 256 shirts. They want to satisfy one extra rule: if contestant A has at least as many points as contestant B, and B receives a shirt, then A also receives one, regardless of the exact point distribution.

This rule is not always possible to follow, since it may force the organizers to hand out far more shirts than planned. That is one reason contestants are encouraged to earn points wherever they can, including by submitting solutions with suboptimal time complexity, which often earn partial points even when not stated explicitly. This smooths the standings and makes everyone happier, especially the organizers.

Suppose n contestants take part, the organizers want to hand out at least k shirts, and contestant i earns $a_i$ points. What is the minimum number of shirts the organizers must hand out to satisfy the extra rule as well?

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 2000$), the number of contestants and the minimum number of shirts the organizers want to hand out.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 120$), where $a_i$ is the score of the $i$-th contestant.

Print one integer: the minimum number of shirts the organizers must hand out to satisfy the extra rule.

In this input, the organizers cannot hand out exactly three shirts. For example, giving them to contestants 2, 3, and 4 would shortchange contestant 1. Contestant 1 scored at least as much as contestant 4 but gets no shirt, so the extra rule fails. The solution is to give shirts to everyone except the last contestant.