Hava limanları
Aviaşirkət n hava limanından, 1-dən n-ə qədər nömrələnmiş, aviabiletlər təklif edir. Hər bir i və j cütü üçün i hava limanından j hava limanına uçuş vaxtı t[ij] məlumdur. Külək və ya coğrafi yerləşmə səbəbindən t[ij] ≠ t[ji] ola bilər. Təyyarə hava limanına endikdə, yenidən havaya qalxa bilməsi üçün yoxlanılmalıdır. Yoxlama vaxtı p[i]-dir və yalnız yoxlamanın aparıldığı hava limanından asılıdır.
m təmin edilən reyslər dəstinə malik olaraq, aviaşirkətin almalı olduğu minimum təyyarə sayını müəyyən edin. Əgər bu, tələb olunan təyyarə sayını azaldarsa, aviaşirkət təyyarələrin köçürülməsi üçün planlaşdırılmamış reyslər əlavə edə bilər.
Giriş məlumatları
Birinci sətir n və m ədədlərini (1 ≤ n, m ≤ 500) ehtiva edir. Növbəti sətir n tam ədəd p[1], ..., p[n] (0 ≤ p[i] ≤ 10^6) ehtiva edir.
Növbəti n sətirin hər biri n tam ədəd ehtiva edir. i + 2-ci sətirdəki j-ci ədəd t[ij]-ə bərabərdir (0 ≤ t[ij] ≤ 10^6). Bütün i üçün t[ii] = 0 təmin edilir. Lakin i ≠ j olduqda t[ij] ≠ t[ji] ola bilər.
Növbəti m sətirin hər biri üç tam ədəd s[i], f[i] və t[i] (1 ≤ s[i], f[i] ≤ n, s[i] ≠ f[i], 1 ≤ t[i] ≤ 10^6) ehtiva edir, bu da aviaşirkətin s[i] hava limanından dəqiq t[i] vaxtında uçuş təmin etməli olduğunu və dəqiq f[i] hava limanına uçmalı olduğunu göstərir.
Çıxış məlumatları
Aviaşirkətin m tələb olunan reysləri təmin etmək üçün almalı olduğu minimum təyyarə sayını çıxış edin.