牛马生活

文件与限制

输入文件：horse.in；输出文件：horse.out。

时间限制：1 秒；空间限制：512 MiB。使用 C++14 O2。

题目描述

众所周知，现在的生活压力很大，张老师自然也是过着牛马的生活——永远在开会，而这些会明明没什么用！

而这天，张老师决定起义！他不想再当牛马了！（至少可以少当一会）

于是老板为了安抚张老师，给他发了 $k$ 张 "会议取消券"

对于一次公司会议，张老师可以使用一张 "会议取消券"，这样他就不用去参加这个会议了

现在张老师统计了接下来 $n$ 天每天的工作会议，为了方便理解，张老师将每天的上班时间划分成 $m$ 段，用一个 $n * m$ 的 $0/1$ 矩阵 $G$ 来表示每天每个时段的会议情况，其中 $G_{i,j} = 1$ 则表示第 $i$ 天的时间段 $j$ 是有一个会议的，$G_{i,j} = 0$ 则表示第 $i$ 天的时间段 $j$ 没有会议

而张老师每天的工作时长可以简单理解为从 每天第一次会议 的时间开始上班，到今天最后一次会议 的时间下班。具体地，若最早、最晚会议的位置分别为 $l,r$，则当天时长为 $r-l+1$；若没有会议，则时长为 $0$

例如一天的会议情况是 $[0,1,1,0,1]$，那么张老师的工作时长就是 $4$

现在张老师想知道，如何使用这 $k$ 张 "会议取消券" 可以使得他接下来这 $n$ 天总的上班时长最短？

输入格式

输入第一行包含两个整数 $n,m$ 含义如题

接下来 $n$ 行每行包含 $m$ 个整数 $G_{i,j}$，用空格隔开，表示会议情况

接下来一行输入一个整数 $k$，表示会议取消券的数量

输出格式

输出一个整数张老师最小的上班时长

数据范围

对于所有数据保证 $G_{i,j} = 0/1$

样例输入1

4 4
0 0 0 1
1 0 0 1
1 1 0 1
0 0 0 1
3

样例输出1

4

样例解释1

取消第二天的第一个会议和第三天的前两个会议，这样每天上班时长为 $1$，一共 $1 * 4 = 4$

样例输入2

5 5
0 1 0 1 0 
1 1 0 1 1
1 1 0 1 0
0 0 0 1 1
1 1 0 1 1
6

样例输出2

9

对于全部数据，$1\le n,m\le500$，$0\le k\le500$。可以使用不超过 $k$ 张取消券。