## Maximum Median Matching Codechef Solution | MEDMAXMATCH | (100/100) FULL | Codechef July Lunchtime | AC Code

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

The -th boy has a happiness value of and the -th girl has a happiness value of . A pair consisting of the -th boy and the -th girl has a happiness value of .

Let the happiness values of the pairs be . 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 , 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 is , the median of is , and the median of is .

### Input Format

• The first line of input will contain a single integer , 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 .
• The second line of each test case contains space-separated integers — the happiness values of the boys.
• The third line of each test case contains space-separated integers — the happiness values of the girls.

### Output Format

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

### Constraints

• is odd
• for each valid
• The sum of across all test cases won’t exceed .

### Sample Input 1

3
1
10
25
3
1 6 6
2 2 7
5
10 4 93 5 16
4 34 62 6 26


### Sample Output 1

35
8
50


### Explanation

Test case

There is only one boy and one girl, so they must be paired with each other. The happiness value of the pair is , and it is also the median.

Test case

Pair with , with , and with . The happiness values are then , with a median of . It can be shown that this is the maximum possible median.

Test case

One way of achieving a median of is as follows:

• Pair with , for a happiness of
• Pair with , for a happiness of
• Pair with , for a happiness of
• Pair with , for a happiness of
• Pair with , for a happiness of

The happiness values are , with a median of . It can be shown that no other pairing obtains a strictly larger median.

				
void solve()
{
ll oo = 1, n;
if (oo != 1)
{
ll ji = -1;
}
else
{
cin >> n;
}

vector<ll> y(n);
vector<ll> x(n);

for (ll i = 0; i < n; i++)
cin >> x[i];
sort(x.begin(), x.end());
for (ll i = 0; i < n; i++)
cin >> y[i];

sort(y.begin(), y.end());

vector<ll> we;

for (ll i = n / 2; i < n; i++)
we.push_back(y[i]);
b = we;
we.clear();
for (ll i = n / 2; i < n; i++)
we.push_back(x[i]);
a = we;

n = a.size();
vector<ll> cty;
for (ll i = 0; i < n; i++)
{
cty.push_back(x[i] + y[n - 1 - i]);
}
sort(cty.begin(), cty.end());
cout << cty << endl;
}