DMOPC '23 Contest 1 P5 - Perfect Matching

View as PDF

Points: 25 (partial)
Time limit: 3.0s
Memory limit: 1G

Author:
Problem types

Alice is developing a new online dating app, DMOPC (DMOJ Modern Online Pairing Client). The app currently has users, guys and girls, where -th guy initially has a location of and the -th girl initially has a location of . We define the distance between the -th guy and the -th girl to be . Instead of allowing the users to browse through potential candidates, DMOPC overcomes this choice overload by matching every guy with exactly one girl and vice versa (such a matching is deemed a perfect matching). Furthermore, according to Alice's utilitarian ideals, Alice believes that the best matching does not need to account for the personalities of each user, but is rather one where the sum of the distances between the people in each matched pair — the inconvenience factor — is minimized.

Of course, the users of DMOPC are constantly on the move. At the -th minute, the -th guy and the -th girl swap locations. Initially and after each of minutes, help Alice compute the minimum inconvenience factor over all perfect matchings.

Constraints

All locations are pairwise distinct.

Input Specification

The first line contains integers and .

The second line contains integers .

The third line contains integers .

The next lines each contain integers and .

Output Specification

Output lines, the initial answer followed by the answers after each swap.

Sample Input

3 3
2 4 1
5 3 6
3 3
2 3
1 1

Sample Output

7
3
5
5

Explanation for Sample

Initially, the best matching is given by , where each pair represents matching the -th guy with the -th girl. This matching has an inconvenience factor of .

After the first swap, the best matching is given by . This matching has an inconvenience factor of .

After the second swap, the best matching is given by . This matching has an inconvenience factor of .

After the third swap, the best matching is given by . This matching has an inconvenience factor of .