23507번 - Marbles 다국어

You are given a track of length $L$. On it there are $N$ marbles at positions $A_1,A_2\cdots,A_N$  and $N$ switches at positions $B_1,B_2,\cdots,B_N$, both of negligably small size. In the beginning, you direct each marble left or right and they all start moving at the constant speed of $1$ in the given direction. When two marbles collide, they bounce off each other elastically, meaning that they continue moving in opposite directions at the same speed. If a marble collides with the beginning or end of the track it bounces off with the same speed in the opposite direction. Keep in mind that it takes exactly one second for a marble at position $i$ to travel to the position $i+1$ or $i-1$, and it also takes exactly one second to travel from $1$ back to $1$ while changing directions, or to travel from $L$ back to $L$ while changing directions. Note that marbles never stop on the switches.

The goal is to have a marble on top of every switch, i.e. to have all marbles simultaneously on the corresponding switches.

You need to find the minimum amount of time needed to achieve this.

In the first line of input you are given $L$ ($L\le 10^9$) and $N$ ($N\le3000$)

In the second line of input you are given $A_1,A_2\cdots,A_N$, the initial positions of the marbles. All $A_i$ are guaranteed to be distinct, and $1\le A_i\le L$.

In the second line of input you are given $B_1,B_2\cdots,B_N$, the initial positions of the marbles. All $B_i$ are guaranteed to be distinct, and $1\le B_i\le L$.

Print one integer: the minimum amount of time to have a marble on top of every switch. If solution does not exist, print $-1$.