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. finish at position n + 1) and ending at any track.
If you are at position i and track number j, the cost to move *forward* to position i + 1 and track j is aij.
You 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.
Your 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.
The 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)
For 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.
As 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.
## Input
The 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)
## Output
For 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.
[samples]
## Note
As 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.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n \in \mathbb{Z} $ be the road length, $ m \in \mathbb{Z} $ the number of tracks.
- 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 $.
- 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 $.
**Constraints**
1. $ 1 \leq T \leq \text{unknown} $ (not bounded in input description)
2. $ 1 \leq n \leq 25000 $, $ 2 \leq m \leq 25 $
3. $ 0 \leq a_{i,j} \leq 10^9 $ for all $ i \in \{1,\dots,n\}, j \in \{1,\dots,m\} $
4. $ 0 \leq b_{i,j} \leq 10^9 $ for all $ i \in \{1,\dots,n\}, j \in \{1,\dots,m-1\} $
**Objective**
Find the minimum total cost $ x $ and, among all paths achieving cost $ x $, the minimum total time $ y $ to traverse the road:
- Start at position $ 1 $, track $ 1 $.
- End at position $ n+1 $, any track.
- At each position $ i \in \{1,\dots,n\} $, you may:
- Move forward to position $ i+1 $ on the same track $ j $, costing $ a_{i,j} $.
- Switch between adjacent tracks $ j $ and $ j+1 $ at position $ i $, costing $ b_{i,j} $ (bidirectional).
Let $ 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 $.
Initialize:
$ dp[1][1] = (0, 0) $, and $ dp[1][j] = (\infty, \infty) $ for $ j \ne 1 $.
For each position $ i \in \{1, \dots, n\} $:
1. **Track switching**: For each $ j \in \{1, \dots, m-1\} $, update:
$$
dp[i][j+1] \leftarrow \min_{\text{lex}} \left( dp[i][j+1],\ dp[i][j] + (b_{i,j}, b_{i,j}) \right)
$$
$$
dp[i][j] \leftarrow \min_{\text{lex}} \left( dp[i][j],\ dp[i][j+1] + (b_{i,j}, b_{i,j}) \right)
$$
(propagate switches within position $ i $ until stable)
2. **Forward move**: For each $ j \in \{1, \dots, m\} $:
$$
dp[i+1][j] \leftarrow \min_{\text{lex}} \left( dp[i+1][j],\ dp[i][j] + (a_{i,j}, a_{i,j}) \right)
$$
Output:
$ \min_{\text{lex}} \{ dp[n+1][j] \mid j \in \{1,\dots,m\} \} = (x, y) $
(Note: Lexicographic minimization: minimize cost first, then time.)