##### Xenny and Alternating Tasks

Xenny and Yana were very keen to celebrate Valentine’s Day at their home. To make preparations for the celebration, they listed down **N** tasks that they had to complete.

To complete the **i ^{th}** task, Xenny takes

**X**seconds and Yana takes

_{i}**Y**seconds. In order to minimize the disparity in tasks performed, they decide to do the tasks

_{i}**alternatingly**. If Xenny did the

**1**task, then Yana would just wait and watch him until he completes the task. After that, Yana would start the

^{st}**2**task, and while she does her task, Xenny would just watch her. He would start the

^{nd}**3**task only after her completion, and they would keep doing tasks alternatingly uptil the

^{rd}**N**task. They could also do tasks in the other order – that is, Yana could do the

^{th}**1**task, after that Xenny could do the

^{st}**2**task, and so on. Their eventual goal was to minimize the total time taken by them to complete all

^{nd}**N**tasks.

Please help them find the minimum total time they would take to complete all **N** tasks.

### Input

The first line of the input contains an integer **T** denoting the number of test cases. The description of **T** test cases follows.

The first line of each testcase contains a positive integer **N** – the number of tasks to be completed.

The second line contains **N** space-separated positive integers representing the time taken in seconds by Xenny to complete the **i ^{th}** task.

The third line contains **N** space-separated positive integers representing the time taken in seconds by Yana to complete the **i ^{th}** task.

### Output

For each testcase, print a single line containing the minimum total time in seconds Xenny and Yana would take to complete the tasks.

### Constraints

**Subtask 1: 40 points**

**1**≤**T**≤**10****1**≤**N**≤**3****1**≤**X**,_{i}**Y**≤_{i}**10**^{5}

**Subtask 2: 60 points**

**1**≤**T**≤**10****1**≤**N**≤**2*10**^{4}**1**≤**X**,_{i}**Y**≤_{i}**10**^{5}

### Sample Testcase

Input:1 3 2 1 2 3 2 1Output:5

### Explanation

Let’s say Xenny does the 1^{st} task. Then Yana would do the 2^{nd} task and Xenny would do the 3^{rd} task. Hence, the total time taken would be: 2 + 2 + 2 = 6 seconds.

Another possibility is that Yana does the 1^{st} task, Xenny does the 2^{nd} task and then Yana does the 3^{rd} task. The total time taken in this case would be 5 seconds.

Hence, the **minimum** total time taken would be **5 seconds**.

Solution:Hint: No need to take large data types and store the two arrays ( of each one's task distribution). The problem can be solved without that.