비트랜드의 고양이

시간 제한1초메모리 제한1024 MB

요약

두 줄의 방에 K(비알레르기)와 A(알레르기) 학생이 있고, 고양이는 같은 줄에서 오른쪽으로 한 칸 이동하거나 반대 줄의 더 오른쪽 방으로 건너뛸 수 있다. 방문할 수 있는 최대 방 수를 구한다.

문제

비트랜드에는 사람들을 찾아가 기쁘게 해 주는 것을 좋아하는 고양이가 삽니다.

봄이 되자 고양이는 시험 준비에 열중하는 비트랜드 대학교 학생들이 걱정되었습니다. 이 대학교의 학생은 고양이에게 알레르기가 없어 기꺼이 고양이를 쓰다듬거나, 아니면 고양이 알레르기가 있는 두 부류로 나뉩니다. 당연히 고양이는 알레르기가 있는 학생은 찾아가지 않습니다.

학생들은 거리 양쪽에 마주 보고 있는 긴 기숙사 두 곳에 삽니다. 두 기숙사는 모두 단층이며 각각 똑같은 방 $N$ 개로 이루어져 있습니다. 각 기숙사의 방은 왼쪽에서 오른쪽으로 일렬로 놓여 있습니다.

고양이는 다음과 같은 방식으로 왼쪽에서 오른쪽으로 학생들을 찾아갑니다.

먼저 고양이는 두 기숙사 중 어느 한 곳의 아무 방 앞에 홀연히 나타납니다.
어떤 방의 학생을 만난 뒤에는, 같은 기숙사에서 바로 오른쪽 옆 방으로 가거나(그 방에 알레르기가 있는 학생이 없어야 합니다), 거리를 건너 반대편 기숙사에서 지금 있는 방보다 오른쪽에 있으면서 알레르기가 있는 학생이 없는 아무 방으로 이동할 수 있습니다.
학생들을 찾아다니는 동안 고양이는 거리를 몇 번이든 건널 수 있습니다.
이렇게 더 이상 이동할 수 없을 때까지 학생들을 찾아갑니다.
그런 다음 고양이는 마법의 힘을 써서 고양이답게 홀연히 사라집니다.

고양이가 최대 몇 명의 학생을 기쁘게 해 줄 수 있는지 구하세요.

첫째 줄에 각 기숙사의 방 개수 $N$ 이 주어집니다. 다음 두 줄은 각각 기숙사 한 곳을 나타내며, $N$ 개의 문자가 놓입니다. $i$ 번째 문자는 그 기숙사의 $i$ 번째 방에 사는 학생이 알레르기가 있는지를 나타냅니다.

고양이가 방문할 수 있는 방의 최대 개수를 정수 하나로 출력합니다.