Bajtokrąg
Limit pamięci: 128 MB
Bajtokrąg składa się z miast, ponumerowanych liczbami od 0 do
i rozmieszczonych w specyficzny sposób.
Dokładnie
z nich leży na okręgu - są to kolejno miasta o numerach
.
Pary kolejnych miast na okręgu połączone są dwukierunkowymi drogami.
Stolica Bajtokręgu (miasto o numerze 0) leży w samym środku okręgu i jest połączona drogami ze wszystkimi innymi miastami.
Znamy czas przejazdu każdą drogą w Bajtokręgu. Władze Bajtokręgu chciałyby ułatwić mieszkańcom komunikację między miastami. W tym celu chcą wybrać dwa najbardziej oddalone miasta (w sensie czasu przejazdu między nimi) i wybudować w nich lotniska.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (
), oznaczającą liczbę miast Bajtokręgu.
Drugi wiersz zawiera
liczb całkowitych dodatnich oznaczających czas przejazdu między kolejnymi miastami na okręgu (tzn.
-ta liczba oznacza czas przejazdu między miastem o numerze
i następnym w kolejności miastem na okręgu).
Trzeci wiersz zawiera
liczb całkowitych dodatnich oznaczających czas przejazdu między stolicą a miastami na okręgu
(tzn.
-ta liczba oznacza czas przejazdu między stolicą a miastem o numerze
).
Zakładamy, że suma wszystkich czasów przejazdu między sąsiednimi miastami jest nie większa niż
.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą - czas przejazdu między najbardziej odległą parą miast Bajtokręgu.
Przykład
Dla danych wejściowych:
6 1 4 5 1 6 3 5 1 8 2
poprawną odpowiedzią jest:
7
Wyjaśnienie do przykładu: Para najbardziej oddalonych miast to (2, 4), a czas przejazdu między nimi wynosi 7. W tych właśnie miastach należy wybudować lotniska.