LKP '18 Contest 1 P6 - The Great Fire of Köres

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.2s
Memory limit: 256M

Authors:
Problem type

The Great Forest of Köres has been set ablaze, leading to one of the greatest forest fires in all of recorded history. The country of Werłantž, which presides over the forest had luckily foreseen the event and built bunkers, where the residents of the Great Forest of Köres may escape to. There are N communities of similar size living in the forest, and there are M such bunkers. Since trees are blocking most of the paths in the forest, it is only possible to travel in axis-aligned directions. Each community will travel to a bunker such that they have to travel the minimal distance possible. As each bunker is large enough to hold all N communities, any number of communities can travel to the same bunker. The country of Werłantž asks you to determine the total distance travelled by all N communities.

Constraints

1 \le N, M \le 100\,000
The coordinates of all of the locations are less than or equal to 10^9 in absolute value.

Subtask 1 [10%]

1 \le N, M \le 1\,000

Subtask 2 [20%]

The coordinates of all locations are less than or equal to 1\,000 in absolute value.

Subtask 3 [70%]

No additional constraints.

Input Specification

The first line contains the integer N.
N lines follow, the ith of which contains two integers, the x and y coordinates of the ith community.
The next line contains the integer M.
M lines follow, the ith of which contains two integers, the x and y coordinates of the ith bunker.

Output Specification

Output one integer, the sum of the distances traveled by all of the communities.

Sample Input

3
1 1
2 2
3 1
2
0 0
4 0

Sample Output

8

Comments

There are no comments at the moment.