Петя відпочиває#5772
Петя — великий шанувальник активного відпочинку. Він вирішив провести днів канікул, відвідуючи святкових заходів у різних містах. На початку своїх канікул Петя визначив, скільки днів йому потрібно, щоб дістатися з одного міста до іншого, а також склав розклад усіх заходів, які планує відвідати. У перший день Петя перебуває в першому місті, і в останній день він також має бути там, інакше його виключать зі школи.
Для кожного заходу відомі дати початку та закінчення, а також місто, де він відбувається. Петя живе на повну, тому відвідує кожен захід повністю. Він не може бути присутнім на двох різних заходах одночасно, навіть якщо вони проходять в одному місті. Проте, якщо два заходи відбуваються в одному місті і перший закінчується в той самий день, коли починається другий, Петя може відвідати обидва. Він також може відвідати захід, що починається в день його прибуття в місто або закінчується в день його від'їзду.
Ваше завдання — визначити максимальну кількість заходів, які Петя може відвідати.
У першому рядку задано три числа: кількість днів відпочинку (1 \le N \le 10^6), кількість міст (1 \le M \le 250) і кількість заходів (1 \le K \le 5000).
У наступних рядках подано по чисел. -е число в (i+1)-му рядку — це ціле додатне число (за винятком діагональних елементів), яке вказує кількість днів A_{i, j}, необхідних для подорожі з -го міста до -го. A_{i, j} \le N. Діагональні елементи дорівнюють . Значення в цій матриці означає, що Петя прибуде у відповідне місто на наступний день після від'їзду.
У наступних рядках описані заходи. У кожному рядку наведено три цілі додатні числа G_i, S_i, F_i — номер міста заходу, а також дні початку і закінчення заходу відповідно.
1 \le G_i \le M, 1 \le S_i \le F_i \le N.
Виведіть одне число — максимальну кількість заходів, які Петя зможе відвідати.
Приклад 1