eolymp
bolt
Try our new interface for solving problems
Məsələlər

Аэропорты

Аэропорты

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Авиакомпания предлагает авиабилеты из n аэропортов, пронумерованных от 1 до n. Время полета t[ij] из аэропорта i в аэропорт j известно для всех пар i и j. Возможно t[ij]t[ji] из-за ветра или географического расположения. При посадке в аэропорту самолет должен быть осмотрен, прежде чем он сможет снова взлететь. Время осмотра составляет p[i] и зависит только от аэропорта, в котором проводится инспекция.

Имея набор из m предоставляемых рейсов, определите минимальное количество самолетов, которое должна купить авиакомпания. Авиакомпания может добавлять внеплановые рейсы для перемещения самолетов, если это уменьшит общее количество необходимых самолетов.

Giriş verilənləri

Первая строка содержит числа n и m (1n, m500). Следующая строка содержит n целых чисел p[1], ..., p[n] (0p[i]10^6).

Каждая из следующих n строк содержит n целых чисел. j-ое число в строке i + 2 равно t[ij] (0t[ij]10^6). Гарантируется, что t[ii] = 0 для всех i. Однако может иметь место t[ij]t[ji] при ij.

Каждая из следующих m строк содержит три целых числа s[i], f[i] и t[i] (1s[i], f[i]n, s[i]f[i], 1t[i]10^6), указывающих на то что авиакомпания должна обеспечить полет из аэропорта s[i] с точным временем вылета t[i], следуя в точности в аэропорт f[i].

Çıxış verilənləri

Выведите минимальное количество самолетов, которые должна приобрести авиакомпания, для обеспечения m требуемых рейсов.

Nümunə

Giriş verilənləri #1
2 2
1 1
0 1
1 0
1 2 1
2 1 1
Çıxış verilənləri #1
2
Giriş verilənləri #2
2 2
1 1
0 1
1 0
1 2 1
2 1 3
Çıxış verilənləri #2
1
Giriş verilənləri #3
5 5
72 54 71 94 23
0 443 912 226 714
18 0 776 347 810
707 60 0 48 923
933 373 881 0 329
39 511 151 364 0
4 2 174
2 1 583
4 3 151
1 4 841
4 3 993
Çıxış verilənləri #3
3
Mənbə 2015 ACM North America - Pacific Northwest, Дивизион 1, Задача A