피자

시간 제한2초메모리 제한128 MB

요약
원형 도로 위 상점 위치들과 배달 지점들이 주어질 때, 각 지점에서 가장 가까운 상점까지의 거리 합을 구한다.
난이도

보통10점 중 4점

유형
이분 탐색, 배열, 정렬
정답자
아직 제출이 없습니다

문제

JOI 피자는 도시 중심부를 지나는 전체 길이 dd 미터의 환상선(원형 도로) 위에서 피자 배달을 한다.

JOI 피자는 환상선 위에 nn개의 점포 S1,…,SnS_1, \dots, S_n을 가지고 있으며, 본점은 S1S_1이다. S1S_1에서 SiS_i까지 시계 방향으로 환상선을 따라 이동했을 때의 거리를 did_i 미터라고 하자. d2,…,dnd_2, \dots, d_n은 11 이상 d−1d-1 이하의 정수이며, 모두 서로 다르다.

주문이 들어오면 피자가 식지 않도록, 배달지까지의 이동 거리가 가장 짧은 점포에서 피자를 구워 배달한다.

배달지의 위치는 00 이상 d−1d-1 이하의 정수 kk로 나타낸다. 이는 본점 S1S_1에서 배달지까지 시계 방향으로 환상선을 따라 이동했을 때의 거리가 kk 미터임을 의미한다. 배달은 반드시 환상선을 따라 이루어지며 다른 길로는 갈 수 없지만, 환상선 위에서는 시계 방향으로 이동해도 되고 반시계 방향으로 이동해도 된다. 따라서 어떤 점포에서 배달지까지의 거리는 두 방향의 거리 중 더 짧은 쪽이다.

예를 들어 점포와 배달지의 위치가 아래 그림과 같은 경우를 생각하자.

첫 번째 배달지에 가장 가까운 점포는 S2S_2이므로 S2S_2에서 배달하며, 이때 점포로부터의 이동 거리는 11이다. 두 번째 배달지에 가장 가까운 점포는 본점 S1S_1이므로 S1S_1에서 배달하며, 이때 이동 거리는 22이다.

환상선의 전체 길이 dd, 점포의 개수 nn, 주문의 개수 mm, 본점을 제외한 점포의 위치를 나타내는 n−1n-1개의 정수 d2,…,dnd_2, \dots, d_n, 그리고 각 배달지의 위치를 나타내는 정수 k1,…,kmk_1, \dots, k_m이 주어질 때, 모든 주문에 대한 배달 이동 거리(가장 가까운 점포에서 배달지까지의 거리)의 총합을 구하는 프로그램을 작성하시오.

입력

입력은 다음 형식으로 주어진다.

  • 첫째 줄: 환상선의 전체 길이를 나타내는 정수 dd (2≤d≤1092 \le d \le 10^9).
  • 둘째 줄: 점포의 개수를 나타내는 정수 nn (2≤n≤1000002 \le n \le 100000).
  • 셋째 줄: 주문의 개수를 나타내는 정수 mm (1≤m≤100001 \le m \le 10000).
  • 이어지는 n−1n-1개의 줄: 본점을 제외한 점포의 위치 d2,d3,…,dnd_2, d_3, \dots, d_n (1≤di≤d−11 \le d_i \le d-1)이 이 순서대로 한 줄에 하나씩 주어진다. 이 값들은 모두 서로 다르다.
  • 그다음 mm개의 줄: 배달지의 위치 k1,k2,…,kmk_1, k_2, \dots, k_m (0≤ki≤d−10 \le k_i \le d-1)이 이 순서대로 한 줄에 하나씩 주어진다.

출력

배달 이동 거리의 총합을 나타내는 정수 하나만을 한 줄에 출력한다.

예제5

  1. 예제 1

    입력
    8
    3
    2
    3
    1
    4
    6
    
    예상 출력
    3
    
  2. 예제 2

    입력
    20
    4
    4
    12
    8
    16
    7
    7
    11
    8
    
    예상 출력
    3
    
  3. 예제 3

    입력
    2
    2
    1
    1
    0
    
    예상 출력
    0
    
  4. 예제 4

    입력
    10
    3
    3
    4
    7
    0
    5
    9
    
    예상 출력
    2
    
  5. 예제 5

    입력
    100
    2
    2
    50
    99
    1
    
    예상 출력
    2