4106: 「JSOI2016」飞机调度
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
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 理论上最少需要的飞机数。
样例输入 复制
3 3
100 1 1
0 1 1
1 0 5
2 1 0
1 2 1
2 1 1
3 1 9样例输出 复制
2提示
输入样例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
数据范围：对于 $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$。