제3회 디미고 프로그래밍 챌린지 오픈 콘테스트

codeforces를 사랑하는 사람들이라면 codeforces 시간은 항상 늦은 저녁이다라는 것을 알 것이다! 11시 이후에는기숙사에서 생활해야하는 디미고에서는 codeforces를 하기 위해서 미술실을 이용해야 한다. 미술실을 이용하기 위해서는 사감 선생님의 허락이 필요하다. codeforces에 열정이 가득한 magic_spirit은 미술실을 매일 빌릴려고 했지만 사감 선생님은 미술실을 매일 빌리게 된다면 미술실을 이용하는 학생들이 매일마다 잠을 늦게 자는 것을 우려하여 다음과 같은 규칙을 만들었다.

1. 미술실은 이틀 연속으로 빌리지는 못한다.

2. 이틀동안 미술실을 빌리지 않았으면 무조건 미술실을 빌린다.

이런 규칙을 만족하면서 magic_spirit은 사감 선생님과 협의를 통해 특별실 날짜표를 만들게 되었다. 하지만 왼속잡이의 숙명(왼손잡이는 글씨를 쓰면 전에쓴 글씨가 번질때가 많음)으로 날짜표의 일부가 손상되었다. 이왕 이렇게 된 거codeforces를 최대한 많이 칠 수 있도록 날짜표를 복구하려던 magic_spirit은 반복되는 늦은 수면으로 머리가 잘 돌아가지 않는다는 것을 알게 되었다. 아픈 magic_spirit을 대신해 다음과 같은 규칙을 만족하면서 codeforces를 최대한 칠 수 있도록 미술실을 빌리는 횟수가 최대가 되도록 할 때 미술실을 몇 번 빌릴 수 있는지를 구해주자. 또한 날짜표는 다음과 같은 형식으로 이루어져 있다.

• O : 미술실사용

• X : 미술실미사용

• ? : 손상되어값이알수없음