## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Maximum Median Matching CodeChef Solution

boys and $N$ girls attend a dance class, where $N$ is odd. For today's practice session, they need to form $N$ boy-girl pairs.

The $i$-th boy has a happiness value of ${A}_{i}$ and the $i$-th girl has a happiness value of ${B}_{i}$. A pair consisting of the $i$-th boy and the $j$-th girl has a happiness value of ${A}_{i}+{B}_{j}$.

Let the happiness values of the $N$ pairs be ${C}_{1},{C}_{2},\dots ,{C}_{N}$. The dance instructor would like it if many of the pairs have a high happiness value, and passes the task to you — find the maximum possible value of the median of $C$, if the boy-girl pairs are chosen optimally.

Note: The median of a odd-sized list of integers is the middle number when they are sorted. For example, the median of $\left[1\right]$ is $1$, the median of $\left[1,5,2\right]$ is $2$, and the

Solution Click Below:-  👉
👇👇👇👇👇

median of $\left[30,5,5,56,3\right]$ is $5$.

### Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.

• Each test case consists of three lines of input.
• The first line of each test case contains a single integer $N$.
• The second line of each test case contains $N$ space-separated integers ${A}_{1},{A}_{2},\dots ,{A}_{N}$ — the happiness values of the boys.
• The third line of each test case contains $N$ space-separated integers ${B}_{1},{B}_{2},\dots ,{B}_{N}$ — the happiness values of the girls.

### Output Format

For each test case, output on a new line the maximum possible median happiness of the $N$ pairs.

### Constraints

• $1\le T\le 3\cdot {10}^{4}$
• $1\le N<3\cdot {10}^{5}$
• $N$ is odd
• $1\le {A}_{i},{B}_{i}\le {10}^{9}$ for each valid $i$
• The