## DMOPC '22 Contest 2 P6 - Yogyakarta Elevators

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

At IOI 2022, Team Canada encountered a mystery with the hotel elevators. Puzzled, they have asked you (their tour guide) to solve it for them.

The elevator system of the hotel can be viewed as a 2-D grid with floors and elevators. The floors are numbered to from bottom to top and the elevators are numbered to from left to right. For each floor , is if elevator stops at that floor and if it doesn't. Each elevator can be used to travel between the floors it stops at.

A contiguous subsequence of floors is defined as explorable if, starting from any floor in the subsequence, it is possible to reach all other floors in the subsequence while only entering floors numbered from to .

Your task is to determine the length of the largest explorable contiguous subsequence of floors.

#### Input Specification

The first line contains integers and .

The next lines each contain characters ( or ), the -th character of the -th line representing .

#### Output Specification

Output the length of the largest explorable contiguous subsequence of floors.

#### Sample Input

5 3
001
010
011
100
001

#### Sample Output

3

#### Explanation for Sample

The largest contiguous subsequence of floors that is explorable is .