Dot Products

5

2 votes
Easy
Problem

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

Time Limit: 1.5
Memory Limit: 256
Source Limit:
Editor Image

?