문제
농부 존은 숫자 선 위에 특이한 패턴으로 소들과 상자들을 배치하는 과정을 사용한다:
농부 존은 정수 M(1 ≤ M ≤ 10^18)을 선택한다. 농부 존은 N(1 ≤ N ≤ 2⋅10^4)개의 구간 [Li, Ri]를 선택하여 소들을 배치하며 (1 ≤ Li ≤ Ri ≤ 10^18), 각 구간에서 Li, Li + M, Li + 2M, …, Ri의 위치에 소를 놓는다. Ri - Li는 M의 배수이다. 농부 존은 P(1 ≤ P ≤ 2⋅10^4)개의 구간 [Ai, Bi]를 선택하여 상자를 배치하며 (1 ≤ Ai ≤ Bi ≤ 10^18), 각 구간에서 Ai, Ai + M, Ai + 2M, …, Bi의 위치에 상자를 놓는다. Bi - Ai는 M의 배수이다. 소와 상자가 배치된 후, 농부 존은 소들이 모든 상자를 집어 드는 데 걸리는 최소 시간이 궁금하다. 매초마다 농부 존은 하나의 소에게 자신의 위치에서 왼쪽 혹은 오른쪽으로 한 칸 이동하라는 명령을 내릴 수 있다. 소가 상자가 있는 위치로 이동하면 그 상자를 주울 수 있다. 모든 상자를 줍는 데 걸리는 최소 시간을 구하라.
입력
첫째 줄에는 M, N, P가 주어진다.
다음 N개의 줄에는 각 줄마다 두 정수 Li와 Ri가 주어진다.
다음 P개의 줄에는 각 줄마다 두 정수 Ai와 Bi가 주어진다.
출력
모든 상자를 소들이 주워 드는 데 걸리는 최소 시간을 나타내는 정수 하나를 출력하라.
예제 #1
100 3 7
10 10
20 20
30 30
7 7
11 11
13 13
17 17
24 24
26 26
33 33
22
이 예제에서 농부 존은 다음과 같은 절차로 22초 안에 모든 상자를 집어 들 수 있다:
소 1을 왼쪽으로 3번 이동하여 상자 1을 줍는다.
소 3을 오른쪽으로 3번 이동하여 상자 7을 줍는다.
소 2를 오른쪽으로 4번 이동하여 상자 5를 줍는다.
소 1을 오른쪽으로 10번 이동하여 상자 2, 3, 4를 줍는다.
소 2를 오른쪽으로 2번 이동하여 상자 6을 줍는다.
예제 #2
2 1 1
1 5
2 6
3
소와 상자는 각각 3개씩 있다. 각 소를 오른쪽으로 한 번씩 이동시키면 된다.
로그인해야 코드를 작성할 수 있어요.