Аеропорти#8181

Аеропорти

1 секунда

128 мегабайтів

Дуже легка

Авіакомпанія виконує рейси між $n$ аеропортами, пронумерованими від $1$ до $n$ . Для кожної пари аеропортів $i$ та $j$ відомий час перельоту $t_{ij}$ t_{ij} з $i$ до $j$ . У загальному випадку $t_{ij} \neq = t_{j i}$ t_{ij} \ne t_{ji} через вітрові умови або географічні особливості.

Після прибуття до аеропорту літак повинен пройти технічний огляд перед наступним вильотом. Час огляду дорівнює $p_{i}$ p_i і залежить лише від аеропорту, в якому він проводиться.

Задано $m$ обов'язкових рейсів. Визначте мінімальну кількість літаків, яка необхідна авіакомпанії для їх виконання. Дозволяється виконувати додаткові (позапланові) перельоти без пасажирів для перебазування літаків, якщо це дозволяє зменшити загальну кількість необхідних літаків.

Вхідні дані

У першому рядку задано два цілих числа $n$ та $m (1 \leq n, m \leq 500)$ m~(1 \le n, m \le 500).

У другому рядку містяться $n$ цілих чисел $p_{1}, p_{2}, \dots, p_{n} (0 \leq p_{i} \leq 1 0^{6})$ p_1, p_2, \dots, p_n~(0 \le p_i \le 10^6).

Далі йдуть $n$ рядків по $n$ цілих чисел у кожному. $j$ -е число в $i$ -му рядку задає значення $t_{ij}$ t_{ij} $(0 \leq t_{ij} \leq 1 0^{6})$ (0 \le t_{ij} \le 10^6). Гарантується, що $t_{ii} = 0$ t_{ii} = 0 для всіх $i$ . При цьому для $i \neq = j$ i \ne j може виконуватися $t_{ij} \neq = t_{j i}$ t_{ij} \ne t_{ji}.

Потім йдуть $m$ рядків, кожен з яких містить три цілих числа $s_{i}, f_{i}$ s_i, f_i та $t_{i} (1 \leq s_{i}, f_{i} \leq n, s_{i} \neq = f_{i}, 1 \leq t_{i} \leq 1 0^{6})$ t_i~(1 \le s_i, f_i \le n, s_i \ne f_i, 1 \le t_i \le 10^6). Це означає, що авіакомпанія повинна забезпечити рейс з аеропорту $s_{i}$ s_i до аеропорту $f_{i}$ f_i з точним часом вильоту $t_{i}$ t_i.

Вихідні дані

Виведіть мінімальну кількість літаків, необхідну авіакомпанії для виконання всіх $m$ заданих рейсів.

Приклади

Приклад 1

Приклад 2

Приклад 3