Airports

Time limit3sMemory limit256 MB

Summary

Find the minimum number of planes needed to operate all scheduled flights when planes can take repositioning flights between them.

Level: Medium7 of 10
Topics: Graph, Shortest path
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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

Examples3

Example 1
Input
```
2 2
1 1
0 1
1 0
1 2 1
2 1 1
```
Expected output
```
2
```
Example 2
Input
```
2 2
1 1
0 1
1 0
1 2 1
2 1 3
```
Expected output
```
1
```

Example 3

Input

5 5
72 54 71 94 23
0 443 912 226 714
18 0 776 347 810
707 60 0 48 923
933 373 881 0 329
39 511 151 364 0
4 2 174
2 1 583
4 3 151
1 4 841
4 3 993

Expected output