4853 - [Jsoi2016]飞机调度
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 \neq 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
输入
3 3 100 1 1 0 1 1 1 0 5 2 1 0 1 2 1 2 1 1 3 1 8
输出
3
提示
样例说明1
在第一个样例中，JS Airways 可以在 0 时刻在 2 号机场安排一架飞机并执飞第 2 条航线（2→1）。此外还需要在 0 时刻在 1 号机场安排一架飞机，这架飞机首先执飞第 1 条航线（1→2），然后通过临时新增一条航线从 2 号机场起飞飞往 33 号机场，降落 3 号机场之后执飞第 3 条航线（3→1）。
样例说明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。