文件读写

输入文件shop.in 输出文件shop.out

限制

• 1000ms
• 512MB

题目描述

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

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

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

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

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

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

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

44

样例解释

徐老师第一天给 $3 \sim 4$ 号冰柜补货，$3 \sim 4$ 号客人可以取到羊腿，付费 $2+3=5$ 元，此时 $3 \sim 4$ 号冰柜各剩一份羊腿

徐老师第二天给 $1 \sim 2$ 号冰柜补货，$1 \sim 4$ 号客人可以取到羊腿，付费 $4+5+0+6=15$ 元，此时 $1 \sim 2$ 号冰柜各剩一份羊腿

徐老师第三天给 $3 \sim 4$ 号冰柜补货，$1 \sim 4$ 号客人可以取到羊腿，付费 $0+7+8+9=24$ 元，此时 $3 \sim 4$ 号冰柜各剩一份羊腿

共计收到 $5+15+24=44$ 元