Minimum Sum of Absolute Differences

You have been given two arrays/lists 'ARR1' and 'ARR2' of length 'N'. Your task is to pair each element of 'ARR1' to an element of 'ARR2' such that the sum of the absolute difference of all pairs is minimum.

Example:

If 'ARR1' = [0, 2, 1], and 'ARR2' = [8, 10, 4] then the most optimal pairing will be (0, 4) , (1, 8) and (2, 10). The sum of absolute difference will be 4 + 7 + 8 = 19.

Note:

An element from one array can make a pair only with at most one element of another array.

Input Format:

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains a positive integer ‘N’ which represents the length of the array/list.

The second line of each test case contains ‘N’ single space-separated integers representing the elements of the first array/list(ARR1).

The third line of each test case contains ‘N’ single space-separated integers representing the elements of the first array/list(ARR2).

Output Format:

For each test case, the only line of output will print an integer denoting the minimum sum of absolute difference of all pairs.

Print the output of each test case in a separate line.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 100
1 <= N <= 5000
0 <= ARR1[i] <= 10^5
0 <= ARR2[i] <= 10^5

Time limit: 1 sec