Stipe

Interview

Time limit1sMemory limit1024 MB

Summary

Pick K people who are each at least as old as everyone skipped, minimizing how many people are turned away before the last dose.

Level: Medium4 of 10
Topics: Array, Sorting, Greedy
Solved: No attempts yet

Problem

Stipe is in charge of a vaccination line. There are N people in the line, and the age of each person is known. When Stipe shouts 'Sljedeći!' ('Next!'), the person at the front of the line steps forward. Stipe then either lets that person get vaccinated or tells them to come back another day.

There are K vaccine doses, and Stipe makes sure all of them are used. After K people have been vaccinated, Stipe announces that there are no doses left and sends the rest of the people in line home.

For Stipe this would be simple, if not for the risk that news portals report at the end of the day: they vaccinated the younger one but not the older one! To prevent this, Stipe makes sure there is no pair of people (X, Y) such that X is vaccinated, Y is not, and X is younger than Y.

Stipe also wants the number of people he sends home while vaccines are still left, that is, before the last person is vaccinated, to be as small as possible. How many people will Stipe send home while vaccines are still left?

Input

The first line contains natural numbers N ( $1 \le N \le 100000$ ) and K ( $1 \le K \le N$ ). Each of the next N lines contains three non-negative integers G ( $0 \le G \le 99$ ), M ( $0 \le M \le 11$ ), and D ( $0 \le D \le 29$ ), the age of the people in line from first to last, in years, months, and days.

Output

Print a single line with the number of people Stipe sends home while vaccines are still left.

Hint

Sample 1: the first and second people are vaccinated, and the third person is sent home when the vaccines run out. No one is sent home while vaccines are still left.

Sample 2: only the third person is vaccinated, and the first two people are sent home while vaccines are still left.

Sample 3: the first and third people are vaccinated. The second and fourth people are sent home, but only the second is sent home while vaccines are still left. The fourth is sent home when the vaccines run out.

Examples3

Example 1
Input
```
3 2
3 3 3
2 2 2
1 1 1
```
Expected output
```
0
```
Example 2
Input
```
3 1
1 2 3
2 3 4
3 4 5
```
Expected output
```
2
```
Example 3
Input
```
4 2
21 2 0
21 1 1
21 2 1
21 1 0
```
Expected output
```
1
```