/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf=0x3f3f3f3f;
const int N=10,M=1000;
int n,m,s;
char a[N+1][M+5];
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)cin>>a[i]+1;
	int ans=inf;
	for(int i=0;i<1<<n-1;i++){
		vector<int> pos;
		pos.pb(0);
		for(int j=1;j<n;j++)if(i&1<<j-1)pos.pb(j);
		pos.pb(n);
		int now=pos.size()-2;
		vector<int> cnt(pos.size()-1,0);
		for(int j=1;j<=m;j++){
			bool ok=true;
			vector<int> cnt0(pos.size()-1,0);
			for(int k=0;k<cnt.size();k++){
				for(int o=pos[k]+1;o<=pos[k+1];o++)cnt0[k]+=a[o][j]^48;
				if(cnt0[k]>s)goto label_end;
				if(cnt[k]+cnt0[k]>s)ok=false;
			}
			if(ok)for(int k=0;k<cnt.size();k++)cnt[k]+=cnt0[k];
			else now++,cnt=cnt0;
		}
		ans=min(ans,now);
	label_end:;
	}
	cout<<ans;
	return 0;
}
### Prompt

Construct a cpp code solution to the problem outlined:

We have a chocolate bar partitioned into H horizontal rows and W vertical columns of squares.

The square (i, j) at the i-th row from the top and the j-th column from the left is dark if S_{i,j} is `0`, and white if S_{i,j} is `1`.

We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.

How many times do we need to cut the bar so that every block after the cuts has K or less white squares?

Constraints

* 1 \leq H \leq 10
* 1 \leq W \leq 1000
* 1 \leq K \leq H \times W
* S_{i,j} is `0` or `1`.

Input

Input is given from Standard Input in the following format:


H W K
S_{1,1}S_{1,2}...S_{1,W}
:
S_{H,1}S_{H,2}...S_{H,W}


Output

Print the number of minimum times the bar needs to be cut so that every block after the cuts has K or less white squares.

Examples

Input

3 5 4
11100
10001
00111


Output

2


Input

3 5 8
11100
10001
00111


Output

0


Input

4 10 4
1110010010
1000101110
0011101001
1101000111


Output

3

### Response

```cpp
/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf=0x3f3f3f3f;
const int N=10,M=1000;
int n,m,s;
char a[N+1][M+5];
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)cin>>a[i]+1;
	int ans=inf;
	for(int i=0;i<1<<n-1;i++){
		vector<int> pos;
		pos.pb(0);
		for(int j=1;j<n;j++)if(i&1<<j-1)pos.pb(j);
		pos.pb(n);
		int now=pos.size()-2;
		vector<int> cnt(pos.size()-1,0);
		for(int j=1;j<=m;j++){
			bool ok=true;
			vector<int> cnt0(pos.size()-1,0);
			for(int k=0;k<cnt.size();k++){
				for(int o=pos[k]+1;o<=pos[k+1];o++)cnt0[k]+=a[o][j]^48;
				if(cnt0[k]>s)goto label_end;
				if(cnt[k]+cnt0[k]>s)ok=false;
			}
			if(ok)for(int k=0;k<cnt.size();k++)cnt[k]+=cnt0[k];
			else now++,cnt=cnt0;
		}
		ans=min(ans,now);
	label_end:;
	}
	cout<<ans;
	return 0;
}
```