BOJ 23507 Marbles

문제 링크:

문제 내용

길이 $L$의 트랙 위에 $N$개의 구슬과 $N$개의 스위치가 있습니다. 구슬과 스위치의 크기는 무시할 수 있습니다. 시각 0에 모든 구슬이 왼쪽이나 오른쪽 중 한 방향으로 구르기 시작합니다. 모든 구슬의 속력은 단위 시간 당 1 단위 길이이며, 구슬이 최초에 굴러갈 방향은 사전에 정할 수 있습니다.

두 구슬이 충돌하면 즉시 서로 반대 방향으로 같은 속력으로 움직입니다. 한 구슬이 트랙의 양 끝에 닿으면 반대 방향으로 움직이는데, 좌표 1에서 1로 돌아오는데, 그리고 좌표 $L$에서 $L$로 돌아오는데 각각 1 단위 시간이 걸립니다. 스위치는 구슬과 상호작용을 하지 않습니다.

각 구슬의 굴러갈 방향을 적절히 정해서 어떤 시점에 모든 스위치 위에 정확히 하나의 구슬이 오도록 하려고 합니다. 그것이 가능하다면 이를 달성하는 데 필요한 최소 시간을 구하세요.

입력

첫 줄에는 정수 $L$과 $N$이 주어집니다. ($1 \le L \le 10^9$, $1 \le N \le 3000$)

두 번째 줄에는 구슬의 위치 $A_1, A_2, \cdots, A_N$이 주어집니다. 이들은 모두 정수이며, 모두 서로 다릅니다.

세 번째 줄에는 스위치의 위치 $B_1, B_2, \cdots, B_N$이 주어집니다. 이들은 모두 정수이며, 모두 서로 다릅니다.

출력

문제의 정답을 출력합니다. 그러한 방법이 존재하지 않을 경우 -1을 대신 출력합니다.

문제 풀이