题目描述

小A每天都有许多工作会议。他希望减少上班时长，于是老板给了他 $k$ 张“会议取消券”。每张券可以取消一场会议，小A可以使用至多 $k$ 张券，也可以保留一些券不用。

小A统计了接下来 $n$ 天的会议安排。每天的时间被划分为 $m$ 个时段，用一个 $n\times m$ 的 $0/1$ 矩阵 $G$ 表示：$G_{i,j}=1$ 表示第 $i$ 天的第 $j$ 个时段有一场会议，$G_{i,j}=0$ 表示该时段没有会议。

取消部分会议后，如果某天仍有会议，设当天最早和最晚的会议分别位于时段 $l,r$，则小A当天的上班时长为 $r-l+1$。如果当天没有会议，则当天的上班时长为 $0$。

例如，一天的会议安排为 $[0,1,1,0,1]$，在不取消会议时，上班时长为 $5-2+1=4$；如果当天只剩一场会议，上班时长为 $1$。

请计算：使用至多 $k$ 张会议取消券后，这 $n$ 天的上班时长之和最小是多少？

输入格式

从文件 horse.in 中读入数据。

第一行包含两个整数 $n,m$，分别表示天数和每天的时段数。

接下来 $n$ 行，每行包含 $m$ 个整数，其中第 $i$ 行的第 $j$ 个整数为 $G_{i,j}$。

最后一行包含一个整数 $k$，表示会议取消券的数量。

输出格式

输出到文件 horse.out 中。

输出一行，包含一个整数，表示最小的总上班时长。

样例 1 输入

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

样例 1 输出

4

样例 1 解释

取消第二天的第一场会议，以及第三天的前两场会议。这样每天都恰好剩下一场会议，每天上班时长均为 $1$，总上班时长为 $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

样例 3

见选手目录下的 horse/horse3.in 与 horse/horse3.ans。

该样例满足第 $4\sim6$ 个测试点的限制，且 $n=500,m=3,k=500$。

样例 4

见选手目录下的 horse/horse4.in 与 horse/horse4.ans。

该样例满足第 $7\sim8$ 个测试点的限制，且 $n=m=50,k=500$。

样例 5

见选手目录下的 horse/horse5.in 与 horse/horse5.ans。

该样例满足第 $9\sim10$ 个测试点的限制，且 $n=m=500,k=500$，每天至多有两场会议。

样例 6

见选手目录下的 horse/horse6.in 与 horse/horse6.ans。

该样例满足第 $11\sim20$ 个测试点的限制，且 $n=m=k=500$。

数据范围

对于所有测试数据，保证 $1\le n,m\le500$，$0\le k\le500$，$G_{i,j}\in\{0,1\}$。

共有 $20$ 个测试点，每个测试点 $5$ 分。

测试点	$n$	$m$	特殊性质
$1\sim3$	$\le4$		无
$4\sim6$	$\le500$	$=3$
$7\sim8$	$\le50$
$9\sim10$	$\le500$		每天至多两场会议
$11\sim20$			无

“每天至多两场会议”指对于每个 $1\le i\le n$，都有 $\sum_{j=1}^mG_{i,j}\le2$。