题目描述

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 Airways 可以在 $0$ 时刻在任意机场布置任意多架维护完毕的飞机，并且可以增开任意多条临时航线以满足飞机调度需求。

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

输入格式

• 第一行包含两个正整数 $N, M$；
• 第二行包含 $N$ 个正整数，表示每个机场的飞机维护时间 $P_1, P_2, \dots, P_N$；
• 接下来 $N$ 行，每行 $N$ 个非负整数，其中第 $i$ 行第 $j$ 个数为 $T_{i,j}$，表示从 $i$ 号机场飞往 $j$ 号机场所需时间。数据保证 $T_{i,i} = 0$；
• 接下来 $M$ 行，每行三个正整数 $X_i, Y_i, D_i$，表示第 $i$ 条航线的起飞机场、降落机场和起飞时间。数据保证 $X_i \ne Y_i$。

输出格式

一行一个正整数，表示最少需要的飞机数。

样例 1

输入

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

输出

2

解释
可以在 $0$ 时刻在 $2$ 号机场安排一架飞机执飞第 $2$ 条航线（$2 \to 1$）。
在 $1$ 号机场安排另一架飞机执飞第 $1$ 条航线（$1 \to 2$），然后通过临时航线从 $2$ 号机场飞往 $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

输出

3

解释
执行完第 $1$ 条航线的飞机无法赶上第 $3$ 条航线的起飞时间，因此需要 $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$。