Description

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

Also, after an aircraft lands, it needs routine maintenance and refueling. When an aircraft lands at airport $k$, it must spend $P_k$ time on maintenance before it can take off again.

JS Airways operates a total of $M$ routes. For the $i$-th direct flight, it must take off from airport $X_i$ at time $D_i$ and fly non-stop to airport $Y_i$.

To simplify the problem, we assume JS Airways can place any number of fully maintained and refueled aircraft at any airport at time $0$. To reduce the number of aircraft used, we also allow JS Airways to add any number of temporary flights to satisfy scheduling needs.

JYY wants to know: in theory, what is the minimum number of aircraft JS Airways needs to complete all these $M$ flights.

Input Format

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

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

The next $N$ lines each contain $N$ non-negative integers. The $j$-th non-negative integer in the $i$-th line is $T_{i,j}$, meaning the time required to fly from airport $i$ to airport $j$. The data guarantees $T_{i,i} = 0$.

The next $M$ lines each contain three positive integers. The $i$-th line is $X_i, Y_i, D_i$, representing the departure airport, the arrival airport, and the departure time of the $i$-th route. The data guarantees $X_i \neq Y_i$.

Output Format

Output one positive integer in a single line, representing the theoretical minimum number of aircraft JS Airways needs.

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

Hint

Sample Explanation 1

In the first sample, JS Airways can arrange one aircraft at airport $2$ at time $0$ and use it to operate flight $2$ ($2 \to 1$). In addition, it needs to arrange one aircraft at airport $1$ at time $0$. This aircraft first operates flight $1$ ($1 \to 2$), then takes a newly added temporary flight from airport $2$ to airport $3$, and after landing at airport $3$, it operates flight $3$ ($3 \to 1$).

Sample Explanation 2

In the second sample, the aircraft that finishes flight $1$ cannot catch the departure time of flight $3$. Therefore, JS Airways must use $3$ different aircraft to complete all flights.

Constraints

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

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

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

Translated by ChatGPT 5