Minimum Number of Airplanes

In the JSOI Kingdom there are \(N\) airports numbered from \(1\) to \(N\). The time to fly from airport \(i\) to airport \(j\) is given by \(T_{i,j}\). Note that due to factors such as wind, geography and air control, \(T_{i,j}\) may not be equal to \(T_{j,i}\).

When a plane lands at airport \(k\), it needs \(P_k\) time for maintenance (inspection and refuelling) before it can take off again.

JS Airways operates a total of \(M\) scheduled flights. The \(i\)th scheduled flight departs at time \(D_i\) from airport \(X_i\) and flies directly to airport \(Y_i\). To simplify the problem, we assume that at time \(0\) an arbitrarily large number of fully serviced planes can be placed at any airport. Furthermore, to minimize the number of planes used, JS Airways is allowed to add arbitrarily many temporary repositioning flights if needed.

Your task is to determine the minimum number of airplanes required to complete all \(M\) scheduled flights.

A plane that completes a flight from \(X_i\) to \(Y_i\) departing at time \(D_i\) will land at time \(D_i + T_{X_i, Y_i}\) and then it will be ready for a subsequent flight from airport \(Y_i\) only after time \(D_i + T_{X_i, Y_i} + P_{Y_i}\). Additionally, a plane can take a repositioning flight from airport \(a\) to airport \(b\) taking time \(T_{a,b}\).

Thus, if a plane finishes flight \(i\) (departing from \(X_i\) and arriving at \(Y_i\)) at time \(D_i + T_{X_i, Y_i} + P_{Y_i}\), then it can be used for another flight \(j\) (departing from \(X_j\) at time \(D_j\)) if

[ D_i + T_{X_i, Y_i} + P_{Y_i} + T_{Y_i, X_j} \le D_j. ]

Find the minimum number of airplanes needed to cover all the \(M\) scheduled flights.

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of airports and the number of scheduled flights, respectively.

The next \(N\) lines each contain \(N\) integers. The \(j\)th integer of the \(i\)th line represents \(T_{i,j}\), the time required to fly from airport \(i\) to airport \(j\).

The following line contains \(N\) integers \(P_1, P_2, \dots, P_N\), where \(P_k\) is the maintenance time at airport \(k\) after landing.

Then \(M\) lines follow. The \(i\)th of these lines contains three integers \(D_i\), \(X_i\), and \(Y_i\), indicating that the \(i\)th scheduled flight departs at time \(D_i\) from airport \(X_i\) and arrives at airport \(Y_i\).

outputFormat

Output a single integer representing the minimum number of airplanes required to complete all scheduled flights.

sample

2 2
0 1
2 0
1 2
1 1 2
5 2 1

1