F1. Наблюдение за животными (упрощенная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие этой версии от усложненной это ограничение на $$$k$$$.

Гильдонг любит наблюдать за животными, так он купил две камеры чтобы снимать на видео диких животных в лесу. Цвет одной камеры красный, а цвет другой камеры синий.

Гильдонг собирается снимать видео на протяжении $$$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]$$$.

Гильдонг получил информацию о том, сколько животных видно в каждой зоне каждый день. Так как он хочет наблюдать за как можно большим числом животных, он хочет попросить вас найти лучший способ расставить эти две камеры в $$$n$$$ дней. Обратите внимание, что если две камеры снимают одну и ту же зону в один и тот же день, все животные этой зоны должны быть учтены только один раз.

Входные данные

В первой строке записаны три целых числа $$$n$$$, $$$m$$$, и $$$k$$$ ($$$1 \le n \le 50$$$, $$$1 \le m \le 2 \cdot 10^4$$$, $$$1 \le k \le min(m,20)$$$) — количество дней, которые Гильдонг собирается записывать видео, количество зон в лесу, и диапазон камеры, соответственно.

Следующие $$$n$$$ строк содержат по $$$m$$$ целых чисел. $$$j$$$-е число в $$$i+1$$$-й строке это количество животных, которое можно увидеть в $$$i$$$-й день в $$$j$$$-й зоне. Каждое количество животных от $$$0$$$ и до $$$1000$$$, включительно.

Выходные данные

Выведите одно целое число — максимальное количество животных, за которыми вы можете наблюдать.

Примеры
Входные данные
4 5 2
0 2 1 1 0
0 0 3 1 2
1 0 4 3 1
3 3 0 0 4
Выходные данные
25
Входные данные
3 3 1
1 2 3
4 5 6
7 8 9
Выходные данные
31
Входные данные
3 3 2
1 2 3
4 5 6
7 8 9
Выходные данные
44
Входные данные
3 3 3
1 2 3
4 5 6
7 8 9
Выходные данные
45
Примечание

Оптимальные способы наблюдать за животными в четырех тестовых примерах:

Пример 1:

Пример 2:

Пример 3:

Пример 4: