← 返回题目列表

Codeforces · 946/D

D. 时间表

中文机器翻译题面 查看原题

Ivan 是伯兰州立大学 (BSU) 的学生。 Berland 周有 n 天,每一天 Ivan 都可能在大学上一些课。

Berland 每天有 m 个工作时间,大学的每节课正好持续一小时。如果有一天 Ivan 的第一节课是在第 i 个小时,最后一课是在第 j 个小时,那么他这一天在大学里度过了 j - i + 1 个小时。如果某天没有课,那么 Ivan 就会呆在家里,因此在大学的时间为 0 小时。

Ivan 不喜欢在大学里度过很多时间,因此他决定跳过一些课程。他一周内不能跳过超过 k 节课。在决定了他应该跳过哪些课程以及应该参加哪些课程后,伊万每天都会在他不跳过的第一堂课开始之前进入大学,并在他决定参加的最后一堂课结束后离开。如果 Ivan 在某一天逃了所有课程,那么他那天就根本不会去大学。

给定 n、m、k 和 Ivan 的时间表,如果他不能跳过超过 k 节课,你能确定他一周内必须在大学度过的最少小时数吗?

输入

第一行包含三个整数 n、m 和 k (1 ≤ n, m ≤ 500, 0 ≤ k ≤ 500) — 分别是 Berland 周的天数、每天的工作时间以及 Ivan 可以跳过的课程数。

接下来是 n 行,第 i 行包含 m 个字符的二进制字符串。如果第i行中的第j个字符为1,则Ivan在第i天的第j个小时有课(如果为0,则没有该课)。

输出

打印如果 Ivan 跳过不超过 k 节课,他在一周内必须在大学度过的最少小时数。

示例

输入 #1

2 5 1
01001
10110

输出 #1

5

输入 #2

2 5 0
01001
10110

输出 #2

8

注意

在第一个示例中,Ivan 可以在第一天跳过两节课中的任意一节,因此他在第一天花费 1 小时,在第二天花费 4 小时。

在第二个示例中,Ivan 不能逃课,因此他每天要花 4 个小时。