P2769 Monkeys Climb Trees

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.

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 one line with a single integer: the minimum total energy required for all $n$ monkeys to climb onto trees.

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