For two n-dimensional vectors u = (u1, u2, ... , un)
and v = (v1, v2, ... , vn)
, the dot product of these vectors is a single number equal to u1v1 + u2v2 + ... + unvn
You are given two n dimensional vectors u
and v
. You are allowed to permute the coordinates of each vector in any way possible.
Choose two permutations such that the inner product of your two new vectors (formed after permutation) is the smallest possible, and output that minimum inner product.
Input Format
The first line contains the integer n
, representing the dimension of the vectors. The next two lines contain n
space separated integers each, giving the coordinates of u
and v
respectively.
Output Format
For each test case, output a single integer indicating the minimum dot product you obtained.
Constraints
1 <= n <= 1000
-100000 <= ui , vi <= 100000