Skalniak

Limit pamięci: 32 MB

Wicehrabia de Bajteaux jest właścicielem znanej na całym świecie kolekcji głazów. Dotychczas utrzymywał ją w piwnicach swojego pałacu, lecz teraz postanowił wyeksponować kolekcję w swoim ogromnym ogrodzie.

Ogrody wicehrabiego mają kształt kwadratu o bokach długości jednostek. Boki kwadratu leżą w kierunkach wschód-zachód i północ-południe. Dla każdego głazu wicehrabia wyznaczył współrzędne punktu, w którym chciałby, żeby został on umiejscowiony (współrzędne te to odległości od południowego i zachodniego boku ogrodu), a następnie przekazał te informacje służącym. Niestety jednak zapomniał im powiedzieć, w jakiej kolejności podał współrzędne poszczególnych punktów. Dokładniej, współrzędne niektórych punktów mógł podać w kolejności odcięta-rzędna, a niektórych rzędna-odcięta. Nieświadomi tego faktu służący rozmieścili głazy zakładając, że kolejność podawania współrzędnych jest standardowa (odcięta-rzędna).

Wicehrabia postanowił zadbać o bezpieczeństwo swojej kolekcji i ogrodzić ją płotem, tworząc skalniak. Płot ze względów estetycznych ma mieć kształt prostokąta o bokach równoległych do boków ogrodu. Wicehrabia tak rozplanował uporządkowania współrzędnych punktów, żeby łączna długość potrzebnego płotu była jak najmniejsza (czyli spośród wszystkich uporządkowań par współrzędnych podanych punktów, uporządkowanie wicehrabiego wymaga minimalnej łącznej długości płotu). (Przyjmujemy przy tym, że prostokąt może mieć boki zerowej długości.)

Aby nie wyszła na jaw omyłkowa realizacja planu wicehrabiego, służący muszą poprzestawiać głazy tak, by długość potrzebnego do ich ogrodzenia płotu była najmniejsza możliwa. Każdy głaz mogą przestawić tylko tak, by jego nowe położenie miało takie same współrzędne jak aktualne, tylko w odwrotnej kolejności. Chcą się przy tym jak najmniej napracować, gdyż głazy są ciężkie. Chcieliby więc zminimalizować łączny ciężar przestawianych głazów.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia aktualne rozmieszczenie głazów w ogrodach wicehrabiego oraz ich ciężar,
• wyznaczy taki sposób poprzestawiania głazów, który umożliwi ogrodzenie ich jak najkrótszym płotem, a dodatkowo zminimalizuje łączny ciężar przestawianych głazów,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę głazów w kolekcji wicehrabiego. Kolejnych wierszy zawiera po trzy liczby całkowite , i (, ), pooddzielane pojedynczymi odstępami i oznaczające współrzędne aktualnego położenia i ciężar -tego głazu. Żadna para nieuporządkowana współrzędnych nie pojawi się na wejściu więcej niż raz.

Wyjście

Pierwszy wiersz wyjścia powinien zawierać dwie liczby całkowite, oddzielone pojedynczym odstępem - najmniejszą możliwą do osiągnięcia długość płotu i minimalny ciężar kamieni, jakie trzeba przemieścić, by taki wynik osiągnąć. Drugi wiersz powinien zawierać ciąg zer i/lub jedynek - -ty znak powinien być jedynką, jeżeli w optymalnym rozwiązaniu przemieszczamy -ty kamień, a zerem w przeciwnym przypadku. Jeżeli istnieje wiele poprawnych rozwiązań, Twój program powinien wypisać jedno z nich.

Przykład

Dla danych wejściowych:

5
2 3 400
1 4 100
2 2 655
3 4 100
5 3 277

poprawną odpowiedzią jest:

10 200
01010

Autorzy zadania: Marek Cygan i Jakub Radoszewski.