404653: GYM101604 E Mike and Cities

Mike has a vacation of m days, and he's going to explore n cities numbered from 1 to n. He can start to visit on the first day any city. If on day d he visited city c₁ then on the day d + 1 he can visit city c₁ (stay where he's for one more day) or city c₂ if there is a road between cities c₁ and c₂.

He can visit a city any number of times. There are k types of roads, each type is described using 3 integers a_i,  b_i and c_i, signifying that there are bidirectional roads between cities (a_i and c_i),  (a_i + 1 and c_i) ...  (b_i and c_i) note that there can be a road between a city and itself, it is also given the fact that c_i ≠ c_j (1 ≤ i < j ≤ k).

In day i (1 ≤ i ≤ m), if he visits city j (1 ≤ j ≤ n) he gets pleasure P_i, j.

Help him find the maximal sum of pleasure in all the days he can achieve.

The first line contains 3 integers n,  m and k (1 ≤ n × m,  k ≤ 300, 000).

The next m lines contains n integers separated by a space, representing matrix P (0 ≤ P_i, j ≤ 10⁹).

The next k lines, each one contains 3 integers separated by a space, representing the different types of roads – a_i,  b_i,  c_i (1 ≤ a_i ≤ b_i ≤ n,  1 ≤ c_i ≤ n).

Output the maximal sum of pleasures he can achieve.

3 3 2
1 2 3
5 6 7
11 5 3
1 1 2
2 3 3

20