51 1 s 128 MB

The people of RGB Street have decided to paint each of their houses red, green, or blue. They've also decided that no two neighboring houses will be painted the same color. The neighbors of house i are houses i-1 and i+1. The first and last houses are not neighbors.

You will be given three arrays of integers R, G and B. Each element of R is the cost of painting the corresponding house red. G and B are defined in a similar manner. Compute the minimal total cost required to perform the work.

The first line contains the number of test cases T (T ≤ 150).

Each test case consists four consecutive lines. N, the number of houses (1 ≤ N ≤ 20) will be given on the first line. Each of three following lines consists N integers separated by spaces, representing elements of R, G and B. Each elements will be between 1 and 1000, inclusive.

Output the answer of each test case on a separate line.

## Sample Input | ## Sample Output |
---|---|

2 3 1 100 100 100 1 100 100 100 1 3 1 100 1 100 100 100 100 100 100 | 3 102 |