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