3. Eww, niečo je tu rozliate

KSPáci boli na chate a keďže málo z nich má plne vyvinutú jemnú motoriku, tak sa im na schodoch vždy podarí niečo vyliať. Na polke schodu je lekvár, na druhej zas Kofola™. Na ďalšom zas Nutella™ a kečup…

Filipkovi síce nepadajú veci z rúk ale za to si na chatu zvládol zobrať len jeden pár ponožiek. Chcel by sa teda večer dostať do izby, s čo najmenej zašpinenými ponožkami. Viete mu s tým pomôcť?

Úloha

Chata má n schodov. Každý schod má dve polovice. Na každej polovici je rozliate niečo, čo Filipkovi zašpiní ponožky. Pre každý schod teda poznáme dve čísla:

• ľavá strana: koľko špiny spôsobí, keď na ňu stúpi
• pravá strana: to isté, ale pre pravú polovicu

Filipko môže na začiatku začať buď na prvom alebo druhom schode, a ľubovoľnou nohou (ľavou alebo pravou). Potom ide hore po schodoch, pričom sa môže pohnúť buď o jeden schod (napr. zo schodu 2 na 3) alebo dva schody (napr. z 2 na 4). Musí striedať nohy – ak posledný krok spravil ľavou, ďalší musí pravou, a naopak. Musí skončiť presne na poslednom schode (čiže sa nesmie zastaviť skôr ani ho preskočiť).

Vašou úlohou je zistiť, aké najmenšie množstvo zašpinenia ponožiek môže Filipko utrpieť, ak sa chce po zafŕkaných schodoch dostať z dolného poschodia na posledný schod, teda najmenší možný súčet zašpinení na polovicach schodov, na ktoré stúpi.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(2 \leq n \leq 5 \cdot 10^5\)) udávajúce počet schodov na chate.

Potom budú nasledovať dva riadky s \(n\) číslami oddelenými medzerou. Prvý pre ľavú stranu a druhý pre pravú. \(i\)-te číslo v riadku prezenovať zašpinenie \(i\)-teho schodu na danej strane. Pre každé číslo zašpinenia platí: \(0 < l_i, p_i \leq 1000\).

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Vypíšte jedno číslo - najnišie možné zašpinenie ponožiek.

Príklady

Input:

4
1 2 2 1
2 1 3 2

Output:

2

Filipko preskočil prvý schod a skočil pravou nohou rovno na druhý s hodnotou 1. Odtiať už dočiahol skočiť na posledný schod ľavou nohou s hodnotou 1, teda dokopy 2.

Input:

5
1 4 5 1 5
1 7 2 2 3

Output:

7

1. schod ľavá noha(1), 3. schod pravá noha(2), 4. schod ľavá noha(1), 5. schod pravá noha(3): 1 + 2 + 1 + 3 = 7.