티셔츠

Potyczki Algorytmiczne 2021 주최 측은 보통 B+C 부문 순위에서 1위부터 256위까지 참가자에게 티셔츠를 나눠 준다. 순위는 B 부문과 C 부문에서 얻은 점수 합으로 매기고, 합이 같으면 문제별 점수 분포를 따진다.

때로는 256장을 넘겨 티셔츠를 더 나눠 주기도 한다. 이때 주최 측은 추가 조건을 지키고 싶어 한다. 참가자 A의 점수가 참가자 B 이상이고 B가 티셔츠를 받았다면, 점수 분포와 관계없이 A도 반드시 티셔츠를 받아야 한다는 조건이다.

이 조건을 지키기 어려울 때도 있다. 계획보다 훨씬 많은 티셔츠를 나눠 줘야 할 수도 있기 때문이다. 그래서 참가자에게는 시간 복잡도가 최적이 아닌 풀이라도 제출해서 점수를 최대한 얻으라고 권장한다. 이런 풀이는 명시하지 않아도 부분 점수를 받는 경우가 많다. 그렇게 하면 순위가 고르게 정리되고 모두가 만족하는데, 특히 주최 측이 그렇다.

참가자가 n명이고 주최 측이 최소 k장의 티셔츠를 나눠 주려 하며, 참가자들이 차례로 $a_1, a_2, \ldots, a_n$점을 얻었다고 하자. 추가 조건까지 지키려면 주최 측은 최소 몇 장의 티셔츠를 나눠 줘야 하는가?

첫째 줄에 두 정수 $n$과 $k$가 주어진다 ($1 \le k \le n \le 2000$). 각각 참가자 수와 주최 측이 나눠 주려는 티셔츠의 최소 개수이다.

둘째 줄에 정수 $n$개 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le 120$). $a_i$는 $i$번째 참가자가 얻은 점수이다.

추가 조건을 만족시키기 위해 주최 측이 반드시 나눠 줘야 하는 티셔츠 수의 최솟값을 정수 하나로 출력한다.

이 입력에서는 티셔츠를 정확히 3장만 나눠 줄 수 없다. 예를 들어 2, 3, 4번 참가자에게 주면 1번 참가자가 불리해진다. 1번은 4번보다 점수가 같거나 높은데 티셔츠를 받지 못하므로 추가 조건이 깨진다. 정답은 마지막 참가자를 제외한 모든 참가자에게 티셔츠를 주는 것이다.