Gazociągi

Limit pamięci: 32 MB

Koncern GazBit zamierza zdominować rynek gazowy w Bajtocji. Specjaliści umiejscowili już na mapie Bajtocji optymalne położenia punktów wydobycia gazu oraz stacji dystrybucji gazu - pozostało jeszcze tylko przyporządkować stacje do punktów wydobycia. Każda stacja dystrybucji ma być połączona z dokładnie jednym punktem wydobycia i odwrotnie, każdy punkt wydobycia z dokładnie jedną stacją.

GazBit specjalizuje się w budowie gazociągów prowadzących z punktów wydobycia do stacji dystrybucji w kierunku południowym i wschodnim - dokładniej, każdy wybudowany gazociąg ma (patrząc z lotu ptaka) kształt łamanej, której każda kolejna część biegnie w kierunku południowym lub wschodnim i jest prostopadła do poprzedniej. Zarząd koncernu zastanawia się, jak przyporządkować punktom wydobycia gazu stacje dystrybucji tak, by zminimalizować łączną długość koniecznych do wybudowania gazociągów. Przy planowaniu można pominąć problem przecinania się gazociągów - ich kolidujące fragmenty zostaną umieszczone na różnych głębokościach pod ziemią.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia planowane położenia punktów wydobycia i stacji dystrybucji gazu,
• wyznaczy takie przyporządkowanie stacji dystrybucji do punktów wydobycia, które pozwala na wybudowanie gazociągów o minimalnej łącznej długości,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę punktów wydobycia (równą liczbie stacji dystrybucji). Kolejne wierszy zawiera po dwie liczby całkowite i ( dla ), oddzielone pojedynczym odstępem i oznaczające współrzędne na mapie punktów wydobycia gazu. Przyjmujemy, że wraz z rosnącą współrzędną poruszamy się na wschód, a wraz z rosnącą współrzędną poruszamy się na północ. Następne wierszy zawiera po dwie liczby całkowite i ( dla ), oddzielone pojedynczym odstępem i oznaczające współrzędne na mapie stacji dystrybucji gazu. Zarówno punkty wydobycia, jak i stacje dystrybucji numerujemy liczbami naturalnymi od 1 do w kolejności występowania na wejściu. Żadna para współrzędnych nie powtórzy się w jednym zestawie danych wejściowych. Ponadto dla każdych danych wejściowych istnieje jakieś przyporządkowanie punktom wydobycia stacji dystrybucji, które można zrealizować za pomocą gazociągów idących tylko na południe i wschód.

Wyjście

Pierwszy wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą minimalną sumaryczną długość wszystkich koniecznych do wybudowania gazociągów. Dalej na wyjściu powinien wystąpić przykładowy opis przyporządkowania stacji punktom wydobycia, który realizuje to minimum. Każdy z kolejnych wierszy powinien zawierać dwie liczby całkowite, oddzielone pojedynczym odstępem i oznaczające numery punktu wydobycia i stacji dystrybucji, które powinny być połączone gazociągiem. Kolejność wypisywania przyporządkowań może być dowolna. Jeżeli istnieje wiele poprawnych rozwiązań, Twój program powinien wypisać jakiekolwiek z nich.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

9
2 3
1 2
3 1

Autor zadania: Jakub Radoszewski.