Bus Logic

Interview

Time limit1sMemory limit512 MB

Summary

Given a starting stop and bus routes as bit strings of length s, find the maximum number of other stops reachable by choosing exactly one bus that serves the starting stop.

Level: Medium4 of 10
Topics: Bit manipulation, Implementation, Array, Brute force
Solved: No attempts yet

Problem

A core part of deciding where to live in a city like Nottingham is the availability of transport links to interesting places. This matters especially to Max, who enlivens his stressful life as organiser of UKIEPC by making frequent sightseeing travels around town in a bright orange bus.

Max's idea of a good time is a visit to a spot that takes exactly one bus journey to get to. He is considering moving house to be near one specific spot along his favourite bus route. How many such other scenic spots can he reach from there, assuming that on a given trip he can choose a new bus route each time?

Figure B.1: A bus route map illustrating Sample Input 1. Max, as usual, is drawn as a white dot in the centre of each bus stop he can start from.

Input

The first line of input contains three integers: Max's starting stop $m$ ( $1 \le m \le s$ ), the number of buses $b$ ( $1 \le b \le 50$ ), and the number of stops $s$ ( $1 \le s \le 50$ ).

The next $b$ lines contain the bus routes, each written as a string of $s$ characters where the $i$ th character being '1' denotes that this bus route has a stop at $i$ , and '0' denotes that it does not.

Output

Output the maximum number of other stops Max can reach from the starting stop by taking exactly one bus.

Examples2

Example 1
Input
```
1 3 5
01100
10011
10111
```
Expected output
```
3
```
Example 2
Input
```
2 2 3
101
101
```
Expected output
```
0
```