小 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。如果这一天一节课都没有，那么小 C 不需要去教学楼，呆的时间为 0。

在最多翘 k 节课的情况下，小 C 想让你求出他在接下来这 n 天在教学楼呆的时间和最小是多少。

注意：翘掉的课必须原本存在；同一节课不能重复计数。

第一行三个整数 n, m, k。

接下来 n 行，每行 m 个整数，表示 a_{i,j}，含义如题。

一行一个整数，表示答案。

样例 1 解释

小 C 可以翘第 2 天的第 1 个小时的课、第 3 天的第 1 个小时与第 2 个小时的课。

此时四天呆在教学楼的时间分别是 1, 1, 1, 1，总和为 4。

数据范围

对于所有数据，n, m, k \le 500,\ 0 \le a_{i,j} \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 号测试点：每天都最多只有 2 个小时有课；
• 17 \sim 20 号测试点：无特殊性质。

提示

每天是相互独立的，只在「总共翘了多少节」这一个维度上耦合。

第一步：对第 i 天预处理 g_i(t)，表示这一天翘掉 t 节课后留在教学楼的最短时间。翘完课之后，剩下的课一定是原来有课的那些小时里的一个连续段 [l, r]，于是 g_i(t) 只需枚举这个连续段的首尾两节真实存在的课得到（t 就是这两节之外被翘掉的课数）。

第二步：把每一天当成一组物品做分组背包，dp(j) 表示前若干天一共翘了 j 节课的最小总时间，转移 dp'(j) = \min_{t \le j} \{ dp(j - t) + g_i(t) \}，总复杂度 O(nk^2)。