Airports

An airline operates flights out of n airports numbered 1 to n. The flight time from airport i to airport j is $t_{ij}$, and $t_{ij}$ can differ from $t_{ji}$ because of wind and terrain.

When a plane lands at airport i, it must be inspected for $p_i$ before it can take off again. The inspection time depends only on the airport where the plane lands, not on where the plane came from. A plane that lands on an extra repositioning flight is inspected the same way.

The airline must operate all m scheduled flights. Scheduled flight $k$ leaves airport $s_k$ at exactly time $t_k$ and flies straight to airport $f_k$. The airline may add any number of repositioning flights to move planes around, and one plane may make several of them in a row.

A plane that operated scheduled flight $a$ can operate scheduled flight $b$ next only if it is back at airport $s_b$ with its inspection finished by time $t_b$. One plane cannot operate two scheduled flights that leave at the same time.

Stated exactly: the plane that finishes flight $a$ is ready to take off again at $A_a = t_a + t_{s_a f_a} + p_{f_a}$. Let $d_{xy}$ be the smallest time needed to move a plane from airport $x$ to airport $y$, which is the minimum, over all routes, of the flight times along the route plus the inspection time at every airport where the plane lands, with $d_{xx} = 0$. One plane can operate $b$ after $a$ exactly when $t_a < t_b$ and $A_a + d_{f_a s_b} \le t_b$.

Find the minimum number of planes needed to operate all m scheduled flights.

The first line contains two space separated integers $n$ and $m$. ($1 \le n, m \le 500$)

The second line contains $n$ space separated integers $p_1, \dots, p_n$. ($0 \le p_i \le 10^6$)

Each of the next $n$ lines contains $n$ space separated integers. The $j$th integer of the $i$th line is $t_{ij}$. ($0 \le t_{ij} \le 10^6$) It is guaranteed that $t_{ii} = 0$ for every $i$, but $t_{ij}$ and $t_{ji}$ can differ when $i \ne j$.

Each of the next $m$ lines contains three space separated integers $s_i$, $f_i$, and $t_i$. ($1 \le s_i, f_i \le n$, $s_i \ne f_i$, $1 \le t_i \le 10^6$) It means the airline must operate a scheduled flight that leaves airport $s_i$ at time $t_i$ and flies straight to airport $f_i$.

Print, on a single line, the minimum number of planes needed to operate all $m$ scheduled flights.