Hero to Zero

题意翻译

给定两个长度为 $n$ 的非负整数数组 $a$ 和 $b$。考虑一个 $n \times n$ 的矩阵 $ c_{i,j} = |a_i - b_j|$ $ ( i \in [1, n],j \in [1, n] )$，你的任务是以最少的分数将矩阵 $c_{i,j}$ 变成一个零矩阵，即矩阵中的每个元素都是 0 。你的初始分数是 0 。 你可以对矩阵 $c$ 进行以下操作： + 将第 $i$ 行的所有元素 -1，你的分数 +1； + 将第 $j$ 行的所有元素 -1，你的分数 +1； + 将第 $i$ 行第 $j$ 列的元素 $c_{i,j}$ -1，你的分数 +1； + 将第 $i$ 行的所有元素 +1，你的分数 -1； + 将第 $j$ 行的所有元素 +1，你的分数 -1； 输出你获得的最小分数。 $ 2 \le n \le 2 \cdot 10^5 $，$ 0 \le a_i,b_j \le 10^8 $。

题目描述

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 $ 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.

输入输出格式

输入格式

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 $ ).

输出格式

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

输入输出样例

输入样例 #1

3
1 2 3
2 2 2

输出样例 #1

2

输入样例 #2

3
3 1 3
1 1 2

输出样例 #2

5

输入样例 #3

2
1 0
2 1

输出样例 #3

2

输入样例 #4

2
1 4
2 3

输出样例 #4

4

输入样例 #5

4
1 3 3 7
6 9 4 2

输出样例 #5

29

说明

In the first example, the matrix looks as follows: 111000111You 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: 221001221You 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.