Wyspy

Limit pamięci: 128 MB

Właśnie odwiedzasz park, w którym znajduje się wysp. Kiedy budowano park, z każdej wyspy został poprowadzony jeden most - długość mostu wychodzącego z wyspy oznaczamy przez . Łącznie w parku jest mostów. Każdym mostem można poruszać się w obu kierunkach (choć każdy most miał swój początek na jednej wyspie). Ponadto, dowolne dwie wyspy są połączone promem pływającym pomiędzy nimi w tę i z powrotem.

Ponieważ wolisz spacerować niż pływać promami, chcesz zmaksymalizować sumę długości mostów, którymi przejdziesz, stosując się do ograniczeń podanych poniżej.

• Możesz rozpocząć zwiedzanie parku od dowolnej wyspy.
• Nie możesz odwiedzić żadnej wyspy więcej niż raz.
• W każdej chwili możesz przemieścić się z wyspy , na której aktualnie się znajdujesz, na inną wyspę , której nie odwiedzałeś wcześniej. Ruch z do możesz wykonać na jeden ze sposobów:
  • Idąc: Możliwe jedynie wtedy, gdy istnieje most łączący obie wyspy. W tym przypadku długość mostu zostaje dodana do łącznej długości pokonanej trasy.
  • Promem: Możesz wybrać ten wariant tylko wtedy, jeśli nie jest osiągalne z przy użyciu dowolnej kombinacji mostów i/lub wcześniej użytych promów. (Przy sprawdzaniu osiągalności należy wziąć pod uwagę wszystkie ścieżki, także te prowadzące przez wyspy wcześniej odwiedzone.)

Zauważ, że nie musisz odwiedzić wszystkich wysp, a przejście wszystkimi mostami może okazać się niemożliwe.

Zadanie

Napisz program, który mając dany opis mostów wraz z ich długościami, wyznaczy maksymalną możliwą do przejścia odległość, zgodnie z zasadami opisanymi powyżej.

Ograniczenia

- liczba wysp w parku;
- długość mostu o numerze .

Wejście

Twój program powinien wczytać ze standardowego wejścia następujące dane:

• Pierwszy wiersz zawierający liczbę całkowitą - liczbę wysp w parku. Wyspy są ponumerowane liczbami od do włącznie.
• Każdy z kolejnych wierszy opisuje most - -ty z nich zawiera dwie liczby całkowite oddzielone pojedynczym odstępem, opisujące most wychodzący z wyspy o numerze . Pierwsza z tych liczb to numer wyspy po drugiej stronie mostu, a druga to długość tego mostu. Możesz założyć, że każdy most jest rozpięty pomiędzy dwiema różnymi wyspami.

Wyjście

Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający jedną liczbę całkowitą - maksymalną możliwą do przejścia odległość.
UWAGA 1: Dla niektórych testów odpowiedź nie zmieści się w 32-bitowym typie całkowitym, możesz potrzebować typów int64 w Pascalu lub long long w C/C++, aby uzyskać pełną liczbę punktów za to zadanie.
UWAGA 2: Podczas uruchamiania programów napisanych w Pascalu w środowisku zawodów, liczby 64-bitowe są wczytywane ze standardowego wejścia znacząco wolniej niż liczby 32-bitowe, nawet gdy wczytywane wartości i tak mieszczą się w 32 bitach. Zalecamy wczytywanie danych do typów 32-bitowych.

Punktacja

W pewnych testach wartych 40 punktów, nie przekracza .

Przykład

Dla danych wejściowych:

7
3 8
7 2
4 2
1 4
1 9
3 4
2 3

poprawną odpowiedzią jest:

24

mostów z przykładu to (1-3), (2-7), (3-4), (4-1), (5-1), (6-3) i (7-2). Zauważmy, że istnieją dwa różne mosty pomiędzy wyspami 2 i 7.
Oto jedna z dróg realizujących maksymalną odległość, jaką można przejść:

• Zacznij od wyspy 5.
• Przejdź mostem długości 9 na wyspę 1.
• Przejdź mostem długości 8 na wyspę 3.
• Przejdź mostem długości 4 na wyspę 6.
• Przepłyń promem z wyspy 6 na wyspę 7.
• Przejdź mostem długości 3 na wyspę 2.

Jedyną nieodwiedzoną wyspą jest 4. Zauważmy, że nie można jej już odwiedzić po pokonaniu powyższej trasy. Dokładniej:

• Nie jesteś w stanie odwiedzić jej pieszo, gdyż nie ma mostu łączącego wyspę 2 (gdzie obecnie jesteś) z wyspą 4.
• Nie możesz przepłynąć na nią promem, gdyż wyspa 4 jest osiągalna z wyspy 2, na której aktualnie jesteś. Możliwa droga do niej to: przejście mostem (2-7), potem użytym już poprzednio promem z wyspy 7 na wyspę 6, następnie mostem (6-3) i ostatecznie mostem (3-4).