Minimum Absolute Difference Matching with Forbidden Equal Pairs

You are given two sequences of n integers: \(A_1, A_2, \ldots, A_n\) and \(B_1, B_2, \ldots, B_n\). Your task is to find a pairing between the numbers such that each \(A_i\) is paired with exactly one \(B_{p(i)}\) (where \(p\) is a permutation of \(\{1,2,\ldots,n\}\)). The objective is to minimize the sum of the absolute differences \(|A_i - B_{p(i)}|\) over all pairs, under the restriction that you are not allowed to pair two equal numbers (i.e. pairing is forbidden when \(A_i = B_{p(i)}\)).

For example, consider \(A = \{5, 6, 8\}\) and \(B = \{5, 7, 8\}\). Although a natural pairing by sorted order would be \(5 \sim 5\), \(6 \sim 7\), \(8 \sim 8\), such pairing is illegal because pairs \(5 \sim 5\) and \(8 \sim 8\) match equal numbers. The optimal valid pairing here is: \(5 \sim 8\), \(6 \sim 5\), and \(8 \sim 7\) with absolute differences \(3\), \(1\), and \(1\) respectively, giving a total cost of \(5\).

If it is impossible to create a valid pairing, output -1.

Note: The absolute difference is defined as \(|x-y|\) and all formulas are written in \(\LaTeX\) format.

inputFormat

The input begins with a single integer \(n\) (the number of elements in each sequence). The second line contains \(n\) space-separated integers representing the sequence \(A\). The third line contains \(n\) space-separated integers representing the sequence \(B\).

Example:

3
5 6 8
5 7 8

outputFormat

Output a single integer representing the minimum total absolute difference of all valid pairings. If no valid pairing exists, output -1.

Example:

5

sample

3
5 6 8
5 7 8

5