You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

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

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

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

而徐老师每天的工作时长可以简单理解为从 每天第一次会议 的时间开始上班，到今天最后一次会议 的时间下班（这里我们忽略会议开会的时间）

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

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

输入格式

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

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

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

输出格式

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

样例输入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

数据范围

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