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 Gi, Fi, i=1,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 va conţ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 Gx Gy, 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 Fx Fy, 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 pe prima linie un număr natural m reprezentând partea întreagă a costului minim total al conductelor.
Restricţii
1 < n < 13
0 <= Gx, Gy, Fx, Fy <= 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.