{"problem":{"name":"E. Mike and Cities","description":{"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 vis","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10160E"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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).\n\n## Output\n\nOutput the maximal sum of pleasures he can achieve.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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' $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10160E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}