简单版本和困难版本之间的唯一区别是对 $$$k$$$ 的约束。
Gildong 喜欢观察动物,所以他买了两台相机来拍摄森林中野生动物的视频。一台相机的颜色为红色,另一台相机的颜色为蓝色。
Gildong 将拍摄 $$$n$$$ 天的视频,从 $$$1$$$ 天到 $$$n$$$ 天。森林可分为 $$$m$$$ 区域,编号从 $$$1$$$ 到 $$$m$$$。他将按以下方式使用相机:
- 在每个奇数日($$$1$$$-st、$$$3$$$-rd、$$$5$$$-th,...),将红色摄像机带到森林并录制 $$$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$$$-st 行中的第 $$$j$$$-th 整数是第 $$$j$$$-th 区域中第 $$$i$$$-th 天可以看到的动物数量。每个动物的数量在 $$$0$$$ 和 $$$1000$$$ 之间(含)。
输出
打印一个整数——可以观察到的动物的最大数量。
示例
输入 #1
4 5 2 0 2 1 1 0 0 0 3 1 2 1 0 4 3 1 3 3 0 0 4
输出 #1
25
输入 #2
3 3 1 1 2 3 4 5 6 7 8 9
输出 #2
31
输入 #3
3 3 2 1 2 3 4 5 6 7 8 9
输出 #3
44
输入#4
3 3 3 1 2 3 4 5 6 7 8 9
输出#4
45
注意
四个例子中观察动物的最佳方式如下:
示例 1:
示例 2:
示例 3:
示例 4: