English · Original
Chinese · Translation
Formal · Original
Ivan is a student at Berland State University (BSU). There are _n_ days in Berland week, and each of these days Ivan might have some classes at the university.
There are _m_ working hours during each Berland day, and each lesson at the university lasts exactly one hour. If at some day Ivan's first lesson is during _i_\-th hour, and last lesson is during _j_\-th hour, then he spends _j_ - _i_ + 1 hours in the university during this day. If there are no lessons during some day, then Ivan stays at home and therefore spends 0 hours in the university.
Ivan doesn't like to spend a lot of time in the university, so he has decided to skip some lessons. He cannot skip more than _k_ lessons during the week. After deciding which lessons he should skip and which he should attend, every day Ivan will enter the university right before the start of the first lesson he does not skip, and leave it after the end of the last lesson he decides to attend. If Ivan skips all lessons during some day, he doesn't go to the university that day at all.
Given _n_, _m_, _k_ and Ivan's timetable, can you determine the minimum number of hours he has to spend in the university during one week, if he cannot skip more than _k_ lessons?
## Input
The first line contains three integers _n_, _m_ and _k_ (1 ≤ _n_, _m_ ≤ 500, 0 ≤ _k_ ≤ 500) — the number of days in the Berland week, the number of working hours during each day, and the number of lessons Ivan can skip, respectively.
Then _n_ lines follow, _i_\-th line containing a binary string of _m_ characters. If _j_\-th character in _i_\-th line is _1_, then Ivan has a lesson on _i_\-th day during _j_\-th hour (if it is _0_, there is no such lesson).
## Output
Print the minimum number of hours Ivan has to spend in the university during the week if he skips not more than _k_ lessons.
[samples]
## Note
In the first example Ivan can skip any of two lessons during the first day, so he spends 1 hour during the first day and 4 hours during the second day.
In the second example Ivan can't skip any lessons, so he spends 4 hours every day.
Ivan 是 Berland 国立大学（BSU）的一名学生。Berland 周有 #cf_span[n] 天，每天 Ivan 可能有一些课程在大学上课。
每个 Berland 日有 #cf_span[m] 个有效工作小时，每节课恰好持续一小时。如果某天 Ivan 的第一节课在第 #cf_span[i] 小时开始，最后一节课在第 #cf_span[j] 小时结束，那么他在这一天在大学花费 #cf_span[j - i + 1] 小时。如果某天没有课程，Ivan 待在家里，因此在大学花费 #cf_span[0] 小时。
Ivan 不喜欢在大学花太多时间，因此他决定逃掉一些课程。他整个星期逃课的总数不能超过 #cf_span[k] 节。在决定哪些课程逃掉、哪些课程参加后，每天 Ivan 都会在他未逃掉的第一节课开始前进入大学，并在他决定参加的最后一节课结束后离开。如果某天 Ivan 逃掉了所有课程，他当天根本不去大学。
给定 #cf_span[n]、#cf_span[m]、#cf_span[k] 和 Ivan 的课表，你能确定他在一周内最少需要在大学花费多少小时吗？他逃课总数不能超过 #cf_span[k] 节。
第一行包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n, m ≤ 500]，#cf_span[0 ≤ k ≤ 500]），分别表示 Berland 周的天数、每天的工作小时数，以及 Ivan 可以逃掉的课程数。
接下来 #cf_span[n] 行，第 #cf_span[i] 行是一个长度为 #cf_span[m] 的二进制字符串。如果第 #cf_span[i] 行的第 #cf_span[j] 个字符是 _1_，则表示 Ivan 在第 #cf_span[i] 天的第 #cf_span[j] 小时有课（如果是 _0_，则没有课）。
请输出 Ivan 在一周内最少需要在大学花费的小时数，前提是逃课总数不超过 #cf_span[k] 节。
在第一个例子中，Ivan 可以逃掉第一天的任意两节课之一，因此他在第一天花费 #cf_span[1] 小时，第二天花费 #cf_span[4] 小时。
在第二个例子中，Ivan 不能逃任何课，因此他每天花费 #cf_span[4] 小时。
## Input
第一行包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n, m ≤ 500]，#cf_span[0 ≤ k ≤ 500]），分别表示 Berland 周的天数、每天的工作小时数，以及 Ivan 可以逃掉的课程数。接下来 #cf_span[n] 行，第 #cf_span[i] 行是一个长度为 #cf_span[m] 的二进制字符串。如果第 #cf_span[i] 行的第 #cf_span[j] 个字符是 _1_，则表示 Ivan 在第 #cf_span[i] 天的第 #cf_span[j] 小时有课（如果是 _0_，则没有课）。
## Output
请输出 Ivan 在一周内最少需要在大学花费的小时数，前提是逃课总数不超过 #cf_span[k] 节。
[samples]
## Note
在第一个例子中，Ivan 可以逃掉第一天的任意两节课之一，因此他在第一天花费 #cf_span[1] 小时，第二天花费 #cf_span[4] 小时。在第二个例子中，Ivan 不能逃任何课，因此他每天花费 #cf_span[4] 小时。
**Definitions**
Let $ n, m, k \in \mathbb{Z} $ denote:
- $ n $: number of days in the week,
- $ m $: number of working hours per day,
- $ k $: maximum number of lessons Ivan can skip.
Let $ T = (T_1, T_2, \dots, T_n) $ be the timetable, where each $ T_i \in \{0,1\}^m $ is a binary string representing Ivan’s schedule on day $ i $.
For day $ i $, let $ L_i = \{ j \in \{1, \dots, m\} \mid T_i[j] = 1 \} $ be the set of hours with lessons.
Let $ \ell_i = |L_i| $ be the number of lessons on day $ i $.
**Constraints**
1. $ 1 \leq n, m \leq 500 $
2. $ 0 \leq k \leq 500 $
3. For each day $ i $, $ 0 \leq \ell_i \leq m $
**Objective**
For each day $ i $, if Ivan attends a non-empty subset $ S_i \subseteq L_i $ of lessons, then the hours spent on day $ i $ is:
$$
h_i(S_i) =
\begin{cases}
\max(S_i) - \min(S_i) + 1 & \text{if } S_i \neq \emptyset \\
0 & \text{if } S_i = \emptyset
\end{cases}
$$
Ivan must choose subsets $ S_1, \dots, S_n $ such that:
$$
\sum_{i=1}^n (\ell_i - |S_i|) \leq k \quad \text{(total skipped lessons ≤ } k\text{)}
$$
Minimize the total weekly hours:
$$
\sum_{i=1}^n h_i(S_i)
$$
API Response (JSON)
{
"problem": {
"name": "D. Timetable",
"description": {
"content": "Ivan is a student at Berland State University (BSU). There are _n_ days in Berland week, and each of these days Ivan might have some classes at the university. There are _m_ working hours during each",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF946D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Ivan is a student at Berland State University (BSU). There are _n_ days in Berland week, and each of these days Ivan might have some classes at the university.\n\nThere are _m_ working hours during each...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Ivan 是 Berland 国立大学（BSU）的一名学生。Berland 周有 #cf_span[n] 天，每天 Ivan 可能有一些课程在大学上课。\n\n每个 Berland 日有 #cf_span[m] 个有效工作小时，每节课恰好持续一小时。如果某天 Ivan 的第一节课在第 #cf_span[i] 小时开始，最后一节课在第 #cf_span[j] 小时结束，那么他在这一天在大学花费 #cf_...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m, k \\in \\mathbb{Z} $ denote: \n- $ n $: number of days in the week, \n- $ m $: number of working hours per day, \n- $ k $: maximum number of lessons Ivan can skip. \n\nLet $...",
"is_translate": false,
"language": "Formal"
}
]
}