Flea Elimination Game

The game takes place on an infinite horizontal number line. Initially, there are n fleas and m pits located at some integer coordinates. In each round the player must choose a common direction (left or right) and move every flea by 1 unit in that direction. Right after a move, any flea whose coordinate coincides with a pit will fall in, let out a shriek, and die.

Using this mechanic, the objective is to kill all the fleas in as few rounds as possible. In one round all fleas move by the same amount so the overall process is determined by a sequence of moves which produces a sequence of net displacements \( S_0=0,\ S_i=S_{i-1}\pm1,\ i\ge1. \)

A flea initially at coordinate \(x\) will be killed in some round \(i\) if at that round the net displacement \(S_i\) equals \(p-x\) for some pit coordinate \(p\); in other words, if \(x+S_i=p\). Since the numbers \(p-x\) depend on both the flea and pit positions, one is allowed to "choose" for each flea an effective target difference \(d=x_{pit} - x\) by selecting an appropriate pit.

However, the twist is that the same move sequence (which is a valid walk on the number line with unit steps) must “hit” the chosen target difference for every flea (possibly at different rounds). Note that any valid move sequence \(S_0,...,S_k\) (with \(S_0=0\) and increments of \(\pm1\)) always visits every integer in the closed interval \([L,R]\), where \(L=\min_i\,S_i\) and \(R=\max_i\,S_i\). Hence the problem reduces to choosing, for every flea at \(x\), one candidate target difference \(d\) (where \(d\in\{p-x: p\text{ is a pit}\}\)) such that all these numbers lie in some interval \([L,R]\) and then “designing” a move sequence whose cost (i.e. minimal number of rounds) is exactly the minimal number of rounds required to traverse the interval starting from 0.

It is well known that if you have to cover an interval \([L,R]\) starting at 0 (with unit moves allowed and you may choose your path arbitrarily) the minimal number of rounds required is

[ \text{cost}(L,R)=\begin{cases} R, &\text{if }0\le L,\ -L, &\text{if }R\le0,\ (R-L)+\min{R, -L}, &\text{if }L<0<R. \end{cases} ]

Your task is to determine the minimum possible number of rounds required to kill all fleas if you can choose both the assignment (i.e. which pit will kill each flea) and the move sequence optimally.

Note: A pit can kill more than one flea (if several fleas land on it in the same move). It is not necessary that the same pit is used only once.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 10^5\)) — the number of fleas and pits respectively.

The second line contains \(n\) integers, representing the initial coordinates of the fleas.

The third line contains \(m\) integers, representing the coordinates of the pits.

outputFormat

Output a single integer, representing the minimum number of rounds required to kill all the fleas.

sample

2 2
0 4
1 3

3