Server Time: Sat Sep 21, 2019 1:53 pm
Welcome ( logout
1169 - Monkeys on Twin Tower
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

Being inspired by the ongoing popularity of animation films, the monkeys are trying to be smarter. They have realized that the only way to get smarter is to learn mathematics. Hence, they have started to do so. With the creative brains as they have, they are applying math in all aspects of life. Now, one of these mathematician monkeys are standing in front of a multi-storied twin tower. The twin tower is actually a couple of tall buildings standing parallel to each other. Each of the buildings has n floors. The ground floor is floor 0, the next one is floor 1 and so on. So, there are 2n floors in total in the twin tower. Each of these floors has a fruit inside it. The monkey knows in advance the amount of time required to eat the fruit in any floor. The monkey starts from the ground floor, climbs up toward the top of the buildings and has to eat exactly n fruits. From floor i, he has only two ways to go to floor i + 1. He can go the floor i + 1 of the same building that he is on in floor i. As he is a good jumper, it can be completed in no time. Also, he can go to floor i + 1 of the other building using a spiral stair connecting the two buildings. This will take a certain time. Please note that, the monkey can only move to floor i + 1 from floor i. He wants to figure out the minimum time required to eat n fruits. Can you verify how good his math is?

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each test case consists of five lines. The first line has a single integer n (1 ≤ n ≤ 1000), the number of floors in each building. The 2nd line contains n integers separated by a single space. These integers denote the number of seconds required to eat the fruit in each floor for the first building. The time is given in ascending order of the floor i.e. the first integer is the number of seconds required to eat the fruit in ground floor of the first building while the last integer is the time required for the fruit in the topmost floor. The next line, containing n integers, describes the same values for the right building. Each of the above 2n integers has a value between 1 and 100. The line four has n - 1 space separated integers. These values denote the time required to jump from the left building to the right one. So, the first integer is the number of seconds to jump from ground floor left building to 1st floor right building. Finally, the fifth line contains n - 1 more integers giving the time required for jumping from the right building to the left one. The jumping times have values between 1 and 50.

Output

For each case, print the case number and the minimum number of seconds required to eat n fruits.

Sample Input

Output for Sample Input

1

4

5 6 8 9

7 9 3 10

5 2 3

2 4 3

Case 1: 26

 


Problem Setter: Mohammad Mahmudur Rahman
Special Thanks: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan