[Solution] Maximum Median Matching CodeChef Solution

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

The i$i$-th boy has a happiness value of Ai$A_i$ and the i$i$-th girl has a happiness value of Bi$B_i$. A pair consisting of the i$i$-th boy and the j$j$-th girl has a happiness value of Ai+Bj$A_i+B_j$.

Let the happiness values of the N$N$ pairs be C1,C2,…,CN$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$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 [1]$[1]$ is 1$1$, the median of [1,5,2]$[1,5,2]$ is 2$2$, and the

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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

Input Format

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

True and False Paper CodeChef Solution

The Last Levels CodeChef Solution

Easy Pronunciation CodeChef Solution

Yet Another Palindrome Making Problem CodeChef Solution

Largest Family Codechef Solution

Maximum Median Matching CodeChef Solution

Consecutive XOR Codechef Solution

Interior Design Codechef Solution

• Each test case consists of three lines of input.
  • The first line of each test case contains a single integer N$N$.
  • The second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ — the happiness values of the boys.
  • The third line of each test case contains N$N$ space-separated integers B1,B2,…,BN$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$N$ pairs.

Constraints

• 1≤T≤3⋅104$1\le T\le 3\cdot {10}^4$
• 1≤N<3⋅105$1\le N<3\cdot {10}^5$
• N$N$ is odd
• 1≤Ai,Bi≤109$1\le A_i,B_i\le {10}^9$ for each valid i$i$
• The