作为一个旅行达人以及航空公司的金卡会员，JYY 每一年的飞行里程可以 绕赤道几周了。JYY 发现，航空公司为了提高飞机的使用率，并不是简单的一条 航线使用一架飞机来回飞，而是会让同一架飞机连续不停的飞不同的航线，甚至 有的时候为了能够完成飞机的调度，航空公司还会增开一些临时航线——在飞机 转场的同时顺路捎一些乘客。JYY 研究了一下 JSOI 著名航空公司 JS Airways 的 常规直飞航线，他想计算一下，在最佳调度方案下，JS Airway 最少需要多少架 飞机才能成功执飞这所有的航线。
JSOI 王国里有 N 个机场，编号为 1 到 N。从 i 号机场到 j 号机场需要飞行Ti,j的时间。由于风向，地理位置和航空管制的因素，Ti,j 和 Tj,i并不一定相同。
此外，由于飞机降落之后需要例行维修和加油。当一架飞机降落 k 号机场时， 需要花费Pk的维护时间才能再次起飞。
JS Airways 一共运营 M 条航线，其中第 i 条直飞航线需要在Di时刻从Xi机场起飞，不经停，飞往Yi机场。
为了简化问题，我们假设 JS Airway 可以在 0 时刻在任意机场布置任意多架加油维护完毕的飞机；为了减少飞机的使用数，我们允许 JS Airways 增开任意多条临时航线以满足飞机的调度需求。
JYY 想知道，理论上 JS Airways 最少需要多少架飞机才能完成所有这 M 个 航班。
输入描述:
输入一行包含两个正整数 N 和 M。
接下来一行包含 N 个正整数表示每一个机场的飞机维护时间。
接下来 N 行，每行 N 个非负整数，其中第 i 行第 j 个非负整数为Ti,j，表示 从 i 号机场飞往 j 号机场所需要花费的时间。数据保证Ti,i= 0。
接下来 M 行，每行 3 个正整数，其中第 i 行为Di"，表示第 i 条航线的 起飞机场，降落机场，以及起飞时间。数据保证Xi ≠Yi, 。
输出描述:
输出文件包含一行一个正整数，表示 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
说明
在第一个样例中，JS Airways 可以在 0 时刻在 2 号机场安排一架飞机并执飞
第 2 条航线（2→1）。此外还需要在 0 时刻在 1 号机场安排一架飞机，这架飞机
首先执飞第 1 条航线（1→2），然后通过临时新增一条航线从 2 号机场起飞飞往
3 号机场，降落 3 号机场之后执飞第 3 条航线（3→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
说明
在第二个样例中，执行完第 1 条航线的飞机无法赶上第 3 条航线的起飞时
间，因此 JS Airways 必须使用 3 架不同的飞机才能完成所有的航班。
备注:
对于 30%的数据满足N,M ≤ 10；
对于 60%的数据满足N,M ≤ 100；
对于 100%的数据满足1 ≤ N,M≤ 500, 0 ≤ Pi,Ti,j ≤ 106, 1 ≤ Di ≤ 106。