Airports — Eolymp

Input

The first line contains two integers $n$ and $m (1 \leq n, m \leq 500)$ m~(1 \le n, m \le 500).

The second line contains $n$ integers $p_{1}, p_{2}, \dots, p_{n} (0 \leq p_{i} \leq 1 0^{6})$ p_1, p_2, \dots, p_n~(0 \le p_i \le 10^6).

The next $n$ lines each contain $n$ integers. The $j$ -th number in the $i$ -th line represents $t_{ij} (0 \leq t_{ij} \leq 1 0^{6})$ t_{ij}~(0 \le t_{ij} \le 10^6). It is guaranteed that $t_{ii} = 0$ t_{ii} = 0 for all $i$ . For $i \neq = j$ i \ne j, it is possible that $t_{ij} \neq = t_{j i}$ t_{ij} \ne t_{ji}.

The following $m$ lines each contain three integers $s_{i}, f_{i}$ s_i, f_i and $t_{i} (1 \leq s_{i}, f_{i} \leq n, s_{i} \neq = f_{i}, 1 \leq t_{i} \leq 1 0^{6})$ t_i~(1 \le s_i, f_i \le n, s_i \ne f_i, 1 \le t_i \le 10^6). This means that the airline must operate a flight from airport $s_{i}$ s_i to airport $f_{i}$ f_i with an exact departure time $t_{i}$ t_i.

Output

Output the minimum number of aircraft required for the airline to perform all $m$ given flights.

Esempi

Esempio 1

Loading

Esempio 2

Loading

Esempio 3

Loading