Problem Description

In the Kingdom of JSOI, there are $N$ airports numbered from $1$ to $N$. It takes $T_{i,j}$ time to fly from airport $i$ to airport $j$. Due to wind direction, geographical location, and air traffic control factors, $T_{i,j}$ and $T_{j,i}$ are not necessarily the same.

Additionally, after landing, an aircraft requires routine maintenance and refueling. When an aircraft lands at airport $k$, it needs $P_k$ maintenance time before it can take off again.

JS Airways operates $M$ direct flight routes, where the $i$-th route requires a flight to depart from airport $X_i$ at time $D_i$ and fly directly to airport $Y_i$ without stopping.

To simplify the problem, we assume that JS Airways can deploy any number of fully serviced aircraft at any airport at time $0$; to reduce the number of aircraft used, we allow JS Airways to add any number of temporary routes to meet the scheduling needs of the aircraft.

JYY wants to know the theoretical minimum number of aircraft required for JS Airways to complete all $M$ flights.

Input Format

The first line contains two positive integers $N$ and $M$.

The next line contains $N$ positive integers representing the maintenance time for each airport.

The following $N$ lines, each containing $N$ non-negative integers, where the $j$-th non-negative integer in the $i$-th line is $T_{i,j}$, indicating the time required to fly from airport $i$ to airport $j$. It is guaranteed that $T_{i,i}=0$.

The next $M$ lines, each containing three positive integers, where the $i$-th line is $X_i, Y_i, D_i$, indicating the departure airport, arrival airport, and departure time of the $i$-th route. It is guaranteed that $X_i \neq Y_i$.

Output Format

A single line containing a positive integer, representing the theoretical minimum number of aircraft required for JS Airways.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2

Sample Input #2

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

Sample Output #2

3

Notes

Sample Explanation 1

In the first sample, JS Airways can arrange an aircraft at airport $2$ at time $0$ and fly the second route ($2→1$). Additionally, an aircraft needs to be arranged at airport $1$ at time $0$, which will first fly the first route ($1→2$), then add a temporary route from airport $2$ to airport $3$, and finally fly the third route ($3→1$) after landing at airport $3$.

Sample Explanation 2

In the second sample, the aircraft that completes the first route cannot make it in time for the third route, so JS Airways must use 3 different aircraft to complete all flights.

Data Range

For $30\%$ of the data, $N, M \le 10$.

For $60\%$ of the data, $N, M \le 100$.

For all data, $1 \le N, M \le 500$, $0 \le P_i, T_{i,j} \le 10^6$, $1 \le D_i \le 10^6$.

见题面 Input 部分

见题面 Output 部分