4393: D-翘课(skip)
内存限制:512 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:2
解决:1
题目描述
### D-翘课(skip)
小 C 进入大学后,经常被各种各样奇奇怪怪的课搞得心烦意乱。
而且由于教学楼与宿舍离得特别远,为了减少通勤时间,小 C 不得已只能在每天的第一节课到教学楼,然后一直在教学楼呆着(即使中间可能没有课了),直到最后一节课结束才会回寝室。
小 C 不想在教学楼呆很长时间,于是小 C 萌生了一个邪恶的想法,翘课!
在小 C 的世界里,一天有 $m$ 个小时。小 C 得知了他接下来的 $n$ 天每个小时的课程安排 $a_{i,j}$,若 $a_{i,j}=1$ 则表示小 C 在第 $i$ 天的第 $j$ 个小时在教学楼有一节课。
对于第 $i$ 天,记 $a$ 为最小的 $j$ 使 $a_{i,j}=1$, $b$ 为最大的 $j$ 使 $a_{i,j}=1$,则小 C 呆在教学楼的时间就是 $b-a+1$ 。
在最多翘 $k$ 节课的情况下,小 C 想让你求出他在接下来这 $n$ 天在教学楼呆的时间和最小是多少。
输入
第一行三个整数 $n,m,k$ 。
接下来 $n$ 行,每行 $m$ 个整数,表示 $a_{i,j}$ ,含义如题。
输出
一行一个整数,表示答案。
样例输入 复制
4 4 3
1 0 0 0
1 0 0 1
1 1 0 1
0 0 0 1
样例输出 复制
4
提示
#### 输入一
```
4 4 3
1 0 0 0
1 0 0 1
1 1 0 1
0 0 0 1
```
#### 输出一
```
4
```
#### 样例解释
小 C 可以选择翘第 $2$ 天的第 $1$ 个小时的课,第 $3$ 天的第 $1$ 个小时的课和第 $2$ 小时的课。
对于所有数据 $n,m,k\le 500,0\le a_i\le 1$ 。
| 测试点 | 数据范围 | 特殊性质 |
| :---------: | :---------: | ---------- |
| $1\sim 3$ | $n,m\le 4$ | 无 |
| $4\sim 7$ | $m=3$ | 无 |
| $8\sim 11$ | $m\le 9$ | 无 |
| $12\sim 13$ | $n,m\le 50$ | 无 |
| $14\sim 16$ | 无限制 | $\text{A}$ |
| $17\sim 20$ | 无限制 | 无 |
$\text A:$ 保证每天小 C 最多只有 $2$ 个小时有课。