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 个小时。