{"problem":{"name":"L. Roads and Tracks","description":{"content":"You are given a road of length n, that has m parallel tracks numbered from 1 to m. You will start moving from the beginning of the road, and at track number 1. You want to pass the whole road (i.e. f","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10150L"},"statements":[{"statement_type":"Markdown","content":"You are given a road of length n, that has m parallel tracks numbered from 1 to m.\n\nYou will start moving from the beginning of the road, and at track number 1. You want to pass the whole road (i.e. finish at position n + 1) and ending at any track.\n\nIf you are at position i and track number j, the cost to move *forward* to position i + 1 and track j is aij.\n\nYou can move between tracks at the same position. If you are at position i, it will take bij seconds to move from track j to j + 1 (or from track j + 1 to j). Note that moving between tracks does not change your position on the road.\n\nYour task is to find what is the minimum cost required to pass the whole road starting from the beginning of the road and at track 1, and ending at any track. If there are multiple solutions, choose the one with minimum time.\n\nThe first line contains an integer T, where T is the number of test cases.\n\nThe first line of each test case contains two integers n and m (1 ≤ n ≤ 25000) (2 ≤ m ≤ 25), where n is the length of the road, and m is the number of tracks.\n\nThen n lines follow, each line contains m integers, where the jth integer in the ith line is the cost of passing through the road from position i to position i + 1 at track j (0 ≤ aij ≤ 109). \n\nThen n lines follow, each line contains m - 1 integers, where the jth integer in the ith line is the number of required seconds to switch between tracks j and j + 1 at position i (0 ≤ bij ≤ 109)\n\nFor each test case, print a single line containing two space separated integers x and y, where x is the minimum cost required to pass the road, and y is the minimum possible time to pass the road with the minimum cost x.\n\nAs input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use _scanf/printf_ instead of _cin/cout_ in C++, prefer to use _BufferedReader/PrintWriter_ instead of _Scanner/System.out_ in Java.\n\n## Input\n\nThe first line contains an integer T, where T is the number of test cases.The first line of each test case contains two integers n and m (1 ≤ n ≤ 25000) (2 ≤ m ≤ 25), where n is the length of the road, and m is the number of tracks.Then n lines follow, each line contains m integers, where the jth integer in the ith line is the cost of passing through the road from position i to position i + 1 at track j (0 ≤ aij ≤ 109). Then n lines follow, each line contains m - 1 integers, where the jth integer in the ith line is the number of required seconds to switch between tracks j and j + 1 at position i (0 ≤ bij ≤ 109)\n\n## Output\n\nFor each test case, print a single line containing two space separated integers x and y, where x is the minimum cost required to pass the road, and y is the minimum possible time to pass the road with the minimum cost x.\n\n[samples]\n\n## Note\n\nAs input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use _scanf/printf_ instead of _cin/cout_ in C++, prefer to use _BufferedReader/PrintWriter_ instead of _Scanner/System.out_ in Java.","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:  \n- Let $ n \\in \\mathbb{Z} $ be the road length, $ m \\in \\mathbb{Z} $ the number of tracks.  \n- Let $ A = (a_{i,j}) \\in \\mathbb{Z}^{n \\times m} $, where $ a_{i,j} $ is the cost to move forward from position $ i $ to $ i+1 $ on track $ j $.  \n- Let $ B = (b_{i,j}) \\in \\mathbb{Z}^{n \\times (m-1)} $, where $ b_{i,j} $ is the cost to switch from track $ j $ to $ j+1 $ (or vice versa) at position $ i $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unknown} $ (not bounded in input description)  \n2. $ 1 \\leq n \\leq 25000 $, $ 2 \\leq m \\leq 25 $  \n3. $ 0 \\leq a_{i,j} \\leq 10^9 $ for all $ i \\in \\{1,\\dots,n\\}, j \\in \\{1,\\dots,m\\} $  \n4. $ 0 \\leq b_{i,j} \\leq 10^9 $ for all $ i \\in \\{1,\\dots,n\\}, j \\in \\{1,\\dots,m-1\\} $  \n\n**Objective**  \nFind the minimum total cost $ x $ and, among all paths achieving cost $ x $, the minimum total time $ y $ to traverse the road:  \n- Start at position $ 1 $, track $ 1 $.  \n- End at position $ n+1 $, any track.  \n- At each position $ i \\in \\{1,\\dots,n\\} $, you may:  \n  - Move forward to position $ i+1 $ on the same track $ j $, costing $ a_{i,j} $.  \n  - Switch between adjacent tracks $ j $ and $ j+1 $ at position $ i $, costing $ b_{i,j} $ (bidirectional).  \n\nLet $ dp[i][j] = (x_{i,j}, y_{i,j}) $ be the pair of minimum cost and minimum time to reach position $ i $ on track $ j $.  \n\nInitialize:  \n$ dp[1][1] = (0, 0) $, and $ dp[1][j] = (\\infty, \\infty) $ for $ j \\ne 1 $.  \n\nFor each position $ i \\in \\{1, \\dots, n\\} $:  \n1. **Track switching**: For each $ j \\in \\{1, \\dots, m-1\\} $, update:  \n   $$\n   dp[i][j+1] \\leftarrow \\min_{\\text{lex}} \\left( dp[i][j+1],\\ dp[i][j] + (b_{i,j}, b_{i,j}) \\right)\n   $$\n   $$\n   dp[i][j] \\leftarrow \\min_{\\text{lex}} \\left( dp[i][j],\\ dp[i][j+1] + (b_{i,j}, b_{i,j}) \\right)\n   $$\n   (propagate switches within position $ i $ until stable)  \n2. **Forward move**: For each $ j \\in \\{1, \\dots, m\\} $:  \n   $$\n   dp[i+1][j] \\leftarrow \\min_{\\text{lex}} \\left( dp[i+1][j],\\ dp[i][j] + (a_{i,j}, a_{i,j}) \\right)\n   $$\n\nOutput:  \n$ \\min_{\\text{lex}} \\{ dp[n+1][j] \\mid j \\in \\{1,\\dots,m\\} \\} = (x, y) $  \n\n(Note: Lexicographic minimization: minimize cost first, then time.)","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10150L","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}