공항

어떤 항공사가 1번부터 n번까지 번호가 붙은 공항 n개에서 항공편을 운항한다. 공항 i에서 공항 j로 가는 비행 시간은 $t_{ij}$이고, 바람과 지형 때문에 $t_{ij}$와 $t_{ji}$가 다를 수 있다.

비행기는 공항 i에 착륙하면 $p_i$만큼 점검을 받아야 다시 이륙할 수 있다. 점검 시간은 착륙한 공항에만 달려 있고 그 비행기가 어디에서 왔는지와는 무관하다. 기체를 옮기려고 항공사가 임의로 추가한 비행으로 착륙했을 때도 점검을 똑같이 받는다.

항공사는 정규편 m개를 모두 운항해야 한다. $k$번째 정규편은 정확히 시각 $t_k$에 공항 $s_k$를 출발해 공항 $f_k$로 곧장 간다. 기체를 옮기는 비행은 정규편 외에 얼마든지 추가할 수 있고, 한 기체가 그런 비행을 여러 번 연달아 해도 된다.

정규편 $a$를 운항한 기체가 이어서 정규편 $b$를 운항하려면 시각 $t_b$까지 공항 $s_b$에 돌아와 점검을 마쳐야 한다. 출발 시각이 같은 정규편 두 개를 한 기체가 모두 운항할 수는 없다.

정확히 적으면 이렇다. 정규편 $a$를 마친 기체가 다시 이륙할 수 있게 되는 시각은 $A_a = t_a + t_{s_a f_a} + p_{f_a}$이다. 공항 $x$에서 공항 $y$로 기체를 옮기는 데 드는 최소 시간을 $d_{xy}$라 하자. $d_{xy}$는 거쳐 가는 경로의 비행 시간과 착륙하는 공항마다의 점검 시간을 모두 더한 값 중 가장 작은 값이고, $d_{xx} = 0$이다. 한 기체가 $a$ 다음에 $b$를 운항할 수 있는 조건은 $t_a < t_b$이면서 $A_a + d_{f_a s_b} \le t_b$인 것이다.

정규편 m개를 모두 운항하려면 비행기가 최소 몇 대 필요한지 구하라.

첫째 줄에 정수 $n$과 $m$이 공백으로 구분되어 주어진다. ($1 \le n, m \le 500$)

둘째 줄에 정수 $p_1, \dots, p_n$이 공백으로 구분되어 주어진다. ($0 \le p_i \le 10^6$)

다음 $n$개 줄에는 각각 정수 $n$개가 공백으로 구분되어 주어진다. $i$번째 줄의 $j$번째 정수가 $t_{ij}$이다. ($0 \le t_{ij} \le 10^6$) 모든 $i$에 대해 $t_{ii} = 0$이지만, $i \ne j$일 때 $t_{ij}$와 $t_{ji}$는 다를 수 있다.

다음 $m$개 줄에는 각각 정수 세 개 $s_i$, $f_i$, $t_i$가 공백으로 구분되어 주어진다. ($1 \le s_i, f_i \le n$, $s_i \ne f_i$, $1 \le t_i \le 10^6$) 시각 $t_i$에 공항 $s_i$를 출발해 공항 $f_i$로 곧장 가는 정규편을 항공사가 운항해야 한다는 뜻이다.

정규편 $m$개를 모두 운항하는 데 필요한 비행기의 최소 대수를 한 줄에 출력한다.