Armstöd

Petitess-organisationen (PO) har möte och de $N$ medlemmarna sitter på stolar i en ring, vända inåt. Mellan varje par av stolar finns ett armstöd som högst en av personerna kan använda. Varje person har en preferens i form av vilken eller vilka armar hen vill placera på armstöden:

  • V: vänster arm

  • H: höger arm

  • A: antingen vänster eller höger arm

  • B: båda armarna

  • I: ingen arm

Skriv ett program som beräknar hur många av personerna som maximalt kan bli nöjda.

Indata

På första raden står ett heltal $N$, antal personer i ringen. På andra raden står personernas preferenser, givna i den ordning personerna sitter, moturs i ringen, i form av en sträng bestående av $N$ bokstäver, vardera V, H, A, B eller I.

Utdata

Programmet ska skriva ut ett heltal: det maximala antalet personer som kan få sin preferens uppfylld.

\includegraphics[width=5cm]{armstodbild.pdf}
Figure 1: Figuren visar lösningen till exempel 1. De tjocka linjerna markerar armar som personer lagt på armstöden. Den grå färgen visar vilka som fått sina preferenser uppfyllda. Pilen markerar var den givna indatasträngen börjar och slutar.

Poängsättning

För testfall värda

$20$ poäng

gäller att

$N=5$

och första bokstaven är I.

$40$ poäng

 

$6\le N\le 15$

, vilka bokstäver som helst.

$20$ poäng

 

$25\le N\le 30$

och första bokstaven är I.

$20$ poäng

 

$25\le N\le 30$

, vilka bokstäver som helst.

Sample Input 1 Sample Output 1
7
BAVIABH
6
Sample Input 2 Sample Output 2
5
IHAVB
4
Sample Input 3 Sample Output 3
15
BHVBABHVIBHABVV
11