h2. Cerinţă

Se dă un număr $N$ şi doua şiruri $A$ şi $B$ de câte $2 * N$ numere naturale. Să consideram 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!

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:

h2. Subtaskuri

* $Subtask *Omul este o persoană umană* - 4 puncte: N ≤ 10$
* $Subtask *Să fie bine ca să  nu fie rău* - 20 de puncte: N ≤ 50$
* $Subtask *Am marcat goluri, aşa şi aşa, multe, dar nu prea multe* - 24 de puncte: 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: N ≤ 50.000$

* $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$

h2. Exemplu
table(example). |_. benzina.in |_. benzina.out |

| 3

| 3

5 1 4 8 7 5
3 7 7 8 5 2
| 33 |

| 5

| 5

7 4 7 7 4 4 4 7 7 7
4 7 4 4 7 7 7 4 4 4
| 61 |

h3. Explicaţie
Pentru primul exemplu, o parantezare optimă este $()()()$.

Pentru al doilea exemplu,câteva dintre parantezările optime sunt $(((()))())$, $(((())))()$ şi $()(()()())$.

Pentru al doilea exemplu, câteva dintre parantezările optime sunt $(((()))())$, $(((())))()$ şi $()(()()())$.

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