Taksi
Taksi xidmətini idarə etmək asan deyil. Sifarişlər gəldikcə onları mümkün qədər tez yerinə yetirmək üçün maşınların mərkəzləşdirilmiş idarə olunmasına ehtiyac var. Eyni zamanda, əvvəlcədən sifariş verən müştərilərin səfərlərini də planlaşdırmaq lazımdır.
Sizin qarşınızda növbəti gün üçün taksi sifarişlərinin siyahısı var. Məqsədiniz, bütün sifarişləri yerinə yetirmək üçün lazım olan minimum taksi maşınlarının sayını azaltmaqdır.
Sadəlik üçün şəhərin planını kvadrat bir şəbəkə kimi qəbul edəcəyik. Şəhərdəki ünvanları tam ədədlər cütü ilə göstərəcəyik: x-koordinatı və y-koordinatı. (a, b) ünvanından (c, d) ünvanına çatmaq üçün tələb olunan vaxt |a-c|+|b-d| dəqiqədir. Taksi növbəti sifarişi ya günün ilk sifarişi olduğu halda, ya da əvvəlki sifarişin son nöqtəsindən başlanğıc nöqtəsinə ən azı bir dəqiqə əvvəl çatdığı halda yerinə yetirə bilər. Diqqət yetirin ki, bəzi sifarişlərin yerinə yetirilməsi gecə yarısından sonra başa çata bilər.
Giriş verilənləri
Giriş faylının ilk sətirində sifarişlərin sayı M (0 ≤ M ≤ 500) verilib. Sonrakı M sətir hər bir sifarişi təsvir edir. Hər sifariş üçün göndərilmə vaxtı hh:mm formatında (aralıq 00:00 ilə 23:59 arasında), göndərilmə nöqtəsinin (a, b) koordinatları və təyinat nöqtəsinin (c, d) koordinatları verilib. Girişdəki bütün koordinatlar qeyri-mənfi və 200-dən çox deyil. Sifarişlər göndərilmə vaxtına görə sıralanmış şəkildə verilib.
Çıxış verilənləri
Çıxış faylına bütün sifarişləri yerinə yetirmək üçün lazım olan minimum taksi maşınlarının sayını göstərən tək tam ədəd yazın.