도장찍기 게임 timer 2초 memory 512MB

정올이는 O도장, X도장, OX도장 세 종류의 스탬프를 각각 0개 이상 가지고 있다. 이것들은 각각 O, X, OX를 종이에 찍을 수 있는 도장들이다.

O도장을 사용하면 O가 하나씩 찍히고, X도장을 사용하면 X가 하나씩 찍힌다.

OX도장을 사용하면 OX가 가로 일렬로 하나씩 찍힌다. 도장의 방향을 바꾸는 것으로, XO를 찍을 수도 있다.

정올이는 가지고 있는 도장들을 각각 정확히 1회씩 적당한 차례로 사용해, 종이에 O와 X를 찍었다. 종이에 찍힌 문자들은 문자열 S로 표시되며, S는 O와 X로 구성된 길이 N의 문자열으로 S_i = O이면 왼쪽에서 i 번째가 찍힌 모양이 O인 것을 나타내며, S_i = X이면 그것이 X 임을 나타낸다 (1≤i≤N).

정올가 가지고있는 도장들의 수를 알지 못하지만 종이에 찍힌 모양들의 상태를 알고 있다면 정올이가 가지고 있는 OX도장의 수로 가능한 최대 값을 구하는 프로그램을 작성하시오.