시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 76 15 12 35.294%

문제

둘레의 길이가 \(L\)인 원형 레일이 있다. 경근이는 레일을 \(L\)등분하여 각 지점에 시계방향으로 \(0\)에서 \(L-1\)까지의 번호를 붙였다. 그리고 번호를 붙인 지점 중 몇 개를 선택하여 시계방향으로 레일 위를 움직이는 개미 \(N\)마리와 반시계방향으로 레일 위를 움직이는 개미 \(M\)마리를 놓았다. 이 때 같은 지점에 두 마리 이상의 개미가 있는 경우는 없다.

레일 위에 올라온 모든 개미는 1초에 1의 거리를 움직인다. 레일의 폭은 최대 한 마리의 개미만이 움직일 수 있을 정도로 매우 좁아서, 서로 반대방향으로 움직이는 개미들이 어느 한 위치에서 부딪치고 난 다음에는 그 즉시 서로 방향을 반대로 바꾸어 움직인다. 개미의 크기는 매우 작아서 점으로 취급하여, 정확히 같은 위치에 존재하게 되어야 부딪친다고 하자.

경근이는 모든 개미를 구별할 수 있어서, 모든 개미가 처음과 같은 위치에서 같은 속도를 가지게 되려면 최소한 몇 초가 필요한지 궁금해졌다. 경근이를 도와 이 시간이 몇 초인지 알려주는 프로그램을 작성하라.

입력

첫 번째 줄에 원형 레일의 둘레를 의미하는 \(L\), 시계방향으로 레일 위를 움직이는 개미의 수를 의미하는 \(N\), 반 시계방향으로 레일 위를 움직이는 개미의 수를 의미하는 \(M\)이 공백으로 구분되어 주어진다.

두 번째 줄에는 시계방향으로 움직이는 개미들이 있는 지점을 의미하는 \(N\)개의 정수가 공백으로 구분되어 주어진다.

세 번째 줄에는 반시계방향으로 움직이는 개미들이 있는 지점을 의미하는 \(M\)개의 정수가 공백으로 구분되어 주어진다.

이 문제는 두 개의 부분 문제로 이루어져 있다.

1번 문제의 입력은 \(1 \leq L \leq 600\), \(1 \leq N, M, N+M\leq 600\)을 만족하며 해결하면 20점을 얻을 수 있다.

2번 문제의 입력은 \(1 \leq L \leq 10^{12}\), \(1 \leq N, M, N+M\leq 10^6\)을 만족하며 해결하면 80점을 얻을 수 있다.

출력

첫 번째 줄에 모든 개미들이 처음과 같은 위치, 같은 속도를 가지게 되려면 최소한 몇 초가 필요한지 출력하라.

예제 입력

2 1 1
0
1

예제 출력

2

힌트

0.5초와 1.5초에 부딪친 후 2초가 되면 처음과 같은 상태가 된다.

출처

Contest > Coder's High > Coder's High 2015 Side Contest A2번