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 c1 then on the day d + 1 he can visit city c1 (stay where he's for one more day) or city c2 if there is a road between cities c1 and c2.
He can visit a city any number of times. There are k types of roads, each type is described using 3 integers ai, bi and ci, signifying that there are bidirectional roads between cities (ai and ci), (ai + 1 and ci) ... (bi and ci) note that there can be a road between a city and itself, it is also given the fact that ci ≠ cj (1 ≤ i < j ≤ k).
In day i (1 ≤ i ≤ m), if he visits city j (1 ≤ j ≤ n) he gets pleasure Pi, 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 ≤ Pi, j ≤ 109).
The next k lines, each one contains 3 integers separated by a space, representing the different types of roads – ai, bi, ci (1 ≤ ai ≤ bi ≤ n, 1 ≤ ci ≤ n).
Output the maximal sum of pleasures he can achieve.
## Input
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 ≤ Pi, j ≤ 109).The next k lines, each one contains 3 integers separated by a space, representing the different types of roads – ai, bi, ci (1 ≤ ai ≤ bi ≤ n, 1 ≤ ci ≤ n).
## Output
Output the maximal sum of pleasures he can achieve.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ r, c \in \mathbb{Z} $ denote grid dimensions ($3 \leq r, c \leq 500$).
- Let $ q \in \mathbb{Z} $ denote the number of original instructions ($1 \leq q \leq 1000$).
- Let $ (s_r, s_c) \in \{2, \dots, r-1\} \times \{2, \dots, c-1\} $ be the starting position (free cell).
- Let $ d_0 \in \{\text{U}, \text{D}, \text{L}, \text{R}\} $ be the initial direction.
- Let $ G \in \{\text{.}, \#\}^{r \times c} $ be the grid, with border cells all blocked and all free cells having at least one adjacent free cell.
- Let $ I = (i_1, i_2, \dots, i_q) $ be the sequence of original instructions, each $ i_j \in \{ \text{F } n \mid n \in \mathbb{Z}^+ \} \cup \{ \text{L}, \text{R} \} $.
Let $ P_k = (p_{k,0}, p_{k,1}, \dots, p_{k,m_k}) $ be the sequence of visited cells (including start), where $ p_{k,0} = (s_r, s_c) $, and each $ p_{k,\ell} $ is determined by executing $ I $ step-by-step on $ G $ with initial direction $ d_0 $.
**Constraints**
1. $ 1 \leq T \leq 128 $
2. $ 3 \leq r, c \leq 500 $, $ 1 \leq q \leq 1000 $
3. All border cells in $ G $ are blocked.
4. Each free cell has at least one adjacent free cell.
5. Robot only moves to free cells; blocked cells are impassable.
6. Instructions are executed sequentially; movement stops at blocked cell (but no instruction is skipped).
**Objective**
Find the minimum number of instructions $ q' $ in a new sequence $ I' $ such that:
- The robot starts at $ (s_r, s_c) $ with direction $ d_0 $.
- The sequence of visited cells under $ I' $ is identical to $ P_k $.
- $ I' $ consists only of instructions of the form $ \text{F } n $ ($ n \geq 1 $) or $ \text{L}, \text{R} $.
- The robot must follow the same path (same cell sequence, same order) as under $ I $.
Minimize $ q' $.