Evacuation Plan

Time limit1sMemory limit128 MB

Summary

Given n team positions and m shelter positions on a line, find the minimum total distance assignment where every shelter gets at least one team.

Level: Medium6 of 10
Topics: Dynamic programming, Sorting, Greedy
Solved: No attempts yet

Problem

A government is building a highway that runs along a straight line. There are $n$ construction teams working at distinct points on it.

To prepare for an emergency, the office must design an evacuation plan that assigns every team to a shelter. There are $m$ shelters located near the highway. Each team is assigned to exactly one shelter, and because every shelter has to be locked from the inside, each shelter must be used by at least one team (no shelter may be left empty).

The amount of fuel a team at position $x$ needs to reach a shelter at position $y$ is $|x - y|$ . Among all valid assignments, find the one that minimizes the total fuel used and report that minimum total fuel.

Input

The first line contains the number of construction teams $n$ ( $1 \le n \le 4000$ ).

The second line contains $n$ integers, the locations of the teams. All locations are distinct positive integers not exceeding $10^9$ .

The third line contains the number of shelters $m$ ( $1 \le m \le n$ ).

The fourth line contains $m$ integers, the locations of the shelters. All locations are distinct positive integers not exceeding $10^9$ .

The fuel needed for a team at position $x$ assigned to a shelter at position $y$ is $|x - y|$ .

Output

Print a single integer: the minimum total fuel needed so that every team is assigned to a shelter and every shelter is used by at least one team.

You do not need to output the actual assignment.

Examples4

Example 1
Input
```
3
1 2 3
2
2 10
```
Expected output
```
8
```
Example 2
Input
```
1
5
1
8
```
Expected output
```
3
```
Example 3
Input
```
5
1 2 3 4 5
2
1 5
```
Expected output
```
4
```
Example 4
Input
```
4
1 2 3 4
4
4 3 2 1
```
Expected output
```
0
```