Petya dincəlir#5772
Petya aktiv istirahətin böyük pərəstişkarıdır. Buna görə də, o, məktəbdəki dərslərdən N gün ərzində aktiv istirahət etməyə və M müxtəlif şəhərdə keçirilən K bayram tədbirlərinə qatılmağa qərar verdi. Petya, istirahətinə hər bir şəhərdən digərinə neçə günə çata biləcəyini müəyyən etməklə başladı, həmçinin ziyarət etmək istədiyi bütün tədbirlərin cədvəlini çap etdi və müəyyən etdi. İlk gün Petya birinci şəhərdədir, N-ci gün də orada olmalıdır, əks halda onu məktəbdən qovacaqlar.
Hər bir tədbirin başlanğıc və bitmə günü, həmçinin keçirildiyi şəhər məlumdur. Petya dolu həyat yaşayır, buna görə də hər tədbirdə yalnız tam iştirak edir. Həmçinin Petya eyni vaxtda iki fərqli tədbirdə iştirak edə bilməz, hətta onlar eyni şəhərdə keçirilsə belə. Ancaq əgər iki tədbir eyni şəhərdə keçirilirsə və birincisi ikinci başlayanda bitirsə, Petya hər ikisinə qatıla bilər. O, həmçinin şəhərə gəldiyi gün başlayan və ya şəhərdən ayrıldığı gün bitən tədbirə qatıla bilər.
İnformatika müəllimi sizə ev tapşırığı verdi: Petya-nın maksimum neçə tədbirdə iştirak edə biləcəyini öyrənin.
Birinci sətirdə üç ədəd verilir — aktiv istirahət günlərinin sayı N (1 ≤ N ≤ 10^6), şəhərlərin sayı M (1 ≤ M ≤ 250) və tədbirlərin sayı K (1 ≤ K ≤ 5000).
Növbəti M sətirdə M ədəd yazılıb. i+1-ci sətirdəki j-ci ədəd — i-ci şəhərdən j-ci şəhərə çatmaq üçün lazım olan müsbət tam günlərin sayı A_{i, j}, diaqonal elementlər istisna olmaqla. A_{i, j} ≤ N. Diaqonal elementlər 0-a bərabərdir. Bu matrisdəki 1 dəyəri, Petya-nın müvafiq şəhərə yola düşdükdən sonra növbəti gün gələcəyini bildirir.
Növbəti K sətirdə tədbirlər yazılıb. Hər sətirdə üç müsbət tam ədəd G_i, S_i, F_i — tədbirin şəhər nömrəsi, həmçinin tədbirin başlanğıc və bitmə günləri müvafiq olaraq verilir.
1 ≤ G_i ≤ M, 1 ≤ S_i ≤ F_i ≤ N.
Yeganə ədəd çıxarın — Petya-nın iştirak edə biləcəyi maksimum tədbirlərin sayı.
Nümunə 1