seceta

Grădinile roditoare ale Bărăganului suferă anual pierderi imense din cauza secetei.

Căutătorii de apă au găsit $n$ fântâni din care doresc să alimenteze $n$ grădini. Fie $G_i$, $F_i$, $i=1 \ldots n$ puncte în plan reprezentând puncte de alimentare ale grădinilor şi respectiv punctele în care se află fântânile. Pentru fiecare punct se dau coordonatele întregi $(x,y)$ în plan. Pentru a economisi materiale, legătura dintre o grădină şi o fântână se realizează printr-o conductă în linie dreaptă. Fiecare fântână alimentează o singură grădină. Consiliul Judeţean Galaţi plăteşte investiţia cu condiţia ca lungimea totală a conductelor să fie minimă. Fiecare unitate de conductă costă $100$ lei noi (RON).

Cerință

Să se determine $m$, costul minim total al conductelor ce leagă fiecare grădină cu exact o
fântână.

Date de intrare

Fişierul de intrare seceta.in vaconţine:

Pe prima linie se află numărul natural $n$, reprezentând numărul grădinilor şi al fântânilor.

Pe următoarele $n$ linii se află perechi de numere întregi $G_x \ G_y$, separate printr-un spaţiu, reprezentând coordonatele punctelor de alimentare ale grădinilor.

Pe următoarele $n$ linii se află perechi de numere întregi $F_x \ F_y$, separate printr-un spaţiu, reprezentând coordonatele punctelor fântânilor.

Date de ieșire

Fişierul de ieşire seceta.out va conţine: $m$ un număr natural reprezentând partea întreagă a costului minim total al conductelor.

Restricții și precizări

• $1 < n < 13$
• $0 \leq G_x, G_y, F_x, F_y \leq 200$
• Nu există trei puncte coliniare, indiferent dacă sunt grădini sau fântâni
• Orice linie din fişierele de intrare şi ieşire se termină prin marcajul de sfârşit de linie

Exemplu

seceta.in

3
1 4
3 3
4 7
2 3
2 5
3 1

seceta.out

624

Explicație

Costul minim este $[6.24264 \cdot 100]=624$ prin legarea perechilor:

Grădini: $(1 \ 4) \ (3 \ 3) \ (4 \ 7)$

Fantani: $(2 \ 3) \ (3 \ 1) \ (2 \ 5)$