Petya is resting
Petya loves staying active, so he's decided to take a break from school for N days to attend K festive events across M different cities. He starts his vacation by figuring out the travel time between each pair of cities and planning the schedule for all the events he wants to attend. On the first day, Petya is in the first city, and he must return there by day N, or he'll face expulsion from school.
For each event, the start day, end day, and the city where it occurs are known. Petya is determined to make the most of his time, so he attends each event from start to finish. He cannot be at two events simultaneously, even if they're in the same city. However, if one event ends on the same day another begins in the same city, he can attend both. He can also attend an event that starts on the day he arrives in a city or ends on the day he leaves.
Your computer science teacher has assigned you a task: determine the maximum number of events Petya can attend.
Input
The first line contains three numbers: the number of days of active leisure N (1 ≤ N ≤ 10^6), the number of cities M (1 ≤ M ≤ 250), and the number of events K (1 ≤ K ≤ 5000).
The next M lines each contain M numbers. The j-th number in the i+1-th line is a positive integer (except for diagonal elements) representing the number of days A_{i, j} needed to travel from city i to city j. A_{i, j} ≤ N. Diagonal elements are 0. A value of 1 in this matrix means Petya will arrive in the destination city the day after departure.
The following K lines list the events. Each line contains three positive integers G_i, S_i, F_i — the city number of the event, and the start and end days of the event, respectively.
1 ≤ G_i ≤ M, 1 ≤ S_i ≤ F_i ≤ N.
Output
Output a single number — the maximum number of events Petya can attend.