Magda and Silly Pairs

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME73/hindi/SILLYPRS.pdf), [Bengali](http://www.codechef.com/download/translated/LTIME73/bengali/SILLYPRS.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME73/mandarin/SILLYPRS.pdf), [Russian](http://www.codechef.com/download/translated/LTIME73/russian/SILLYPRS.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME73/vietnamese/SILLYPRS.pdf) as well. Chef and his friend Magda have $2N$ mutual friends: $N$ of these friends are chefs and the other $N$ are chefettes. The chefs are numbered $1$ through $N$ and the chefettes are (independently) also numbered $1$ through $N$. Since Magda wants their friends to be as happy as possible and to preserve traditional family values, she wants to pair them up in such a way that each chef is paired with exactly one chefette and each chefette with exactly one chef. The chefs have heights $A_1, A_2, \ldots, A_N$ and the chefettes have heights $B_1, B_2, \ldots, B_N$. For each valid $i, j$, if the $i$th chef and the $j$th chefette are paired, they will have exactly one child with height $\left\lfloor\frac{A_i+B_j}{2}\right\rfloor$. Magda wants to pair up the chefs and chefettes in such a way that the sum of heights of all their children ($N$ children in total) is maximum possible. Please help her do that. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \ldots, A_N$.  The third line contains $N$ spaceseparated integers $B_1, B_2, \ldots, B_N$. ### Output Print a single line containing one integer ― the maximum sum of heights of the children. ### Constraints  $1 \le T \le 10$  $1 \le N \le 10^5$  $1 \le A_i \le 10^9$ for each valid $i$  $1 \le B_i \le 10^9$ for each valid $i$ ### Subtasks **Subtask #1 (40 points):** $1 \le N \le 100$ **Subtask #2 (60 points):** original constraints ### Example Input ``` 2 3 4 5 6 1 2 3 5 4 8 6 4 1 2 5 7 4 7 ``` ### Example Output ``` 10 23 ``` ### Explanation **Example case 1:** One possible solution is to pair the first chef with the second chefette, the second chef with the first chefette and the third chef with the third chefette. Their children will have heights $3$, $3$ and $4$, respectively.Author:  thesitzr 
Tags  ltime73, taran_1407, thesitzr 
Date Added:  22062019 
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, rust, SCALA, swift, 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions