Reading Room Distancing

Social distancing is in full swing because of the coronavirus. But even before these times, there was a place where distancing was observed well: the reading room.

Mingyu, who worked as a manager at a reading room, discovered something surprising. People always try to sit farther away from each other.

Mingyu observed this and organized it as follows.

1. People prefer the seat that is farthest from the person sitting closest to them. If nobody is using the reading room, they prefer seat number 1 the most.
2. If rule 1 cannot decide, they prefer the seat with the smallest seat number among the farthest seats.

Mingyu, who has worked as a reading room manager for a long time, has a preferred seat. But Mingyu is very timid, so he wants to avoid people being unable to use the seat they wanted to use because of him.

The reading room where Mingyu works is open from 09:00 to 21:00, and it runs strictly by reservation, so Mingyu can know when each person will use the reading room.

Based on this information, Mingyu wants to calculate how much he can use his preferred seat.

The first line gives the number of reading room seats N, the number of reading room reservation holders T, and the seat number P that Mingyu likes, separated by spaces. (1 ≤ N ≤ 100, 1 ≤ T ≤ 500, 1 ≤ P ≤ N)

The next T lines give the reading room entry time and exit time in the form HHMM HHMM.

(0900 ≤ HHMM ≤ 2100, and there is no case where the exit time is earlier than the entry time, such as 0910 0900)

Print the total number of minutes for which Mingyu can use his preferred seat.

All seats in the reading room start empty.

If reservations start at the same time, the person with the shorter usage time is seated first.

There is no state in which a reservation holder in the reading room reservation list cannot sit because there are no seats.

Mingyu wants to calculate how much he can use his preferred seat, so the reservation holders do not affect his use of seats.