unittest
{
	assert( [ "3 5 4", "11100", "10001", "00111" ].parse.expand.solve == 2 );
	assert( [ "3 5 8", "11100", "10001", "00111" ].parse.expand.solve == 0 );
	assert( [ "4 10 4", "1110010010", "1000101110", "0011101001", "1101000111" ].parse.expand.solve == 3 );
}



import core.bitop;
import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto hwk = input.front.split.to!( long[] );
	auto css = new dchar[][]( hwk[ 0 ], hwk[ 1 ] );
	foreach( ref cs; css )
	{
		input.popFront;
		cs = input.front.to!( dchar[] );
	}
	return tuple( hwk[ 2 ], css );
}

auto solve( long k, dchar[][] css )
{
	// 横方向に分割する位置をbit全列挙する
	auto ans = long.max;
	LOOP: foreach( yb; 0L .. 1L << ( css.length.signed - 1 ) )
	{
		auto bp = yb._popcnt;
		auto r = bp;
		auto vts = new long[ 1 + bp ];
		auto vtm = 0L;
		auto vtc = 0L;
		foreach( x; 0L .. css[ 0 ].length.signed )
		{
			auto vs = new long[ 1 + bp ];
			auto vi = 0L;
			
			// 縦方向に分割が必要か判定
			for( auto y = 0L; y < css.length; y++ )
			{
				if( css[ y ][ x ] == '1' )
				{
					vts[ vi ]++;
					vs[ vi ]++;
					vtm = max( vtm, vts[ vi ] );
				}
				if( yb & ( 1L << y ) ) vi++;
			}
			
			if( k < vtm )
			{
				// 縦方向に分割する
				if( vtc == 0 ) continue LOOP;		// 1列だけでKマス超えてしまったので無理
				r++;
				vts[] = vs[];
				vtm = vts.reduce!max;
				if( vtm == 0 ) continue LOOP;		// 1列だけでKマス超えてしまったので無理
				vtc = 1;
			}
			else
			{
				// 縦方向に分割しない
				vtc++;
			}
		}
		ans = min( ans, r );
	}
	return ans;
}
