Problem description

– Lemurze podły. Wytłumacz swoją tu obecność! – krzyknął Skipper do Juliana – Kowalski, raport taktyczny! Jak pozbyć się tych wstrętnych lemurów?

Julian bez ogródek wszedł do pingwiniej bazy i zaczął się panoszyć. Wyciągnął już paczkę chrupek z Rico i rozsiadł się wygodnie przed telewizorem.

– Moris podnóżek! – powiedział Julian, po czym do bazy wszedł Moris, ulokował podnóżek w postaci Morta pod nogami Króla i zaczął go wachlować.

– Ssaki gadowe opuśćcie tę bazę już!

– Nie umiecie się dzielić? To się nauczcie. Moris podaj mi tę poduszkę.

– Nie udawaj głupiego, Ogoniasty!

– A jeśli nie udaję?

– Won! Precz!

Nie ma co owijać w bawełnę, że bezduszne lemury znęcają się bezdusznie nad biednymi pingwinami. Pingwiny postanowiły więc zrobić coś z tym faktem i dookoła swojej bazy zainstalować anty-ssakowo-przeciw-lemurowe zabezpieczenie. Takie zabezpieczenie składa się z N ustawionych w rzędzie i ponumerowanych kolejnymi liczbami naturalnymi od 1 do N ultradźwiękowych nadajników. Nadajnik o numerze i ma moc o wartości A_i. Dodatkowo moce nadajników są parami różne. Wydajność całego zabezpieczenia określa się jako sumę N − 1 wartości bezwzględnych różnic nadajników ustawionych przy sobie:

$$\sum^{N-1}_{i=1} |A_{i+1} - A_{i}|$$

Pingwiny zdobyły już wszystkie nadajniki. Muszą je jeszcze ustawić w odpowiedniej kolejności, która zmaksymalizuje wydajność zabezpieczenia. Sytuacja jednak nie jest taka prosta, ponieważ o tym, czy zabezpieczenie działa poprawnie, decyduje to, który z każdej pary sąsiednich nadajników ma większą moc. Dokładnie określone jest to w następujący sposób: i-ty nadajnik ma mieć mniejszą moc niż i + 1-wszy, gdy parametr zabezpieczenia B_i jest równy 1, a większą, gdy parametr zabezpieczenia B_i jest równy 0.

Twoim zdaniem jest pomóc pingwinom i napisać program, który na podstawie mocy poszczególnych nadajników oraz parametrów zabezpieczenia wyznaczy jego maksymalną wydajność, możliwą do uzyskania.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N oznaczająca liczbę nadajników. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych A_i, pooddzielanych pojedynczymi odstępami i oznaczających moce poszczególnych nadajników ultradźwiękowych. W trzecim wierszu wejścia znajduje się ciąg N − 1 liczb naturalnych B_i, pooddzielanych pojedynczymi odstępami i oznaczających kolejne parametry zabezpieczenia.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba naturalna – maksymalna wydajność zabezpieczenia, możliwa do uzyskania.

Ograniczenia

1 ≤ N ≤ 300 000, 1 ≤ A_i ≤ 10⁹, 0 ≤ B_i ≤ 1.

Przykład

4
1 2 3 4
1 0 1

7

10
5 10 20 8 30 100 7 1 4 42
0 0 1 1 1 0 1 1 0

299

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.