Airports
An airline company offers flights out of n airports, conveniently labeled from 1 to n. The flighttime t[ij] from airport i to airport j is known for every i and j. It may be the case that t[ij] ≠ t[ji], due to things like wind or geography. Upon landing at a given airport, a plane must be inspected before it can be own again. This inspection time p[i] is dependent only on the airport at which the inspection is taking place and not where the previous flight may have originated.
Given a set of m flights that the airline company must provide, determine the minimum number of planes that the company needs to purchase. The airline may add unscheduled flights to move the airplanes around if that would reduce the total number of planes needed.
Input
The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 500). The next line contains n space-separated integers p[1], ..., p[n] (0 ≤ p[i] ≤ 10^6).
Each of the next n lines contains n space-separated integers. The j-th integer in line i + 2 is t[ij] (0 ≤ t[ij] ≤ 10^6). It is guaranteed that t[ii] = 0 for all i. However, it may be the case that t[ij] ≠ t[ji] when i ≠ j.
Each of the next m lines contains three space-separated integers s[i], f[i] and t[i] (1 ≤ s[i], f[i] ≤ n, s[i] ≠ f[i], 1 ≤ t[i] ≤ 10^6), indicating that the airline company must provide a flight that flies out from airport s[i] at exactly time t[i], heading directly to airport f[i].
Output
Print, on a single line, a single integer indicating the minimum number of planes the airline company must purchase in order to provide the m requested flights.