In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.
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ż
.
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą - czas przejazdu między najbardziej odległą parą miast Bajtokręgu.
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.