Tables

Peter’s friend, Paul is the boss in a restaurant and he asked for Peter’s help in a troublesome matter! The restaurant’s online booking system has malfunctioned: some reservations were mistakenly booked which are impossible to satisfy. Your job is to filter out these from the bookings. In the restaurant there are $A$ tables, each of which has $S$ seats. The reservation system worked the following way: every potential customer provided $3$ numbers $e$, $t$ and $g$ which the system temporarily accepted. $e<t$ are the time of arrival and departure. $g-1$ is the number of companions the customer comes with. Then at midnight the system has closed. Then it was supposed to execute the following algorithm: find the temporary reservation with earliest arrival time (in case of a tie, choose the one which was booked earlier). If there are enough fully empty tables to seat these guests, then confirm this reservation, else reject the reservation (sending an email to the customer).

Note that the during the seating, minimal number of tables are assigned to the groups, that is if $g=10$ and $S=3$, then $4$ tables should be reserved, even if there are more available. Another important condition is not to mix different groups, that is if $g=3$ and there are no empty tables but there are a partially filled table with $3$ free seats, then the reservation must be rejected.

Example: let $R=5\ \ A=4\ \ S=4$

arrival (e)	departure (t)	group size (g)
10	20	8
15	30	4
10	25	10
28	50	13
41	71	10

The third reservation was rejected because of lack of tables. The first reservation is confirmed, the second one as well, since at the time of their arrival there are two empty tables. The fourth reservation is rejected. The fifth is confirmed. Overall there are $2$ rejected reservations.

Please help Peter by writing a program which calculates the number of rejected reservations!

Input specification

On the first line of the input, there are $3$ numbers: $R$, $A$, $S$. Each of the next $R$ lines contains $3$ integers: $e_i, t_i, g_i$. The information (arrival, departure and number of guests (the group size)) about the $i$th reservation.

Output specification

Output a single integer: the number of rejected reservations.

Constraints

$1\le R \le 10000$
$1\le A \le 1000$
$1\le S \le 10$
$1\le e_{i},t_{i} \le 1000000000$
$1\le g_{i} \le 100$

Sample input 1

1. 5 4 4
2. 10 20 8
3. 15 30 4
4. 10 25 10
5. 28 50 13
6. 41 71 10

download as text file

Sample output 1

1. 2

download as text file

Sample input 2

1. 9 3 4
2. 1 5 2
3. 2 5 3
4. 3 5 4
5. 4 5 2
6. 5 10 3
7. 6 10 4 
8. 7 10 2
9. 8 10 3
10. 9 10 4

download as text file

Sample output 2

1. 3

download as text file

Sample input 3

1. 5 4 4
2. 10 20 8
3. 20 30 4
4. 30 40 10
5. 40 50 7
6. 50 60 10

download as text file

Sample output 3

1. 0

download as text file