{"raw_statement":[{"iden":"statement","content":"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.\n\nHe 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).\n\nIn day i (1 ≤ i ≤ m), if he visits city j (1 ≤ j ≤ n) he gets pleasure Pi, j.\n\nHelp him find the maximal sum of pleasure in all the days he can achieve.\n\nThe first line contains 3 integers n,  m and k (1 ≤ n × m,  k ≤ 300, 000).\n\nThe next m lines contains n integers separated by a space, representing matrix P (0 ≤ Pi, j ≤ 109).\n\nThe 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).\n\nOutput the maximal sum of pleasures he can achieve.\n\n"},{"iden":"input","content":"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)."},{"iden":"output","content":"Output the maximal sum of pleasures he can achieve."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ r, c \\in \\mathbb{Z} $ denote grid dimensions ($3 \\leq r, c \\leq 500$).  \n- Let $ q \\in \\mathbb{Z} $ denote the number of original instructions ($1 \\leq q \\leq 1000$).  \n- Let $ (s_r, s_c) \\in \\{2, \\dots, r-1\\} \\times \\{2, \\dots, c-1\\} $ be the starting position (free cell).  \n- Let $ d_0 \\in \\{\\text{U}, \\text{D}, \\text{L}, \\text{R}\\} $ be the initial direction.  \n- 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.  \n- 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} \\} $.  \n\nLet $ 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 $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 128 $  \n2. $ 3 \\leq r, c \\leq 500 $, $ 1 \\leq q \\leq 1000 $  \n3. All border cells in $ G $ are blocked.  \n4. Each free cell has at least one adjacent free cell.  \n5. Robot only moves to free cells; blocked cells are impassable.  \n6. Instructions are executed sequentially; movement stops at blocked cell (but no instruction is skipped).  \n\n**Objective**  \nFind the minimum number of instructions $ q' $ in a new sequence $ I' $ such that:  \n- The robot starts at $ (s_r, s_c) $ with direction $ d_0 $.  \n- The sequence of visited cells under $ I' $ is identical to $ P_k $.  \n- $ I' $ consists only of instructions of the form $ \\text{F } n $ ($ n \\geq 1 $) or $ \\text{L}, \\text{R} $.  \n- The robot must follow the same path (same cell sequence, same order) as under $ I $.  \n\nMinimize $ q' $.","simple_statement":"You have a robot on an r×c grid that moves in 4 directions (U, D, L, R). It starts at a given position and direction. The grid has free cells ('.') and blocked cells ('#'), with borders always blocked. The robot follows a list of instructions: either \"F n\" (move forward n steps) or \"R\" (turn right 90°).  \n\nYou want to rewrite the instruction list to be as short as possible, while making the robot visit the exact same cells in the exact same order. You cannot change the start position or direction.  \n\nFind the minimum number of instructions needed.","has_page_source":false}