시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 40 9 8 20.513%

문제

An airline company offers flights out of n airports, conveniently labeled from 1 to n. The flight time tij from airport i to airport j is known for every i and j. It may be the case that tij ≠ tji, due to things like wind or geography. Upon landing at a given airport, a plane must be inspected before it can be flown again. This inspection time pi 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.

입력

The first line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 500). The next line contains n space-separated integers p1, . . . , pn (0 ≤ pi ≤ 106).

Each of the next n lines contains n space-separated integers. The jth integer in line i + 2 is tij (0 ≤ tij ≤ 106). It is guaranteed that tii = 0 for all i. However, it may be the case that tij ≠ tji when i ≠ j.

Each of the next m lines contains three space-separated integers, si, fi, and ti (1 ≤ si, fi ≤ n, si ≠ fi, 1 ≤ ti ≤ 106), indicating that the airline company must provide a flight that flies out from airport si at exactly time ti , heading directly to airport fi.

출력

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.

예제 입력

2 2
1 1
0 1
1 0
1 2 1
2 1 1

예제 출력

2

예제 입력 2

2 2
1 1
0 1
1 0
1 2 1
2 1 3

예제 출력 2

1

예제 입력 3

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

예제 출력 3

3

힌트