버스 논리

면접 대비

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

요약

출발 정류장과 길이 s인 비트 문자열로 주어진 버스 노선들이 있을 때, 출발 정류장을 지나는 버스 하나를 골라 갈 수 있는 다른 정류장 수의 최댓값을 구한다.

난이도: 보통10점 중 4점
유형: 비트 연산, 구현, 배열, 완전 탐색
정답자: 아직 제출이 없습니다

문제

노팅엄 같은 도시에서 어디에 살지 결정할 때 중요한 요소는 흥미로운 장소로 가는 교통편이 얼마나 잘 갖춰져 있느냐이다. UKIEPC 운영자로 스트레스 받는 삶을 살면서 밝은 주황색 버스를 타고 시내 곳곳을 자주 관광하는 Max에게는 특히 중요한 문제다.

Max가 생각하는 즐거운 시간은 버스를 딱 한 번만 타면 갈 수 있는 장소를 방문하는 것이다. 그는 가장 좋아하는 버스 노선을 따라 특정 장소 근처로 이사하는 것을 고려하고 있다. 그곳에서 갈 수 있는 다른 명소는 몇 곳인가? (한 번 이동할 때마다 새로운 버스 노선을 선택할 수 있다고 가정한다.)

그림 B.1: 예제 입력 1을 설명하는 버스 노선 지도. 늘 그렇듯 Max는 그가 출발할 수 있는 각 버스 정류장의 중앙에 흰 점으로 그려져 있다.

입력

첫째 줄에는 세 정수, Max의 출발 정류장 $m$ ( $1 \le m \le s$ ), 버스의 수 $b$ ( $1 \le b \le 50$ ), 정류장의 수 $s$ ( $1 \le s \le 50$ )가 주어진다.

다음 $b$ 개의 줄에는 버스 노선이 주어진다. 각 노선은 길이 $s$ 의 문자열로 표현되며, $i$ 번째 문자가 '1'이면 이 버스 노선이 $i$ 번 정류장에 정차한다는 뜻이고, '0'이면 정차하지 않는다는 뜻이다.

출력

Max가 출발 정류장에서 버스를 정확히 한 번 타고 갈 수 있는 다른 정류장의 최대 개수를 출력한다.

예제2

예제 1
입력
```
1 3 5
01100
10011
10111
```
예상 출력
```
3
```
예제 2
입력
```
2 2 3
101
101
```
예상 출력
```
0
```