Description

The game is played on a number line that extends infinitely to the left and right. There are $n$ fleas and $m$ pits on it, and they can both be modeled as points on the number line.

In each round, the player must choose to make all fleas jump together one unit to the left or one unit to the right. If a point representing a flea coincides with a point representing a pit, the flea will fall into the pit, scream, and then die.

The upset Xiaoxue wants to kill all fleas in the shortest time. Please help her compute the minimum number of rounds needed.

Input Format

The first line contains two positive integers $n,m$ separated by spaces.

The second line contains $n$ integers $x_1,x_2,\ldots,x_n$ separated by spaces, where $x_i$ is the initial coordinate of the $i$-th flea.

The third line contains $m$ integers $y_1,y_2,\ldots,y_m$ separated by spaces, where $y_i$ is the coordinate of the $i$-th pit.

The input guarantees that all of these $n+m$ coordinates are pairwise distinct.

Output Format

Only one line with one integer, the minimum number of rounds needed to kill all fleas.

3 2
3 -1 2
0 10

5

见附加文件的 hole2.in。 

见附加文件的 hole2.ans。

Hint

[Sample 1 Explanation]

In the first round, make all fleas jump one step to the right. The second flea falls into the first pit, and the remaining two fleas are at $4, 3$ respectively.

In the next four rounds, make all fleas jump to the left. Both fleas fall into the first pit, and the game ends.

[Constraints and Notes]

Note: The input size of this problem is large, so please avoid overly slow input methods.

• For $20\%$ of the testdata, $1 \le n \le 20$, $1 \le m \le 300$.
• For another $20\%$ of the testdata, $1 \le n,m \le 300$.
• For another $20\%$ of the testdata, $1 \le x_i,y_i \le 2000$.
• For another $10\%$ of the testdata, $1 \le n,m \le 2000$.
• For another $10\%$ of the testdata, $m=2$.
• For $100\%$ of the testdata, $1 \le n,m \le 2 \times 10^5$, $-10^9 \le x_i,y_i \le 10^9$.

Translated by ChatGPT 5