P4158 [SCOI2009] Painter

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.

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 a single integer: the maximum number of cells that can be painted correctly.

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