409485: GYM103577 K Walking Tiles

Some tiles of the UNAL entrance are just a mess. Sometimes when you are walking and you step a tile with your right foot you get your left foot dirty because of the mud under the tiles. It literally splashes out and this is awful, you know? Just when you are wearing you best suit you get dirty because of this. Osman is fed up with this. That's why he is trying to solve this problem so walking at the UNAL can be better.

He achieved to map every tile of UNAL in a 2D map. Unfortunately, he has only information about a few of them. Some of the tiles are loose and others are fixed while the others are unknown.

You can step on a fixed tile and be sure you won't get dirty and similarly you can step on a loose tile and be sure that you will get dirty. For the other tiles, you can't be sure if you can step on without getting dirty.

So in order to get a better understanding of this map Osman needs you to help with calculating distances. Suppose you start in a loose tile, then, of course, you want to go the closest fixed tile and for that, you can only move in one of the 4 directions (front, left, right, back).

For example in the below image can walk 3 steps to the right and 1 front (the blue is fixed and the red is loose while the others are unknown). So the distance is 4.

You need to compute the sum of closest distances for each loose tile to its closest fixed tile.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2\times10^5$$$) — The number of loose and fixed tiles respectively.

The following $$$n$$$ lines contain a pair of numbers ($$$-10^9 \le x, y \le 10^9$$$) which indicated the row and column of each loose tile will contain (note that rows and columns can be negative).

The following $$$m$$$ lines contain a pair of numbers ($$$-10^9 \le x, y \le 10^9$$$) which indicated the row and column of each fixed tile will contain (note that rows and columns can be negative).

It's guaranteed that a tile can't be in both lists. Each tile can be either fixed, loose, or unknown.

Print one integer which is the sum of closest distances for each loose tile to any closest fixed tile.

1 1
0 0
3 1

4

5 5
3 1
3 9
0 6
5 0
8 9
10 7
3 2
4 10
1 6
6 1

10

3 3
0 2
4 6
0 0
1 0
6 4
7 1

8