Problem Description

Xiao Lan’s job is to manage shared bicycles. Now, he needs to move $n$ shared bicycles that are not properly parked to $m$ parking spots.

Xiao Lan’s management area is a street, which can be viewed as a number line. The $i$-th bicycle is at position $a_i$, and the $j$-th parking spot is at position $b_j$.

Moving a bicycle from position $x$ to a parking spot at position $y$ costs $|x - y|$ units of effort.

Each parking spot can hold at most one bicycle. It is known that $n \leq m$, so it is always possible to assign a parking spot to every bicycle. You need to compute: under a reasonable assignment of bicycles to parking spots, what is the minimum total effort Xiao Lan needs.

Input Format

The input consists of 3 lines.

The first line contains two positive integers $n, m$, representing the number of bicycles and the number of parking spots.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, representing the positions of the bicycles.

The third line contains $m$ positive integers $b_1, b_2, \dots, b_m$, representing the positions of the parking spots.

Output Format

Output one line with one positive integer, representing the minimum effort Xiao Lan needs to spend.

3 4
1 3 7
2 4 5 8

3

3 4
3 1 3
5 2 2 8

4

Hint

Sample Explanation 1

One optimal assignment is as follows:

• Move the bicycle at position $1$ to the parking spot at position $2$.
• Move the bicycle at position $3$ to the parking spot at position $4$.
• Move the bicycle at position $7$ to the parking spot at position $8$.

The total cost is:

$$\begin{aligned} |1 - 2| + |3 - 4| + |7 - 8| = 1 + 1 + 1 = 3 \end{aligned}$$

Therefore, the minimum effort required is $3$.

Constraints and Notes for Test Cases

For $40\%$ of the test cases, $n, m \leq 8$.

For another $20\%$ of the test cases, $n = m$.

For all test cases, $1 \leq n \leq m \leq 5000$, $1 \leq a_i, b_i \leq 10^9$.

Translated by ChatGPT 5