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.
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [30%]
Subtask 4 [40%]
No additional constraints.
The first line contains integers and .
The next lines each contain characters ( or ), the -th character of the -th line representing .
Output the length of the largest explorable contiguous subsequence of floors.
5 3 001 010 011 100 001
Explanation for Sample
The largest contiguous subsequence of floors that is explorable is .