In the JSOI kingdom, there are $N$ airports, numbered from $1$ to $N$. The flight time from airport $i$ to airport $j$ is $T_{i,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 an aircraft lands, it requires routine maintenance and refueling. When an aircraft lands at airport $k$, it requires $P_k$ units of maintenance time before it can take off again.

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

To simplify the problem, we assume that JS Airways can deploy any number of fully maintained aircraft at any airport at time $0$. To minimize the number of aircraft used, we allow JS Airways to add any number of temporary routes to satisfy scheduling requirements.

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

Input

The input contains: The first line contains two positive integers $N$ and $M$. The second line contains $N$ positive integers representing the maintenance time for each airport. The next $N$ lines each contain $N$ non-negative integers, where the $j$-th integer in the $i$-th line is $T_{i,j}$, the time required to fly from airport $i$ to airport $j$. It is guaranteed that $T_{i,i} = 0$. The next $M$ lines each contain 3 positive integers, where the $i$-th line contains $X_i, Y_i, D_i$, representing the departure airport, arrival airport, and departure time of the $i$-th route. It is guaranteed that $X_i \neq Y_i$.

Output

Output a single positive integer representing the theoretical minimum number of aircraft required by JS Airways.

Examples

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

Output 1

2

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

Output 2

3

Note

In the first example, JS Airways can deploy an aircraft at airport $2$ at time $0$ to fly the $2$-nd route ($2 \to 1$). Additionally, it needs to deploy an aircraft at airport $1$ at time $0$. This aircraft first flies the $1$-st route ($1 \to 2$), then takes a newly added temporary route from airport $2$ to airport $3$, and after landing at airport $3$, flies the $3$-rd route ($3 \to 1$).

In the second example, the aircraft that completes the $1$-st route cannot arrive in time for the departure of the $3$-rd route, so JS Airways must use $3$ different aircraft to complete all flights.

Constraints

• For $30\%$ of the data: $N, M \le 10$.
• For $60\%$ of the data: $N, M \le 100$.
• For $100\%$ of the data: $1 \le N, M \le 500$, $0 \le P_i, T_{i,j} \le 10^6$, $1 \le D_i \le 10^6$.