Problem F

Fallen Tree

Problem Description

Early on this morning, the old tree in John’s garden had collapsed onto the street in front of his house. Fortunately no one was injured and no cars were damaged. The tree was big enough to cover one side of the street so cars from one direction can’t go through. Although it’s still morning, this little accident has tied up the traffic because cars from both directions can only use the only remaining clear side, which creates bottleneck. And because of this, everyone is getting impatient and starts to honk their car.

Feeling bad, John decided to help control the traffic. First, he forbids more cars to get into the street. And then, he controls the cars that already caught in the traffic to escape from there. Unfortunately, no car is willingly to turn back, so the only option is to allow each car moving forward and escape from the clear side.

Each car driver has various type of temperament (he can tell it by the number of their honk in a minute), but easy to predict. When cars from his/her side are moving, he/she will not honk. If they’re stop moving (because of the opposite direction cars turn to use the clear side), then he/she will start to honk again.

The most front car needs exactly one minute to escape from the bottleneck. To alternate the turn from one direction to another, you need one extra minute, and other cars that still queued in both directions will also honk on that minute.

Supposed that you know the number of cars in each direction, and the number of honk in a minute for each car, help John to calculate the least amount of total honk he will receive from all cars.

Input Speficication

The first line of input contains an integer T, the number of test cases follow

Each case begins with two integers, L (0 <= L <= 1,000) the number of cars in the left part (who want to go right), and R (0 <= R <= 1,000) the number of cars in the right part (who want to go left). The next two lines, each contains L and R integers consecutively. Each line contains H_i the number of honk per minute (0 <= H_i <= 100,000) from each car. The first element is the most front car in each queue, while the last element is the most back in the queue (last to escape).

Output Speficication

For each case, print in a single line the number of least amount of honk that John will possibly receive from all cars.

2
4 4
5 1 1 1
2 2 2 2
5 5
6 1 1 1 1
2 2 2 2 2

34
48