Background

$大家都看过猫和老鼠吧$

$假设有一天杰瑞偷了一块方形的披萨$ $上面有一些奶酪块$

$结果杰瑞刚把他搬回来就噎死了（这啥剧情阿）$

$于是一群小杰瑞吃席$ $就开始商量怎么分这块披萨$

$但这群小杰瑞实在是太贪心了，每个人都想得到奶酪多的那块$

$于是请教了你来分这块披萨$

Description

$给出一个H * W的数组表示披萨，1表示有一块奶酪，0表示没有奶酪，给出一个K$ $要求切割得到的每一块小披萨都包括小于等于K粒的奶$

$你要切割披萨以至于得到的每一块披萨上都有小于等于K块的奶酪$

$注：每一次切割必须从披萨的一端切到另一端$ $比如下图这样是合理的切法$

$下图是不合理的$

$你必须保证每个小杰瑞最终得到的皮萨里必须有小于等于K块的奶酪$

$你能求出满足条件的最小切割数吗$

Format

Input

$第一行给出H，W，K，表示披萨的尺寸和K$

$1\leq H\leq 10$

$1\leq W\leq 1000$

$1\leq K\leq H * W$

$接下来给出H * W的矩阵，1代表奶酪，0代表没有奶酪$

Output

$最小切割数$

Samples

3 5 4
11100
10001
00111

2

$切法有很多，这里解释其中一种切法$

$第一块11100 奶酪为3小于等于K$

$第二块10001 奶酪为2小于等于K$

$第三块00111 奶酪为3小于等于K$

Limitation

1s, 1024KiB for each test case.