== include(page="template/taskheader" task_id="benzina") ==

_Textul problemei sta sub influenta noului curent literar numit $umorul absent$_

_Textul problemei stă sub influenţa noului curent literar numit $umorul absent$_

Marcel se plimba linistit cu blatmobilul cand, deodata, ii auzi pe _Dl IOI_, _Nry_ si _Semicerc_ vorbind ca la coltul strazii. Pentru ca erau la coltul strazii. Spirit santajist, Marcel s-a gandit ca poate subtiliza informatii relevante daca sta si ii asculta. Pentru a nu parea suspect, a coborat din blatomobil si le dadea tarcoale celor trei dand senzatia ca e in cautare de benzina. In sensul de motivat. A aflat ca cei trei puneau la cale o aparitie in Azerbaidjan sub noile nume de scena _Dl IOIT_, _Nrz_, respectiv _Demicerc_. Realizand ca numai in romanele politiste si in scrisori pierdute poti afla informatii suficient de prestigioase tragand cu urechea, Marcel a plecat sa caute benzina in alta parte. Adica motivat.

Marcel se plimba liniştit cu blatmobilul când, deodată, îi auzi pe _Dl IOI_, _Nry_ si _Semicerc_ vorbind ca la colţul strazii. Pentru că erau la colţul străzii. Spirit şantajist, Marcel s-a gândit că poate subtiliza informaţii relevante dacă stă şi îi ascultă. Pentru a nu părea suspect, a coborât din blatomobil si le dadea tarcoale celor trei dand senzatia ca e in cautare de benzină. În sensul de motivat. A aflat că cei trei puneau la cale o apariţie în Azerbaidjan sub noile nume de scenă _Dl IOIT_, _Nrz_, respectiv _Demicerc_. Realizând că numai in romanele poliţiste şi în scrisori pierdute poţi afla informaţii suficient de prestigioase tragând cu urechea, Marcel a plecat să caute benzină in alta parte. Adică motivat.

h2. Cerinta

Se da un numar $N$ si doua siruri $A$ si $B$ de cate $2N$ numere naturale. Sa consideram o parantezare corecta de lungime $2N$ careia vrem sa ii calculam costul. Pentru fiecare paranteza $i$, daca e deschisa adaugam $A{~i~}$ iar daca e inchisa adaugam $B{~i~}$. Gasiti costul maxim al unei parantezari corecte!

Se dă un numar $N$ şi doua siruri $A$ şi $B$ de câte $2N$ numere naturale. Să consideram o parantezare corectă de lungime $2N$ căreia vrem sa îi calculam costul. Pentru fiecare paranteza $i$, dacă e deschisă adăugam $A{~i~}$ iar dacă e închisa adaugăm $B{~i~}$. Găsiţi costul maxim al unei parantezări corecte!

O parantezare este corecta daca este construita conform urmatoarelor reguli:

O parantezare este corectă daca este construită conform următoarelor reguli:

* $<sirul vid> = <parantezare corecta>$
* $<parantezare corecta> + <parantezare corecta> = <parantezare corecta>$
* $"(" + <parantezare corecta> + ")" = <parantezare corecta>$

* $<şirul vid> = <parantezare corectă>$
* $<parantezare corectă> + <parantezare corectă> = <parantezare corectă>$
* $"(" + <parantezare corectă> + ")" = <parantezare corectă>$

h2. Date de intrare

Fişierul de intrare $benzina.in$ (adica motivat.in) contine numarul $N$ pe prima linie, sirul $A$ pe a doua linie sirul $B$ pe a treia linie. Un sir apare sub forma a $2N$ numere naturale mai mici ca $10^9^$ separate prin cate un spatiu.

Fişierul de intrare $benzina.in$ (adica motivat.in) conţine numarul $N$ pe prima linie, sirul $A$ pe a doua linie şi şirul $B$ pe a treia linie. Un şir apare sub forma a $2N$ numere naturale mai mici ca $10^9^$ separate prin câte un spaţiu.

h2. Date de ieşire