P5769 [JSOI2016] Aircraft Scheduling

In the JSOI Kingdom, there are $N$ airports, numbered from $1$ to $N$. Flying from airport $i$ to airport $j$ takes time $T_{i,j}$. Due to wind direction, geographic location, and air traffic control, $T_{i,j}$ and $T_{j,i}$ are not necessarily the same. Also, after an aircraft lands, it needs routine maintenance and refueling. When an aircraft lands at airport $k$, it must spend $P_k$ time on maintenance before it can take off again. JS Airways operates a total of $M$ routes. For the $i$-th direct flight, it must take off from airport $X_i$ at time $D_i$ and fly non-stop to airport $Y_i$. To simplify the problem, we assume JS Airways can place any number of fully maintained and refueled aircraft at any airport at time $0$. To reduce the number of aircraft used, we also allow JS Airways to add any number of temporary flights to satisfy scheduling needs. JYY wants to know: in theory, what is the minimum number of aircraft JS Airways needs to complete all these $M$ flights.

The first line contains two positive integers $N, M$. The next line contains $N$ positive integers, representing the aircraft maintenance time for each airport. The next $N$ lines each contain $N$ non-negative integers. The $j$-th non-negative integer in the $i$-th line is $T_{i,j}$, meaning the time required to fly from airport $i$ to airport $j$. The data guarantees $T_{i,i} = 0$. The next $M$ lines each contain three positive integers. The $i$-th line is $X_i, Y_i, D_i$, representing the departure airport, the arrival airport, and the departure time of the $i$-th route. The data guarantees $X_i \neq Y_i$.

Output one positive integer in a single line, representing the theoretical minimum number of aircraft JS Airways needs.

**Sample Explanation 1** In the first sample, JS Airways can arrange one aircraft at airport $2$ at time $0$ and use it to operate flight $2$ ($2 \to 1$). In addition, it needs to arrange one aircraft at airport $1$ at time $0$. This aircraft first operates flight $1$ ($1 \to 2$), then takes a newly added temporary flight from airport $2$ to airport $3$, and after landing at airport $3$, it operates flight $3$ ($3 \to 1$). **Sample Explanation 2** In the second sample, the aircraft that finishes flight $1$ cannot catch the departure time of flight $3$. Therefore, JS Airways must use $3$ different aircraft to complete all flights. ------------ **Constraints** For $30\%$ of the testdata, $N, M \le 10$. For $60\%$ of the testdata, $N, M \le 100$. For all testdata, $1 \le N, M \le 500$, $0 \le P_i, T_{i,j} \le 10^6$, $1 \le D_i \le 10^6$. Translated by ChatGPT 5