CF1304F1 Animal Observation (easy version)
题目描述
简单版与困难版的唯一区别在于 $k$ 的限制。
Gildong 喜欢观察动物，因此他买了两台摄像机，用来在森林中拍摄野生动物的视频。一台摄像机是红色的，另一台是蓝色的。
Gildong 计划连续 $n$ 天拍摄视频，从第 $1$ 天到第 $n$ 天。森林被划分为 $m$ 个区域，编号从 $1$ 到 $m$。他将按照以下方式使用摄像机：
- 在每个奇数天（第 $1$、$3$、$5$ 天等），带红色摄像机到森林，并连续拍摄 $2$ 天。
- 在每个偶数天（第 $2$、$4$、$6$ 天等），带蓝色摄像机到森林，并连续拍摄 $2$ 天。
- 如果在第 $n$ 天开始用某台摄像机拍摄，则该摄像机只拍摄一天。
每台摄像机可以观察森林中连续的 $k$ 个区域。例如，如果 $m=5$ 且 $k=3$，他可以将摄像机放在以下三个区域范围中的一个，连续拍摄两天：$[1,3]$、$[2,4]$ 和 $[3,5]$。
Gildong 已经得知每一天每个区域能看到多少只动物。由于他希望观察到尽可能多的动物，请你帮他计算在 $n$ 天内，如何安放两台摄像机，才能观察到最多的动物。注意，如果两台摄像机在同一天观察到同一片区域，该区域的动物只计数一次。
输入格式
第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n \le 50$，$1 \le m \le 2 \cdot 10^4$，$1 \le k \le \min(m,20)$）——Gildong 计划拍摄的天数、森林的区域数以及摄像机的观察范围。
接下来的 $n$ 行，每行包含 $m$ 个整数。第 $i+1$ 行的第 $j$ 个整数表示第 $i$ 天第 $j$ 个区域能看到的动物数量。每个动物数量在 $0$ 到 $1000$ 之间。
输出格式
输出一个整数，表示最多能观察到的动物数量。
说明/提示
四个示例的最优观察方式如下：
示例 1：
示例 2：
示例 3：
示例 4：
由 ChatGPT 4.1 翻译