8591번 - Tamy 다국어

W Bajtocji zbudowano wielki zbiornik wodny. Podzielono go na pewną liczbę jednakowej długości sektorów. Pomiędzy każdymi dwoma sąsiednimi sektorami znalazła się tama o pewnej wysokości. Tamy zbudowano także przed pierwszym oraz za ostatnim sektorem.

Obecnie poziom wody w całym zbiorniku jest taki sam. Ponieważ jednak zaczął padać ulewny deszcz, poziom wody zaczął szybko wzrastać. Król Bajtocji chce wiedzieć, ile czasu upłynie, zanim woda przeleje się przez pierwszą lub przez ostatnią tamę, wskutek czego pewnikiem dojdzie do zalania Bajtocji. Obliczenie tego utrudnia fakt, że nad każdym z sektorów deszcz może padać z różną intensywnością.

Pomóż królowi obliczyć czas, jaki pozostał do wylania się wody poza zbiornik. Jeżeli poziom wody jest równy dokładnie wysokości tamy, woda jeszcze się nie wylewa. Gdy część zbiornika już zalana wodą jest ograniczona z obu stron tamami tej samej wysokości, woda przelewa się z niej w obie strony równie szybko.

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą $n$ ($1 ≤ n ≤ 500\,000$), oznaczającą liczbę sektorów, na jakie podzielony jest zbiornik.

Drugi wiersz zawiera ciąg $n+1$ liczb całkowitych $w_i$ ($1 ≤ w_i ≤ 1\,000\,000$) pooddzielanych pojedynczymi odstępami, oznaczających wysokości (ponad początkowy poziom wody) kolejnych tam.

Trzeci wiersz zawiera ciąg $n$ liczb całkowitych $k_i$ ($1 ≤ k_i ≤ 1\,000\,000$) pooddzielanych pojedynczymi odstępami, oznaczających, o ile poziomów woda podnosi się w $i$-tym sektorze w ciągu jednej sekundy.

Pierwszy wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, będącą najmniejszą liczbą całkowitą nie mniejszą niż liczba sekund, po których woda wyleje się ze zbiornika.