Cube Tower 2

HUST Past Monthly Hard Problems Challenge Contest (1)

Time Limit : 5 Second

Memory Limit : 128 MB

Submission: 52

Solved: 8

Description

There are a large cube tower which are stacked as following:

There are N levels, numbered 0, 1, 2, ……, N-1 from bottom to top, each has (N-i)*(N-i) 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 i-th level.(i=0,1,2,……,N-1,the same below)
The following line contains N numbers, indicating the difficulty value B[i] of the BLUE face on the i-th level.
And the last line contains N numbers, indicating the difficulty value Y[i] of YELLOW face on the i-th 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

<a href="http://www.gaewah.com/">Gaewah</a> & yh

Submit