409930: GYM103855 M Short Question

Memory Limit:1024 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

M. Short Questiontime limit per test4 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

I have a question, could you please answer it?

You are given two sequences $$$(p_1, p_2, \ldots, p_N)$$$, $$$(q_1, q_2, \dots, q_N)$$$ of length $$$N$$$. What is the value of this sum?

$$$$$$\sum_{i=1}^{N} {\sum_{j=1}^{N} {\min(|p_i - p_j|, |q_i - q_j|)} }$$$$$$

Input

In the first line, a single integer $$$N$$$ is given ($$$ 1 \leq N \leq 1\,000\,000$$$).

In the second line, $$$N$$$ integers $$$p_1, p_2, \ldots, p_N$$$ are given ($$$1 \leq p_i \leq 1\,000\,000$$$).

In the third line, $$$N$$$ integers $$$q_1, q_2, \ldots, q_N$$$ are given ($$$1 \leq q_i \leq 1\,000\,000$$$).

Output

Output a single integer, the answer to the question.

ExamplesInput
3
1 3 2
1 2 3
Output
6
Input
4
1 1 1000000 1000000
1000000 1000000 1 1
Output
7999992

加入题单

上一题 下一题 算法标签: