Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

graph matchings

math

*2900

No tag edit access

The problem statement has recently been changed. View the changes.

×
J. Hero to Zero

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputThere are no heroes in this problem. I guess we should have named it "To Zero".

You are given two arrays $$$a$$$ and $$$b$$$, each of these arrays contains $$$n$$$ non-negative integers.

Let $$$c$$$ be a matrix of size $$$n \times n$$$ such that $$$c_{i,j} = |a_i - b_j|$$$ for every $$$i \in [1, n]$$$ and every $$$j \in [1, n]$$$.

Your goal is to transform the matrix $$$c$$$ so that it becomes the zero matrix, i. e. a matrix where every element is exactly $$$0$$$. In order to do so, you may perform the following operations any number of times, in any order:

- choose an integer $$$i$$$, then decrease $$$c_{i,j}$$$ by $$$1$$$ for every $$$j \in [1, n]$$$ (i. e. decrease all elements in the $$$i$$$-th row by $$$1$$$). In order to perform this operation, you pay $$$1$$$ coin;
- choose an integer $$$j$$$, then decrease $$$c_{i,j}$$$ by $$$1$$$ for every $$$i \in [1, n]$$$ (i. e. decrease all elements in the $$$j$$$-th column by $$$1$$$). In order to perform this operation, you pay $$$1$$$ coin;
- choose two integers $$$i$$$ and $$$j$$$, then decrease $$$c_{i,j}$$$ by $$$1$$$. In order to perform this operation, you pay $$$1$$$ coin;
- choose an integer $$$i$$$, then increase $$$c_{i,j}$$$ by $$$1$$$ for every $$$j \in [1, n]$$$ (i. e. increase all elements in the $$$i$$$-th row by $$$1$$$). When you perform this operation, you receive $$$1$$$ coin;
- choose an integer $$$j$$$, then increase $$$c_{i,j}$$$ by $$$1$$$ for every $$$i \in [1, n]$$$ (i. e. increase all elements in the $$$j$$$-th column by $$$1$$$). When you perform this operation, you receive $$$1$$$ coin.

You have to calculate the minimum number of coins required to transform the matrix $$$c$$$ into the zero matrix. Note that all elements of $$$c$$$ should be equal to $$$0$$$ simultaneously after the operations.

Input

The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^8$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_j \le 10^8$$$).

Output

Print one integer — the minimum number of coins required to transform the matrix $$$c$$$ into the zero matrix.

Examples

Input

3 1 2 3 2 2 2

Output

2

Input

3 3 1 3 1 1 2

Output

5

Input

2 1 0 2 1

Output

2

Input

2 1 4 2 3

Output

4

Input

4 1 3 3 7 6 9 4 2

Output

29

Note

In the first example, the matrix looks as follows:

1 | 1 | 1 |

0 | 0 | 0 |

1 | 1 | 1 |

You can turn it into a zero matrix using $$$2$$$ coins as follows:

- subtract $$$1$$$ from the first row, paying $$$1$$$ coin;
- subtract $$$1$$$ from the third row, paying $$$1$$$ coin.

In the second example, the matrix looks as follows:

2 | 2 | 1 |

0 | 0 | 1 |

2 | 2 | 1 |

You can turn it into a zero matrix using $$$5$$$ coins as follows:

- subtract $$$1$$$ from the first row, paying $$$1$$$ coin;
- subtract $$$1$$$ from the third row, paying $$$1$$$ coin;
- subtract $$$1$$$ from the third row, paying $$$1$$$ coin;
- subtract $$$1$$$ from $$$a_{2,3}$$$, paying $$$1$$$ coin;
- add $$$1$$$ to the third column, receiving $$$1$$$ coin;
- subtract $$$1$$$ from the first row, paying $$$1$$$ coin;
- subtract $$$1$$$ from $$$a_{2,3}$$$, paying $$$1$$$ coin.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/14/2024 05:11:50 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|