HUST Past Monthly Hard Problems Challenge Contest (1)
From: 20110513 12:00:00
To: 20110513 17:00:00
Now: 20170920 01:10:11
Status: Public
J  Cube Tower 2
Time Limit: 5s
Memory Limit: 128MB
Submissions: 52 Solved: 8
 Description
 There are a large cube tower which are stacked as following:
 There are N levels, numbered 0, 1, 2, ……, N1 from bottom to top, each has (Ni)*(Ni) cubes.
 Each level’s topmost row and leftmost column are against walls.
Now Ai.Freedom (a brave man) wants to reach the top cube face of the stack. But there are monsters, zombies, and ghosts on the way, it makes the explore not smoothly. Choose different paths will got into different difficulties.
To make the problem simple, assume each colored face has a difficulty value(be shown as in the figure). Ai.Freedom has previously got a map with difficulty values marked on each face. When he reaches a face he will encounter the monsters, zombies, and ghosts with the marked difficulty.
When he is on a BLUE face or GREEN face, he can only climb up to a YELLOW face which is exactly upward of his position. And when he is on a YELLOW face he can move to another YELLOW face next to it, and he can go upward as well.
Every face with the same color on the same level has the same difficulty value.
So please help Ai.Freedom choose the best path to reach the top, which has the minimum total difficulty value.
 Input
 The first line contains a single integer T, the number of test cases.
For each case:
The first line contains a single integer N (1<=N<=100,000) indicating the level number.
The following line contains N numbers, indicating the difficulty value G[i] of the GREEN face on the ith level.(i=0,1,2,……,N1,the same below)
The following line contains N numbers, indicating the difficulty value B[i] of the BLUE face on the ith level.
And the last line contains N numbers, indicating the difficulty value Y[i] of YELLOW face on the ith level.
(1<=G[i],B[i],Y[i]<=5,000)
 Output
 For each case, write a single number for the minimum total difficulty value.
(One of the best path to reach the top of the second sample input are shown in the figure.)
 Sample Input

2
5
3 3 100 3 2
4 5 8 30 19
2 2 2 2 2
5
52 6 9 8 7
8 7 5 4 55
8 9 2 4 2
 Sample Output

35
60
 Hint
 Source
 Gaewah & yh