Bunu təşkil etmək olar
Hər il bir neçə universitet proqramlaşdırma üzrə universitetlərarası yarışlar təşkil edir. ACM ICPC Dhaka hər il Dakkada regional yarış keçirir və burada ACM ICPC dünya çempionatında iştirak etmək üçün bir və ya iki komanda seçilir.
Bu məqsədlə, MMR (Rahman Missiyası) proqramlaşdırma məktəbi açmağa qərar verdi. Məktəbdə n fənn tədris olunacaq. Hər bir fənn hər gün tədris olunacaq (əks halda proqramçılar hesablama həndəsəsini öyrənərkən DP-ni unudacaqlar!). Sizə hər bir kursun i (1 ≤ i ≤ n) başlanğıc a_i və son vaxtı b_i (daxil olmaqla) veriləcək. Həmçinin bu kursa qeydiyyatdan keçmiş tələbələrin sayı s_i (1 ≤ i ≤ n) məlum olacaq. Heç bir tələbə iki fərqli kursa qeydiyyatdan keçməyib. MMR bu məktəbin fəaliyyəti üçün Qüllə Müşahidə binasında bir neçə otaq icarəyə götürmək istəyir. Hər bir otaq m tələbəyə qədər yerləşdirə bilər. Proqramçılar (tələbələr) çox narahat və bir az çirkindir! Buna görə də, i fənni sinifdə başa çatdıqda, j fənnini i fənnindən sonra eyni sinifdə başlamaq üçün clean_ij vaxt sərf etmək lazımdır.
Siz MMR-ə proqramlaşdırma məktəbinin fəaliyyəti üçün icarəyə götürülməli olan ən az sinif sayını müəyyən etməyə kömək etməlisiniz.
Giriş verilənləri
Testlərin sayı t (t ≤ 100) ilə başlayır. Hər bir test iki tam ədədlə başlayır: kursların sayı n (1 ≤ n ≤ 100) və otaqların tutumu m (1 ≤ m ≤ 10000). Növbəti n sətir hər bir kursun başlanğıc və son vaxtını a_i, b_i (0 ≤ a_i ≤ b_i ≤ 10000000) və s_i (1 ≤ s_i ≤ 10000) üç tam ədədini ehtiva edir. Növbəti n sətir vaxt matrisini təsvir edir, burada i-ci sətir n tam ədəd clean_ij (1 ≤ i ≤ n, 1 ≤ j ≤ n, 0 ≤ clean_ij ≤ 10000000, clean_{ii}= 0) ehtiva edir.
Çıxış verilənləri
Hər bir test üçün onun nömrəsini, 1 ilə başlayaraq, və cavabı - icarəyə götürülməsi lazım olan ən az otaq sayını ayrıca sətirdə çıxarın.