Stipe

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

요약

대기열에서 K명을 골라 접종하되 접종자가 비접종자보다 어리지 않도록 하고, 백신이 남은 동안 조기 귀가시키는 인원을 최소화한다.

난이도: 보통10점 중 5점
유형: 그리디, 스택
정답자: 아직 제출이 없습니다

문제

U redu za cijepljenje stoji N ljudi. Za svaku osobu u redu znamo koliko je stara. Kada redar Stipe vikne Sljedeći!, istupi osoba koja je prva na redu. Na Stipi je tada ili da je propusti na cijepljenje, ili da joj kaže da dođe drugi put.

Doza cjepiva ima ograničeno, njih K, a Stipe će se pobrinuti da se sve iskoriste. Nakon što je cijepljeno K ljudi, Stipe će objaviti kako cjepiva više nema i ostatak ljudi koji stoji u redu poslati kućama.

Za Stipu bi sve bilo jednostavno, kada ne bi postojala opasnost da portali na kraju dana objave vijest: Cijepili mlađeg, a starijeg ne! Kako do toga ne bi došlo, Stipe će paziti da ne postoji nijedan par osoba (X, Y), tako da je osoba X cijepljena, osoba Y ne, a osoba X mlađa je od osobe Y.

Osim toga, Stipe će paziti i da broj ljudi koje pošalje kući dok cjepiva još ima, tj. prije nego što je zadnja osoba cijepljena, bude minimalan. Koliko će ljudi Stipe poslati kući dok cjepiva još ima?

입력

U prvom su retku prirodni brojevi N (1 ≤ N ≤ 100 000) i K (1 ≤ K ≤ N).

U sljedećih N redaka su po tri nenegativna cijela broja G (0 ≤ G ≤ 99), M (0 ≤ M ≤ 11) i D (0 ≤ D ≤ 29), starost osoba u redu, redom od prve do posljednje, izražena u godinama, mjesecima i danima.

출력

U prvi i jedini redak ispiši koliko će ljudi Stipe poslati kući dok cjepiva još ima.

힌트

Opis prvog probnog primjera: Cijepit će se prva i druga osoba, a treća će osoba biti poslana kući zbog nestanka cjepiva. Nijedna osoba neće biti poslana kući dok cjepiva još ima.

Opis drugog probnog primjera: Cijepit će se samo treća osoba, a prve će dvije osobe biti poslane kući dok cjepiva još ima.

Opis trećeg probnog primjera: Cijepit će se prva i treća osoba, a druga i četvrta osoba bit će poslane kući, no samo druga dok cjepiva još ima. Četvrta će osoba biti poslana kući zbog nestanka cjepiva.

예제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
```