Xenny and Alternating Tasks

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
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_{i} seconds and Yana takes Y_{i} seconds. In order to minimize the disparity in tasks performed, they decide to do the tasks alternatingly. If Xenny did the 1^{st} task, then Yana would just wait and watch him until he completes the task. After that, Yana would start the 2^{nd} task, and while she does her task, Xenny would just watch her. He would start the 3^{rd} task only after her completion, and they would keep doing tasks alternatingly uptil the N^{th} task. They could also do tasks in the other order  that is, Yana could do the 1^{st} task, after that Xenny could do the 2^{nd} task, and so on. Their eventual goal was to minimize the total time taken by them to complete all 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 spaceseparated positive integers representing the time taken in seconds by Xenny to complete the i^{th} task.
The third line contains N spaceseparated 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 1 Output: 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.
Author:  wittyceaser 
Tester:  xcwgf666 
Editorial  https://discuss.codechef.com/problems/XENTASK 
Tags  basicprog, cakewalk, march17, wittyceaser 
Date Added:  15022017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 