Дано прямоугольное поле размера $$$m \times n$$$. В левой верхней клетке с координатами $$$(1, 1)$$$ — стартовой — стоит жираф. Он хочет попасть в правую нижнюю клетку с координатами $$$(m, n)$$$ — финишную. Каждой клетке поля соответствует целое число — количество деревьев в ней.
Жираф умеет делать ходы двух видов: на $$$k$$$ клеток вниз и $$$1$$$ клетку вправо; или на $$$k$$$ клеток вправо и $$$1$$$ вниз. Жираф хочет пройти по полю из стартовой клетки в финишную, в конце каждого хода поедая листья на деревьях в клетке, в которую он пришёл. В стартовой клетке он ничего не ест. При этом каждый чётный ход жираф чувствует себя голодным, поэтому съедает $$$3t$$$ листьев, а каждый нечётный ход чувствует себя объевшимся, поэтому съедает только $$$t$$$ листьев, где $$$t$$$ — количество деревьев на клетке. Ходы нумеруются с единицы.
Выясните, какое наибольшее количество листьев жираф может съесть в своём путешествии.
В первой строке заданы через пробел два целых числа: $$$m$$$ и $$$n$$$ ($$$1 \le m, n \le 100$$$).
Во второй строке задано число целое $$$k$$$ ($$$1 \le k \le \min (m, n)$$$).
В следующих $$$m$$$ строках записано по $$$n$$$ чисел в каждой; $$$j$$$-е число $$$i$$$-й из этих строк соответствует количеству деревьев в клетке $$$(i, j)$$$, это целое число в диапазоне от $$$0$$$ до $$$100$$$, включительно.
Выведите одно число — наибольшее количество листьев, которое может съесть жираф по пути из стартовой клетки в финишную. Если таких путей нет, выведите $$$-1$$$.
2 211 11 1
1
3 521 2 0 3 12 4 5 7 83 0 7 1 0
5
3 211 32 41 2
-1
