404420: GYM101502 L Roads and Tracks

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 a_ij.

You can move between tracks at the same position. If you are at position i, it will take b_ij 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 j^th integer in the i^th line is the cost of passing through the road from position i to position i + 1 at track j (0 ≤ a_ij ≤ 10⁹).

Then n lines follow, each line contains m - 1 integers, where the j^th integer in the i^th line is the number of required seconds to switch between tracks j and j + 1 at position i (0 ≤ b_ij ≤ 10⁹)

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.

1
5 3
1 1 1
2 2 2
2 1 3
1 7 1
2 1 2
2 1
1 3
1 2
1 8
2 1

6 4

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.