← Home
write a go solution for Description:
There 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 nxn such that c_i,j=|a_i-b_j| for every iin[1,n] and every jin[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 jin[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 iin[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 jin[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 iin[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 Format:
The first line contains one integer n (2<=n<=2*10^5).

The second line contains n integers a_1,a_2,...,a_n (0<=a_i<=10^8).

The third line contains n integers b_1,b_2,...,b_n (0<=b_j<=10^8).

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

Note:
In the first example, the matrix looks as follows:

111000111

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:

221001221

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.. Output only the code with no comments, explanation, or additional text.