Description

windy has $N$ wooden boards that need to be painted. Each board is divided into $M$ cells. Each cell should be painted red or blue.

In each painting operation, windy can choose a contiguous segment of cells on a single board and paint it with one color. Each cell can be painted at most once.

If windy can paint at most $T$ times, what is the maximum number of cells he can paint correctly?

A cell is considered incorrect if it is left unpainted or painted with the wrong color.

Input Format

The first line contains three integers, $N$, $M$, $T$.

Then there are $N$ lines, each containing a string of length $M$, where 0 denotes red and 1 denotes blue.

Output Format

Output a single integer: the maximum number of cells that can be painted correctly.

3 6 3
111111
000000
001100

16

Hint

For $30\%$ of the testdata, $1 \le N, M \le 10$, $0 \le T \le 100$.

For $100\%$ of the testdata, $1 \le N, M \le 50$, $0 \le T \le 2500$.

Translated by ChatGPT 5