该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

最近企鹅公司新出了一个游戏，特别火爆，徐老师自然也不甘人后进入了游戏

结果他发现因为是新游戏推出，游戏爆火，不但玩的人特别多，而且游戏策划为了提高用户在线时长设计了连续 $n$ 天的 开服活动

而在这 $n$ 天中，每天从早上到晚上，游戏策划一共设计了 $m$ 个不同的游戏活动（同一个游戏活动一定在固定时间开始，并且不同的游戏活动时间不会产生冲突）

形式化的来说，也就是每天会有 $m$ 个时间段，每个时间段有一个游戏活动，每天会随机开放其中几个活动供玩家完成

可以用一个日程表格来描述每天的每个活动是否开放（用 $1$ 表示开放，用 $0$ 表示不开放）

例如有 $3$ 天，每天有 $4$ 个时间段：

1 1 0 1 表示第 1 天开放了 1 2 4 三个活动
1 0 0 1 表示第 2 天开放了 1 4 两个活动
0 1 1 0 表示第 3 天开放了 2 3 两个活动

徐老师作为一个高端玩家，自然是要在游戏初期参加每一次的游戏活动，获得奖励，保证自己的角色强度处于第一梯队

但是由于服务器爆火，徐老师发现很多人压根登录不上游戏，但是徐老师作为心悦$10$级会员，每天有一次随时登录的特权！但是如果中途退出了，就要和普通玩家一样排队等待进入游戏

所以徐老师不得已，只能在每天最早开始的活动开始时就登录游戏，并且直到当天最后一个活动结束才能退出游戏

那么也就是说，对于上面的例子，徐老师第 $1,2$ 天的游戏时长会达到 $4$ 个单位时间，第 $3$ 天的游戏时长是 $2$ 个单位时间

这太浪费时间了，要知道徐老师除了是一个高端玩家以外，他还是一个高阶竞赛选手！他还要参加集训！

为了节省时间，徐老师决定——氪金！

作为高贵的心悦$10$级会员，徐老师找到了游戏官方，提出了上面的问题，于是游戏官方送给了徐老师一共 $k$ 张 心悦券

每张 心悦券 可以让徐老师在不登录游戏的情况下完成 $1$ 次活动

现在徐老师想知道，如何使用这些 心悦券 可以让他在这 $n$ 天内的游戏在线时长尽可能短？这样他才能空出更多的时间去参加集训！

P.S. 各位同学请不要学徐老师，徐老师这是非常典型的反面教材，游戏以后有的是时间玩，但是学习错过了这个阶段那就是错过了！暑假训练机不可失！

输入格式

输入第一行包含两个整数 $n,m$，表示开服活动的天数和每天的活动数量

接下来 $n$ 行，每行 $m$ 个数字，分别表示第 $i$ 天第 $j$ 个活动是否开放，其中 $a_{i,j} = 1$ 表示第 $i$ 天第 $j$ 个活动开放，$a_{i,j} = 0$ 则表示不开放

接下来一行包含一个整数 $k$，表示 心悦券 的数量

输出格式

输出一行包含一个整数，表示徐老师最少的在线时长

数据范围

对于所有数据，保证 $k \leq$ 开放的活动总数

样例输入1

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

样例输出1

4

样例解释1

其中一种方案是完成第 $2$ 天的第 $1$ 个活动，第 $3$ 天的 $1,2$ 两个活动

样例输入2

5 5 
1 0 0 0 1 
1 0 1 1 0
1 1 0 1 1 
0 0 0 1 0
1 0 1 0 1 
4

样例输出2

10