3901: 张老师的羊腿小店
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
张老师最近开了一家羊腿小店！
在这家店里，张老师摆了 $n$ 个羊腿冰柜，一字排开，编号分别为 $1 \sim n$
一开始这些冰柜都是空的，张老师每天在营业前会选择连续的 $k$ 个冰柜进行补货。
每次张老师给一个冰柜补货时，会先取出冰柜里的羊腿收走（如果存在），再放入两人份的羊腿到这个冰柜。
接下来 $m$ 天，每天都有 $n$ 个客户来取羊腿，$x$ 号客户会取走 $x$ 号冰柜里的一份羊腿，如果这个客户能取到羊腿则会付给张老师钱，否则不付钱。
张老师已经提前知道了第 $i$ 天的 $j$ 号客户如果取到羊腿则会付 $a_{i,j}$ 元钱
现在张老师想知道，每天如何进行补货可以让他赚到最多的钱？
P.S. 众所周知张老师很懒，请不要提出让张老师每天都给所有冰柜补货的馊主意
在这家店里，张老师摆了 $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$ 号客户会付的钱
接下来 $m$ 行，每行 $n$ 个整数 $a_{i,j}$ 表示第 $i$ 天的 $j$ 号客户会付的钱
| 测试点编号 | $1 \leq n,m \leq$ | 特殊性质 |
| :---: | :---: | :---: |
| $1 \sim 2$ | $10$ | $k=n$ |
| $3 \sim 6$ | $10$ | 无 |
| $7 \sim 10$ | $1000$ | 无 |
对于所有数据保证：$0 \leq a_{i,j} \leq 1000,1 \leq n * m \leq 500000,1 \leq k \leq min(n,50)$
| :---: | :---: | :---: |
| $1 \sim 2$ | $10$ | $k=n$ |
| $3 \sim 6$ | $10$ | 无 |
| $7 \sim 10$ | $1000$ | 无 |
对于所有数据保证：$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$ 元
张老师第一天给 $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$ 元