Minimise Maximum Sum

★★★★★

3.5

12 votes

Sorting, Easy

Details

Problem

You are given an array containing \(2 \times n\) elements.You have to partition the numbers in to n pairs with the property that partition minimize the maximum sum of a pair.

Input

First line contains T number of test cases. Next line contain N number of pairs. Next line contain 2*N positive integers represent elements of an array.

Output

For each test case print minimum possible maximum sum of a pair.

CONSTRAINTS

1<=T<=100
1<=N<=100000
1<=A[i]<=100000

Sample Input

1
3
5 6 2 3 9 8

Sample Output

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

In sample input possible partitions are ((5,6) , (9,2) , (8,3)) and pair sum for these partitons are (11,11,11) so minimum possible maximum sum is 11. Other possible pairs are ((3,2) , (9,5) , (8,6)) so here minimum possible maximum sum is 14. So 11 is minimum possible maximum sum from all possible pair of partitions.