시간 제한
메모리 제한
시간 제한
1초
메모리 제한
128 MB
한 정부가 직선 형태의 고속도로를 건설하고 있습니다. 이 고속도로 위의 서로 다른 지점에서 n개의 건설팀이 작업하고 있습니다.
비상 상황에 대비하여, 각 건설팀을 어느 대피소로 이동시킬지 정하는 대피 계획을 세워야 합니다. 고속도로 근처에는 m개의 대피소가 있습니다. 모든 건설팀은 정확히 하나의 대피소에 배정되며, 각 대피소는 안에서 문을 잠가야 하므로 적어도 한 팀 이상이 사용해야 합니다 (비어 있는 대피소가 있으면 안 됩니다).
위치 x에 있는 팀이 위치 y의 대피소로 이동하는 데 필요한 연료의 양은 ∣x−y∣입니다. 가능한 모든 배정 중에서 총 연료 사용량이 최소가 되도록 배정했을 때, 그 최소 총 연료량을 구하세요.
첫째 줄에 건설팀의 수 n이 주어집니다 (1≤n≤4000).
둘째 줄에 n개의 정수가 주어지며, 각 팀의 위치를 나타냅니다. 모든 위치는 서로 다른 양의 정수이고 109을 넘지 않습니다.
셋째 줄에 대피소의 수 m이 주어집니다 (1≤m≤n).
넷째 줄에 m개의 정수가 주어지며, 각 대피소의 위치를 나타냅니다. 모든 위치는 서로 다른 양의 정수이고 109을 넘지 않습니다.
위치 x의 팀이 위치 y의 대피소로 이동할 때 필요한 연료는 ∣x−y∣입니다.
모든 팀이 대피소에 배정되고 모든 대피소가 적어도 한 팀에게 사용될 때 필요한 최소 총 연료량을 정수 하나로 출력합니다.
실제 배정 방법은 출력할 필요가 없습니다.