#2077. 「JSOI2016」飞机调度

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

JSOI 王国里有 N 个机场,编号为 1 N 。从 i 号机场到 j 号机场需要飞行 T_{i, j} 的时间。由于风向,地理位置和航空管制的因素, T_{i, j} T_{j, i} 并不一定相同。

此外,由于飞机降落之后需要例行维修和加油。当一架飞机降落 k 号机场时,需要花费 P_k ​​ 的维护时间才能再次起飞。

JS Airways 一共运营 M 条航线,其中第 i 条直飞航线需要在 D_i 时刻从 X_i 机场起飞,不经停,飞往 Y_i 机场。

为了简化问题,我们假设 JS Airway 可以在 0 时刻在任意机场布置任意多架加油维护完毕的飞机;为了减少飞机的使用数,我们允许 JS Airways 增开任意多条临时航线以满足飞机的调度需求。

JYY 想知道,理论上 JS Airways 最少需要多少架飞机才能完成所有这 M 个航班。

输入格式

第一行包含两个正整数 N,M
接下来一行包含 N 个正整数表示每一个机场的飞机维护时间;
接下来 N 行,每行 N 个非负整数,其中第 i 行第 j 个非负整数为 T_{i,j} ,表示从 i 号机场飞往 j 号机场所需要花费的时间。数据保证 T_{i,i}=0
接下来 M 行,每行三个正整数,其中第 i 行为 X_i,Y_i,D_i ,表示第 i 条航线的起飞机场,降落机场,以及起飞时间。数据保证 X_i\not =Y_i

输出格式

一行一个正整数,表示 JS Airways 理论上最少需要的飞机数。

样例

样例输入 1

3 3
100 1 1
0 1 1
1 0 5
2 1 0
1 2 1
2 1 1
3 1 9

样例输出 1

2

样例说明 1

在第一个样例中,JS Airways 可以在 0 时刻在 2 号机场安排一架飞机并执飞第 2 条航线( 2\to 1 )。此外还需要在 0 时刻在 1 号机场安排一架飞机,这架飞机首先执飞第 1 条航线( 1\to 2 ),然后通过临时新增一条航线从 2 号机场起飞飞往 3 号机场,降落 3 号机场之后执飞第 3 条航线( 3\to 1 )。

样例输入 2

3 3
100 1 1
0 1 1
1 0 5
2 1 0
1 2 1
2 1 1
3 1 8

样例输出 2

3

样例说明 2

在第二个样例中,执行完第 1 条航线的飞机无法赶上第 3 条航线的起飞时间,因此 JS Airways 必须使用 3 架不同的飞机才能完成所有的航班。

数据范围与提示

对于 30\% 的数据,满足 N,M\le 10
对于 60\% 的数据,满足 N,M\le 100
对于全部数据,满足 1\le N,M\le 500,0\le P_i,T_{i,j}\le 10^6,1\le D_i\le 10^6