题目描述

徐老师最近开了一家羊腿小店！

在这家店里，徐老师摆了 $n$ 个羊腿冰柜，一字排开，编号分别为 $1 \sim n$

一开始这些冰柜都是空的，徐老师每天在营业前会选择连续的 $k$ 个冰柜进行补货。

每次徐老师给一个冰柜补货时，会先取出冰柜里的羊腿收走（如果存在），再放入两人份的羊腿到这个冰柜。

接下来 $m$ 天，每天都有 $n$ 个客户来取羊腿，$x$ 号客户会取走 $x$ 号冰柜里的一份羊腿，如果这个客户能取到羊腿则会付给徐老师钱，否则不付钱。

徐老师已经提前知道了第 $i$ 天的 $j$ 号客户如果取到羊腿则会付 $a_{i,j}$ 元钱

现在徐老师想知道，每天如何进行补货可以让他赚到最多的钱？

P.S. 众所周知徐老师很懒，请不要提出让徐老师每天都给所有冰柜补货的馊主意

输入格式

本题采用文件读写。

• 读入文件名：shop.in
• 写出文件名：shop.out

第一行包含三个整数 $n,m,k$，含义如题

接下来 $m$ 行，每行 $n$ 个整数 $a_{i,j}$ 表示第 $i$ 天的 $j$ 号客户会付的钱

输出格式

输出一个整数表示徐老师最多能赚到的钱

样例

4 3 2
1 0 2 3
4 5 0 6
0 7 8 9

44

数据范围与提示

• 对于所有数据保证：$0 \leq a_{i,j} \leq 1000,1 \leq n * m \leq 500000,1 \leq k \leq min(n,50)$