Hava limanları#8181
Aviaşirkət -dən -ə qədər nömrələnmiş hava limanı arasında reyslər həyata keçirir. Hər bir və hava limanı cütü üçün -dən -yə uçuş müddəti t_{ij} məlumdur. Ümumi halda külək şəraiti və ya coğrafi xüsusiyyətlərə görə t_{ij} \ne t_{ji} ola bilər.
Hava limanına çatdıqdan sonra təyyarə növbəti uçuşdan əvvəl texniki yoxlamadan keçməlidir. Yoxlama müddəti p_i-yə bərabərdir və yalnız onun aparıldığı hava limanından asılıdır.
məcburi reys verilmişdir. Aviaşirkətin onları yerinə yetirmək üçün lazım olan minimum təyyarə sayını müəyyən edin. Lazım olan ümumi təyyarə sayını azaltmaq mümkündürsə, təyyarələrin yenidən bazalanması üçün sərnişinsiz əlavə (qeyri-planlı) uçuşlar həyata keçirməyə icazə verilir.
Birinci sətirdə iki tam ədəd və m~(1 \le n, m \le 500) verilmişdir.
İkinci sətirdə tam ədəd p_1, p_2, \dots, p_n~(0 \le p_i \le 10^6) verilmişdir.
Sonra hər birində tam ədəd olan sətir gəlir. -ci sətirdəki -ci ədəd t_{ij} (0 \le t_{ij} \le 10^6) qiymətini verir. Bütün üçün t_{ii} = 0 olduğu zəmanət verilir. Bu zaman i \ne j olduqda t_{ij} \ne t_{ji} ola bilər.
Sonra sətir gəlir, hər biri üç tam ədəd s_i, f_i və t_i~(1 \le s_i, f_i \le n, s_i \ne f_i, 1 \le t_i \le 10^6) ehtiva edir. Bu o deməkdir ki, aviaşirkət s_i hava limanından f_i hava limanına dəqiq t_i vaxtında uçuşu təmin etməlidir.
Aviaşirkətin verilmiş reysin hamısını yerinə yetirmək üçün lazım olan minimum təyyarə sayını çap edin.
Nümunə 1
Nümunə 2
Nümunə 3