Wyspa

Limit pamięci: 32 MB

W Bajtlandii postanowiono zorganizować mecz pomiędzy dwiema zwaśnionymi drużynami piłkarskimi: Linuksowcami i Mikromiękkimi. Ponieważ kibice obu drużyn znani są z wzajemnej głębokiej antypatii, należy ich ulokować w miastach możliwie najdalej od siebie oddalonych i pozwolić na oglądanie meczu tylko w telewizji. Bajtlandia jest wyspą, a wszystkie jej miasta leżą na wybrzeżu. Wzdłuż brzegów wyspy biegnie dwukierunkowa autostrada, która łączy wszystkie miasta. Z każdego miasta do każdego innego można dojechać na dwa sposoby: w kierunku zgodnym z ruchem wskazówek zegara, i w kierunku przeciwnym. Długość krótszej z tych dróg jest odległością między miastami.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis wyspy,
• obliczy maksymalną odległość na jaką mogą zostać odseparowani kibice,
• zapisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia zapisana jest jedna dodatnia liczba całkowita , , oznaczająca liczbę miast znajdujących się na wyspie. W kolejnych wierszach zapisano długości odcinków autostrady pomiędzy sąsiednimi miastami. Każdy z tych wierszy zawiera jedną dodatnią liczbę całkowitą. W wierszu o numerze zapisana jest długość odcinka autostrady pomiędzy miastem o numerze , a miastem o numerze , natomiast w wierszu o numerze zapisana jest długość drogi pomiędzy miastem a . Całkowita długość autostrady nie przekracza .

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą oznaczającą maksymalną odległość na jaką mogą zostać odseparowani kibice.

Przykład

Dla danych wejściowych:

5
1
2
3
4
5

poprawną odpowiedzią jest:

7

Autor zadania: Piotr Chrząstowski.