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 corectă dacă este construită conform următoarelor reguli:

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

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