Аеропорти
Авіакомпанія пропонує авіаквитки з n аеропортів, пронумерованих від 1 до n. Відомо, що час польоту t[ij] з аеропорту i до аеропорту j заданий для всіх пар i і j. Через вітер або географічне розташування може бути, що t[ij] ≠ t[ji]. Після приземлення в аеропорту літак повинен пройти огляд перед наступним злетом. Час огляду, що дорівнює p[i], залежить лише від аеропорту, де проводиться інспекція.
Маючи набір з m запланованих рейсів, визначте мінімальну кількість літаків, які повинна придбати авіакомпанія. Авіакомпанія може додавати додаткові рейси для переміщення літаків, якщо це зменшить загальну кількість необхідних літаків.
Вхідні дані
Перший рядок містить числа n і m (1 ≤ n, m ≤ 500). Наступний рядок містить n цілих чисел p[1], ..., p[n] (0 ≤ p[i] ≤ 10^6).
Кожен з наступних n рядків містить n цілих чисел. j-е число в рядку i + 2 дорівнює t[ij] (0 ≤ t[ij] ≤ 10^6). Гарантовано, що t[ii] = 0 для всіх i. Однак може бути, що t[ij] ≠ t[ji] при i ≠ j.
Кожен з наступних m рядків містить три цілі числа s[i], f[i] і t[i] (1 ≤ s[i], f[i] ≤ n, s[i] ≠ f[i], 1 ≤ t[i] ≤ 10^6), які вказують на те, що авіакомпанія повинна забезпечити політ з аеропорту s[i] з точним часом вильоту t[i], прямуючи в аеропорт f[i].
Вихідні дані
Виведіть мінімальну кількість літаків, які повинна придбати авіакомпанія для забезпечення m необхідних рейсів.