Fişierul intrare/ieşire:	benzina.in, benzina.out	Sursă	Junior Challenge 2018
Autor	Alexandru Petrescu, Bogdan Pop	Adăugată de	Junior Challenge •JuniorChallenge2018
Timp execuţie pe test	0.15 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Benzina

Textul problemei stă sub influenţa noului curent literar numit umorul absent

Marcel se plimba liniştit cu blatmobilul când, deodată, îi auzi pe Dl. IOI, Nry şi Semicerc vorbind ca la colţul străzii. 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 blatmobil şi le-a dat târcoale celor trei, dând senzaţia că e în căutare 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 în romanele poliţiste şi în scrisori pierdute poţi afla informaţii suficient de prestigioase trăgând cu urechea, Marcel a plecat să caute benzină în altă parte. Adică motivat.

Cerinţă

Se dă un număr N şi două şiruri A şi B de câte 2 * N numere naturale. Să considerăm o parantezare corectă de lungime 2 * N căreia vrem să îi calculăm costul. Pentru fiecare paranteză i, dacă e deschisă adăugam A_i iar dacă e închisă adăugăm B_i. Găsiţi costul maxim al unei parantezări corecte!

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

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

Date de intrare

Fişierul de intrare benzina.in (adică motivat.in) conţine numărul N pe prima linie, şirul A pe a doua linie şi şirul B pe a treia linie. Un şir apare sub forma a 2 * N numere naturale mai mici ca 10⁹ separate prin câte un spaţiu.

Date de ieşire

În fişierul de ieşire benzina.out (adica motivat.out) se va afla un singur număr, şi anume costul maxim al unei parantezări corecte.

Subtaskuri

• Subtask Omul este o persoană umană - 4 puncte (testele 1 şi 2): N ≤ 10
• Subtask Să fie bine ca să nu fie rău - 20 de puncte (testele 3-12): N ≤ 50
• Subtask Am marcat goluri, aşa şi aşa, multe, dar nu prea multe - 24 de puncte (testele 13-24): N ≤ 750
• Subtask Noi... vedete; de la început până la sfârşit... nu pot să înţeleg ce s-a întâmplat - 52 de puncte (testele 25-50): N ≤ 50.000

Exemplu

Explicaţie

Pentru primul exemplu, o parantezare optimă este ()()().
Pentru al doilea exemplu, câteva dintre parantezările optime sunt (((()))()), (((())))() şi ()(()()()).

Cum se trimit solutii?