H. Permutator
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Manuel and Felix have been searching for a good math problem all night before the TeamsCode Contest, and they've found it!

Omer has two arrays $$$a$$$ and $$$b$$$, permute $$$b$$$ to minimize the sum of $$$a[k] \cdot b[k]$$$ where $$$(i \leq k \leq j)$$$ for every subarray $$$[i, j]$$$.

In other words, you have to minimize the value of the following expression: $$$\sum_{i = 0}^{n-1} \sum_{j = i}^{n-1} \sum_{k = i}^{j} a_{k} \cdot b_{k}$$$

Input

The first line consists in one integer $$$n$$$ $$$(2 \leq n \leq 10^{5})$$$ — the number of elements in both arrays.

The second line consists in $$$n$$$ integers $$$a_{0}, ..., a_{n-1}$$$ $$$(-100 \leq a_{i} \leq 100)$$$ — the values of the elements in $$$a$$$.

The third line consists in $$$n$$$ integers $$$b_{0}, ..., b_{n-1}$$$ $$$(-100 \leq b_{i} \leq 100)$$$ — the values of the elements in $$$b$$$.

—

Testcases in subtasks are numbered from $$$1$$$ to $$$20$$$ with samples skipped.

Tests $$$1-2$$$: $$$(1 \leq n \leq 6)$$$.

Tests $$$3-20$$$: No additional constraints.

Each test is worth 5 points with samples skipped.

Output

Output the minimum possible value after permuting $$$b$$$.

Example
Input
3
5 4 -1
4 3 2
Output
65
Note

You can permute $$$b$$$ to obtain $$$(3, 2, 4)$$$ and minimize the answer.

 —

Problem Idea: danx

Problem Preparation: danx

Occurrences: Novice 6