Yawned-Zoned

Interview

Time limit2.5sMemory limit1024 MB

Summary

Place exactly W dividers between columns so the largest group of students who yawn from one starting student is as small as possible, then print that size.

Level: Medium5 of 10
Topics: Dynamic programming, BFS, Graph
Solved: No attempts yet

Problem

Jeongwon had a strange experience while teaching a class at school. One student felt sleepy and yawned, and the students sitting nearby started yawning as well.

The classroom has seats arranged in a grid of $R$ rows and $C$ columns, and some seats are occupied by students. When a student yawns, the student sitting one seat in front, one seat to the left, one seat to the right, and one seat behind will yawn next. A student who has already yawned does not yawn again.

Even if only one student yawns, many students will yawn after some time. Jeongwon wants to stop the class from being disrupted by too many yawns at once, so he plans to install vertical dividers. A divider can be placed between column $i$ and column $i+1$ for $1 \leq i < C$ . Because a divider is very long, it must block the seats from the front row to the back row.

If a divider is installed between two students, a yawn does not spread from one student to the other. Using this, Jeongwon wants to install exactly $W$ dividers so that the maximum number of additional students who yawn after a single student yawns is minimized. Write a program that helps Jeongwon place the dividers.

Input

The first line contains the number of rows $R$ , the number of columns $C$ , and the number of dividers $W$ .

Each of the next $R$ lines contains a string of $C$ digits describing the classroom. The $j$ -th value of the $i$ -th string is 1 if a student sits in the seat in row $i$ (counting from the front) and column $j$ (counting from the left), and 0 if the seat is empty.

Output

Print the maximum number of students who yawn at once when Jeongwon places $W$ dividers in the best way.

Examples2

Example 1
Input
```
2 5 0
11011
01101
```
Expected output
```
4
```
Example 2
Input
```
3 6 2
110011
011110
110011
```
Expected output
```
5
```