Stipe

면접 대비

시간 제한1초메모리 제한1024 MB

요약

나이가 주어진 N명 중에서 탈락한 사람보다 모두 나이가 많도록 K명을 고르고, 마지막 접종 전에 돌려보내는 사람 수의 최솟값을 구합니다.

난이도: 보통10점 중 4점
유형: 배열, 정렬, 그리디
정답자: 아직 제출이 없습니다

문제

백신 접종을 기다리는 줄에 N명의 사람이 서 있다. 줄에 선 사람마다 나이가 주어진다. 접종 담당자 Stipe가 'Sljedeći!'(다음!)라고 외치면 줄의 맨 앞 사람이 앞으로 나온다. Stipe는 그 사람을 접종시키거나, 다른 날 다시 오라고 돌려보낸다.

백신은 K회분이고, Stipe는 백신을 모두 사용한다. K명이 접종을 받으면 Stipe는 백신이 더 없다고 알리고, 줄에 남은 사람들을 집으로 돌려보낸다.

Stipe의 일이 단순하기만 하다면 좋겠지만, 하루가 끝나면 언론이 "어린 사람은 접종하고 나이 많은 사람은 접종하지 않았다!"라고 보도할 위험이 있다. 이를 막기 위해 Stipe는 접종받은 사람 X, 접종받지 못한 사람 Y의 쌍 (X, Y) 가운데 X가 Y보다 어린 쌍이 없도록 한다.

또한 Stipe는 백신이 아직 남아 있을 때 집으로 돌려보내는 사람 수를 최소로 하려고 한다. 즉, 마지막 사람이 접종받기 전에 돌려보내는 사람 수가 최소가 되어야 한다. 백신이 아직 남아 있을 때 Stipe는 몇 명을 집으로 돌려보내는가?

입력

첫째 줄에 자연수 N ( $1 \le N \le 100000$ )과 K ( $1 \le K \le N$ )가 주어진다. 이어지는 N개의 줄에는 줄에 선 순서대로 첫 번째 사람부터 마지막 사람까지의 나이가 한 줄에 하나씩 주어진다. 각 줄에는 음이 아닌 정수 G ( $0 \le G \le 99$ ), M ( $0 \le M \le 11$ ), D ( $0 \le D \le 29$ ) 세 개가 공백으로 구분되어 있으며, 각각 년, 개월, 일 단위의 나이이다.

출력

백신이 아직 남아 있을 때 Stipe가 집으로 돌려보내는 사람 수를 첫 번째이자 유일한 줄에 출력한다.

힌트

첫 번째 입력 설명: 첫 번째와 두 번째 사람이 접종을 받고, 세 번째 사람은 백신이 떨어져서 집으로 돌려보내진다. 백신이 남아 있는 동안 돌려보내진 사람은 없다.

두 번째 입력 설명: 세 번째 사람만 접종을 받고, 첫 번째와 두 번째 사람은 백신이 남아 있는 동안 집으로 돌려보내진다.

세 번째 입력 설명: 첫 번째와 세 번째 사람이 접종을 받는다. 두 번째와 네 번째 사람은 집으로 돌려보내지지만, 백신이 남아 있는 동안 돌려보내지는 사람은 두 번째뿐이다. 네 번째 사람은 백신이 떨어졌을 때 돌려보내진다.

예제3

예제 1
입력
```
3 2
3 3 3
2 2 2
1 1 1
```
예상 출력
```
0
```
예제 2
입력
```
3 1
1 2 3
2 3 4
3 4 5
```
예상 출력
```
2
```
예제 3
입력
```
4 2
21 2 0
21 1 1
21 2 1
21 1 0
```
예상 출력
```
1
```