Авиакомпания предлагает авиабилеты из 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 требуемых рейсов.