该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

🏀 湘北队的饮料冰柜

文件读写

输入文件：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 \times 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$ 号冰柜，得到收入 $2+3=5$ 元，此时 $3 \sim 4$ 号冰柜各剩 1 瓶。
• 第二天：樱木选择补 $1 \sim 2$ 号冰柜，得到收入 $4+5+0+6=15$ 元，此时 $1 \sim 2$ 号冰柜各剩 1 瓶。
• 第三天：樱木再次选择补 $3 \sim 4$ 号冰柜，得到收入 $0+7+8+9=24$ 元。
• 总计收入：$5+15+24=44$ 元。