Sequences + Longest Common Subsequence

Minimal Sum

Two arrays of positive integers are given: a1..n and b1..n. Find the permutation i1, i2, ..., in of numbers 1, 2, ..., n, for which the sum

a1 * bi1 + ... + an * bin

is minimal. Each number must be included in permutation only once.


The first line contains the number of elements n (n100) in arrays. The second line contains the elements of the first array, and the third line contains the elements of the second array. The array elements do not exceed 106.


Print the minimal value of required sum.

Time limit 1 seconds
Memory limit 128 MiB
Input example
7 2 4 3 10
5 11 6 9 6
Output example