At our soccer training camp, we have rehearsed a lot of motion sequences. In case we are defending, all players except the two strikers of our team are in our half. As soon as we are getting the ball, we are starting a counterattack with a long-range pass to one of our strikers. They know each others motion sequences and may pass the ball to the other striker at fixed points.

There are a lot of decisions: the defender has to select the striker to pass the ball to, and the ball possessing striker has to decide at each of the n fixed points if to pass to the other striker or to run and to dribble. At the last position in the motion sequence of a striker he shoots on the goal. Each of the four actions (long-range pass, dribble, pass, and shoot on the goal) may fail (e.g. because of a defending player of the opposite team) - so our coach has assigned difficulties.

What is the minimal difficulty of a goal assuming your team plays optimally?

In the example depicted in the picture, the defending player (cross in left half) passes the ball to one of the strikers (crosses in right half). The strikers move along fixed paths simultaneously. At each of the fixed positions (circles), the ball possessing striker either dribbles with the ball or passes to the other striker. At the last position, he shoots on the goal.

Input

The first line of the input consists of the number of test cases c that follow (1 ≤ c ≤ 100). Each test case consists of five lines. The first line of each test case contains n (2 ≤ n ≤ 100000), the number of fixed points in each strikers motion sequence. It is followed by l₀, l₁, s₀ and s₁, the difficulty of a long-range pass to the corresponding striker and the difficulties of the shoots of the strikers. Each striker is described in two lines (first striker 0, then striker 1): The first line contains n-1 difficulties, where the ith number stands for passing from point i to the other player at point i + 1. The second line also contains n-1 difficulties, where the ith number stands for dribbling from point i to point i+1. You may safely assume that each difficulty is a non-negative integer less than 1000.

Output

For each test case in the input, print one line containing the minimal difficulty of a move sequence leading to a goal.

Example

Input:
2
3 3 5 7 999
9 13
60 5
22 6
5 5
5 3 5 7 999
9 13 8 4
60 5 17 13
22 6 15 11
5 5 18 29
Output:
23
42