대피 계획

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

요약

직선 위의 n개 팀 위치와 m개 대피소 위치가 주어질 때, 모든 대피소가 최소 한 팀씩 배정받으면서 총 이동 거리를 최소화하는 값을 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 정렬, 그리디
정답자: 아직 제출이 없습니다

문제

한 정부가 직선 형태의 고속도로를 건설하고 있습니다. 이 고속도로 위의 서로 다른 지점에서 $n$ 개의 건설팀이 작업하고 있습니다.

비상 상황에 대비하여, 각 건설팀을 어느 대피소로 이동시킬지 정하는 대피 계획을 세워야 합니다. 고속도로 근처에는 $m$ 개의 대피소가 있습니다. 모든 건설팀은 정확히 하나의 대피소에 배정되며, 각 대피소는 안에서 문을 잠가야 하므로 적어도 한 팀 이상이 사용해야 합니다 (비어 있는 대피소가 있으면 안 됩니다).

위치 $x$ 에 있는 팀이 위치 $y$ 의 대피소로 이동하는 데 필요한 연료의 양은 $|x - y|$ 입니다. 가능한 모든 배정 중에서 총 연료 사용량이 최소가 되도록 배정했을 때, 그 최소 총 연료량을 구하세요.

입력

첫째 줄에 건설팀의 수 $n$ 이 주어집니다 ( $1 \le n \le 4000$ ).

둘째 줄에 $n$ 개의 정수가 주어지며, 각 팀의 위치를 나타냅니다. 모든 위치는 서로 다른 양의 정수이고 $10^9$ 을 넘지 않습니다.

셋째 줄에 대피소의 수 $m$ 이 주어집니다 ( $1 \le m \le n$ ).

넷째 줄에 $m$ 개의 정수가 주어지며, 각 대피소의 위치를 나타냅니다. 모든 위치는 서로 다른 양의 정수이고 $10^9$ 을 넘지 않습니다.

위치 $x$ 의 팀이 위치 $y$ 의 대피소로 이동할 때 필요한 연료는 $|x - y|$ 입니다.

출력

모든 팀이 대피소에 배정되고 모든 대피소가 적어도 한 팀에게 사용될 때 필요한 최소 총 연료량을 정수 하나로 출력합니다.

실제 배정 방법은 출력할 필요가 없습니다.

예제4

예제 1
입력
```
3
1 2 3
2
2 10
```
예상 출력
```
8
```
예제 2
입력
```
1
5
1
8
```
예상 출력
```
3
```
예제 3
입력
```
5
1 2 3 4 5
2
1 5
```
예상 출력
```
4
```
예제 4
입력
```
4
1 2 3 4
4
4 3 2 1
```
예상 출력
```
0
```