Ants

Time limit3sMemory limit128 MB

Summary

Find the minimum-cost perfect matching between n points and n points using squared Euclidean distance as edge weight.

Level: Medium7 of 10
Topics: Graph, Math, Dynamic programming
Solved: No attempts yet

Problem

Young naturalist Bill studies ants at school. His ants feed on plant lice (aphids) that live on apple trees, and each ant colony needs its own apple tree to feed from.

Bill has a map with the coordinates of $n$ ant colonies and $n$ apple trees. He wants to connect each ant colony to exactly one apple tree so that every colony is paired with a distinct tree.

The cost of connecting a colony located at $(x_c, y_c)$ to an apple tree located at $(x_t, y_t)$ is the squared Euclidean distance between them:

$(x_c - x_t)^2 + (y_c - y_t)^2.$

Among all ways to pair the $n$ colonies with the $n$ apple trees one-to-one, find the minimum possible total cost.

In the picture, ant colonies are drawn as empty circles and apple trees as filled circles; the lines show one possible pairing.

Input

The first line contains a single integer $n$ ( $1 \le n \le 100$ ) — the number of ant colonies and apple trees.

The next $n$ lines describe the ant colonies, and the following $n$ lines describe the apple trees. Each colony and each tree is given by a pair of integer coordinates $x$ and $y$ ( $-10\,000 \le x, y \le 10\,000$ ) on the Cartesian plane. All $2n$ points are distinct.

Output

Print a single integer: the minimum total cost of pairing every ant colony with a distinct apple tree, where the cost of one connection is the squared Euclidean distance between the colony and the tree.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
1
0 0
3 4
```
Expected output
```
25
```
Example 3
Input
```
2
0 0
6 6
6 5
1 1
```
Expected output
```
3
```