|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||0||0||0||0.000%|
In Lala land, young Lumbo and his older brother Jumbo used to play a game that they loved so much. Initially, the game was as follows. Jumbo chooses a number N, then he draws a 3 × N grid on the floor marking some cells as important. The grid cells are referenced by a pair (i, j), where i is the row number, such that the uppermost row has number 1, and j is the column number, such that the leftmost column has number 1. The grid has 3 rows and N columns. Afterwards, Jumbo asks Lumbo to try his best jumping with one leg on the grid cells such that he follows the following rules:
One day, Jumbo thought that the game is too easy that anyone, son of yesterday in his own words, can easily finish the game, so he decided to add new rules to it. So, in addition to the previous rules stated, Jumbo added the following rule:
Then, as before, he asked Lumbo to jump with one leg on the grid cells such that he visits each important cell at least once, but this time he should minimize the overall cost he has to pay.
Lumbo tried some jumps but he is not sure whether any of them has the minimum cost. Lumbo feels that it is too hard for him to do this, so he asked you to help him compute the minimum cost. Can you help him win over his brother and prove that he is son of today?
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100)
Each test case starts with a line containing two integers:
The next 3 lines will each contain N −1 space separated integers describing the costs of the vertical separating edges. So, the first line describes the costs of the vertical edges separating the cells of the first row ((1, 1),(1, 2), . . . ,(1, N)), and similarly for the second and third lines.
The following 2 lines will each contain N space separated integers describing the costs of the horizontal separating edges. So, the first line describes the costs of the edges separating cells (1, c) and (2, c) for each column c, and similarly, the second line describes the costs of the edges separating cells (2, c) and (3, c) for each column c. (0 ≤ edgecosts ≤ 100)
This will be followed by P lines each containing 2 space separated integers:
For each test case, print a single line containing the minimum cost Lumbo needs to pay to jump on the grid cells visiting each important cell at least once.
2 3 4 11 28 1 62 94 89 31 15 64 76 57 33 1 2 1 1 1 3 2 3 4 3 13 21 32 11 6 70 23 14 15 16 23 31 17 34 13 11 9 1 1 3 4 1 4
Here is an explanation for the second sample test case: