Description

windy有\(N\)条木板需要被粉刷。每条木板被分为\(M\)个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷\(T\)次，他最多能正确粉刷多少格子？ 一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

Input

第一行包含三个整数\(N,M,T\)。 接下来有\(N\)行，每行一个长度为\(M\)的字符串，\(0\)表示红色，\(1\)表示蓝色。

Output

包含一个整数，最多能正确粉刷的格子数。

Sample Input

3 6 3

111111

000000

001100

Sample Output

16

HINT

\(30\%\)的数据，满足\(1 \le N,M \le 10\)；$0 \le T \le 100 $。

\(100\%\)的数据，满足\(1 \le N,M \le 50\)；\(0 \le T \le 2500\) 。

一个很明显的dp，\(f_{i,j}\)表示该木板前\(i\)格涂\(j\)次得到的最多格子数；\(g_{i,j}\)表示前\(i\)块木板涂\(j\)次得到的最多格子数。

转移如下（\(pre_{i}\)表示该木板前\(i\)格\(1\)的数目）：

\(f_{i,j} = max(f_{i,j},f_{k,j-1}+max(pre_{i}-pre_{k},i-k-(pre_{i}-pre_{k})))\)；

\(g_{p,i} = max(g_{p,i},g_{p-1,j}+f_{m,i-j})\)。

代码如下：

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

using namespace std;

#define inf (1<<29)

#define maxn (60)

#define maxt (2510)

int n,m,t,pre[maxn],f[maxn][maxt],g[maxn][maxt];

inline void dp(int p)

{

	memset(f,0,sizeof(f));

	for (int i = 1;i <= m;++i)

		for (int j = 1;j <= t;++j)

		{

			f[i][j] = f[i-1][j];

			for (int k = 0;k < i;++k)

				f[i][j] = max(f[i][j],f[k][j-1]+max(pre[i]-pre[k],i-k-(pre[i]-pre[k])));

		}

	for (int i = 1;i <= t;++i)

		for (int j = 0;j <= i;++j)

			g[p][i] = max(g[p][i],g[p-1][j]+f[m][i-j]);

}

int main()

{

	freopen("1296.in","r",stdin);

	freopen("1296.out","w",stdout);

	scanf("%d %d %d",&n,&m,&t);

	for (int p = 1;p <= n;++p)

	{

		for (int i = 1;i <= m;++i) scanf("%1d",pre+i),pre[i] += pre[i-1];

		dp(p);

	}

	printf("%d",g[n][t]);

	return 0;

}