#agc034d. [agc034_d]Manhattan Max Matching
[agc034_d]Manhattan Max Matching
Problem Statement
Snuke is playing with red and blue balls, placing them on a two-dimensional plane.
First, he performed operations to place red balls. In the -th of these operations, he placed red balls at coordinates . Then, he performed another operations to place blue balls. In the -th of these operations, he placed blue balls at coordinates . The total number of red balls placed and the total number of blue balls placed are equal, that is, . Let this value be .
Snuke will now form pairs of red and blue balls so that every ball belongs to exactly one pair. Let us define the score of a pair of a red ball at coordinates and a blue ball at coordinates as .
Snuke wants to maximize the sum of the scores of the pairs. Help him by finding the maximum possible sum of the scores of the pairs.
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the maximum possible sum of the scores of the pairs.
Sample Input 1
Sample Output 1
If we pair the red ball at coordinates and the blue ball at coordinates , the score of this pair is . Then, if we pair the red ball at coordinates and the blue ball at coordinates , the score of this pair is . Making these two pairs results in the total score of , which is the maximum result.
Sample Input 2
Sample Output 2
Snuke may have performed multiple operations at the same coordinates.