5. Éra fanúšika hviezdnych bitiek

Je to opäť tu!!! Sebik sa nevie dočkať. O dva mesiace nastane totiž jeho obľúbená časť roka - finále galakticky známej ligy Hviezdne Bitky (inde známe aj ako Stars Brawl), a on sa nevie dočkať, kedy znova uvidí svojich idolov si to opäť rozdať. Každá hviezda pošle elitný tím zložený iba z tých najlepších z jej planét, a tieto všetky vzrušujúce zápasy sa odohrajú pred očami fanúšikov neďaleko Sebikovej planéty. Má našporenú kopu peňazí, a už sa teší ako bude fandiť naživo - avšak má jeden problém. Sebik je pravý fanúšik Hviezdnych líg, a veľmi rád by si pozrel obrovské množstvo tímov - respektíve, nerád by zmeškal nejaké hry svojich obľúbencov, a lístky sa rýchlo míňajú! Pomôžte mu!

Úloha

V Hviezdnych Bitkách súťaží \(2^r\) tímov očíslovaných od \(0\) do \(2^r-1\). Hrajú vo forme štandardného pavúka s \(r\) kolami: prvé kolo hrá tím \(0\) proti tímu \(1\), tím \(2\) proti tímu \(3\), a v druhom kole sa stretnú výherci týchto dvoch zápasov, a tak ďalej až do finále. Sebik každému tímu fandí v inej miere, teda pre tím \(i\) si určil číslo \(a_i\). Sebik je ochotný vymeškať maximálne \(a_i\) zápasov odohraných tímom \(i\) v celom turnaji. Žiadne dva zápasy nebežia paralelne, teda ak by chcel, vedel by si kúpiť lístky na všetky zápasy, avšak to by bolo príliš drahé. Každý lístok na zápas má totiž svoju cenu \(c_{xj}\). Vašou úlohou je zistiť, ako najlacnejšie vie Sebik kúpiť lístky tak, aby pre nejaký tím nevymeškal viac zápasov ako chcel.

Formát vstupu

V prvom riadku vstupu je číslo \(r\), počet kôl v turnaji.

V druhom riadku je \(2^r\) čísel, pričom \(i\)-té z nich udáva, koľko zápasov je Sebik ochotný vymeškať pre tím \(i\). Tieto čísla sú iba v rozsahu od 0 do \(r\).

Nasleduje \(r\) riadkov. \(x\)-tý¹ riadok obsahuje \(2^{r-x}\) čísel, pričom \(j\)-té z nich udáva \(c_{xj}\), teda cenu lístka \(j\)-tého zápasu \(x\)-tom kole. Teda v prvom riadku je \(2^{r-1}\) čísel, v druhom \(2^{r-2}\)…

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

Navyše, v prvej sade platí, že všetky zápasy stoja rovnako veľa peňazí.

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo, a to najmenšiu možnú cenu, ktorú musí Sebik zaplatiť, aby pre žiadny tím nevymeškal viac zápasov ako chcel.

Príklad

Input:

2
1 1 0 1
300 300
300

Output:

600

Keďže nemôžeme zmeškať ani jeden zápas tímu \(2\), tak musíme kúpiť všetky zápasy čo by teoreticky mohli hrať, teda druhé semifinále a finále. Pre ostatné tímy stačí, ak kúpime iba finále, lebo \(1\) zápas zmeškať môžeme.

Input:

3
1 2 3 2 1 0 1 3
100 150 50 90
500 400
800

Output:

1350

Pre tím \(5\) nemôžeme zmeškať jediný zápas, a tak musíme kúpiť všetko, čo by teoreticky mohli hrať, teda zápasy za \(50\), \(400\) a \(800\). To nám vyrieši všetky tímy okrem tímu \(0\), pre ktorý ak by sa dostal do semifinále, zmeškali by sme dva zápasy, a tak musíme kúpiť ešte jeden lístok. Optimálne je kúpiť lístok za \(100\), a teda riešením bude \(100 + 50 + 400 + 800 = 1350\).

Input:

4
1 2 4 1 1 4 0 1 1 1 0 4 3 2 4 0
1 2 4 8 3 4 5 8
4 5 6 7
9 8
15

Output:

73