stiva

Să considerăm o stivă, iniţial vidă. Putem efectua următoarele operaţii:

• $push(X)$ - se introduce în stivă litera $X$ (evident, în vârful stivei);
• $pop$ - se extrage litera aflată la vârful stivei (operaţia pop se execută atunci când stiva este nevidă);
• $top$ - se afişează litera aflată la vârful stivei (operaţia top se execută atunci când stiva este nevidă).

O secvenţă de operaţii este considerată corectă dacă:

• iniţial stiva este vidă;
• se execută o serie de operaţii $push$, $pop$, $top$, fără a executa pop sau top când stiva este vidă;
• la final stiva este vidă.

Utilizând secvenţe corecte de operaţii, putem afişa diferite şiruri de caractere. De exemplu, şirul ABCACBA poate fi generat astfel: $push(A)$, $top$, $pop$, $push(B)$, $top$, $pop$, $push(C)$, $top$, $pop$ etc.

O altă secvenţă de operaţii corectă, dar mai scurtă ar fi: $push(A)$, $top$, $push(B)$, $top$, $push(C)$, $top$, $push(A)$, $top$, $pop$, $top$, $pop$, $top$, $pop$, $top$, $pop$.

Cerinţă

Dat fiind un şir format din litere mari, să se determine numărul minim de operaţii dintr-o secvenţă corecte care afişează şirul dat.

Date de intrare

Fişierul de intrare stiva.in conţine pe prima linie un şir format numai din litere mari.

Date de ieșire

Fişierul de ieşire stiva.out va conţine o singură linie pe care va fi scris numărul minim de operaţii dintr-o secvenţă corecte care afişează şirul din fişierul de intrare.

Restricții și precizări

• Lungimea şirului este $\leq 500$.

Exemplul 1

stiva.in

ABCACBA

stiva.out

15