Description

In Monkey Village, there is a straight mountain path that is very narrow, and its width can be ignored. There are $n$ monkeys standing on the path watching the students who came to compete today. Let a positive integer $X_i$ denote the position of the $i$-th monkey; no two monkeys stand at the same position. There are $m$ tall trees planted at positions along this path. Let a positive integer $Y_j$ denote the position of the $j$-th tree; no two trees occupy the same position.

While the monkeys were intently admiring everyone's excellent programming skills, a tiger swaggered over. The monkeys broke into a cold sweat. Their first reaction was to find a tall tree to climb, which would help them avoid being bitten or eaten by the tiger (do not consider the tiger climbing trees).

If the monkey at position $a$ runs to the tree at position $b$, the energy cost is $|a - b|$. To make the most effective use of these trees for shelter, each tree must have at least one monkey. Please compute the minimum total energy required for all $n$ monkeys to climb onto trees.

Input Format

The input consists of 4 lines.

• Line 1: an integer $n$, the number of monkeys.
• Line 2: $n$ integers; the $i$-th integer $X_i$ is the position of the $i$-th monkey.
• Line 3: an integer $m$, the number of trees.
• Line 4: $m$ integers; the $j$-th integer is the position $Y_j$ of the $j$-th tree.

Output Format

Output one line with a single integer: the minimum total energy required for all $n$ monkeys to climb onto trees.

3
1 4 5
2
3 8

6

3
3 1 10
2
8 3

4

Hint

For $30\%$ of the testdata, $1 \le n \le 500$, $1 \le X_i, Y_i \le 10^5$.

For $100\%$ of the testdata, $1 \le n \le 5000$, $1 \le m \le n$, $1 \le X_i, Y_i \le 10^9$.

Translated by ChatGPT 5