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

糖果寻宝录

题目背景

游园会的最后一项挑战是“糖果迷宫”。这是一个巨大的 $N \times M$ 的网格迷宫。小朋友需要从迷宫的左上角入口 $(1,1)$ 出发，最终到达右下角的出口 $(N,M)$。每次移动，小朋友只能向右走一格，或者向下走一格。迷宫的每一个格子里都放着一定数量的糖果，走到该格子就可以将糖果收入囊中。 最特别的是，入口处会发给每个小朋友一台“魔法相机”。在到达任意一个格子时，如果对着该格子使用魔法相机，就可以让该格子里的糖果数量瞬间翻倍！ 不过，这台魔法相机非常消耗能量，它虽然可以无限次使用，但每次使用后都需要一段时间来“充能”。具体来说，两次使用之间必须至少经过 $D$ 个格子。也就是说，如果你在总步数为 $S_1$ 时使用了一次相机，那么下一次使用至少要在总步数达到 $S_1 + D$ 时才能使用（起点 $(1,1)$ 的步数记为 $0$，走一步算增加 $1$ 个步数）。

题目描述

给定一个 $N \times M$ 的网格，第 $i$ 行第 $j$ 列的格子有 $A_{i,j}$ 颗糖果。 你可以从 $(1,1)$ 出发，每次只能向右走到 $(i, j+1)$ 或向下走到 $(i+1, j)$，直到走到 $(N,M)$。 途中你可以多次使用魔法相机使得当前格子的糖果数 $\times 2$。但必须满足：任意两次使用相机的格子之间，由于只能向右或向下走，它们之间的曼哈顿距离（即行数差与列数差的绝对值之和）必须大于等于 $D$。 请你计算，从起点到终点，最多能收集到多少颗糖果？（你可以选择一次相机也不用）。

输入格式

第一行包含三个正整数 $N, M, D$，分别表示迷宫的行数、列数，以及魔法相机的充能冷却距离。 接下来 $N$ 行，每行包含 $M$ 个正整数，表示每个格子的糖果数量 $A_{i,j}$。

输出格式

输出一行一个整数，表示最多能收集到的糖果总数。

样例输入 #1

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

样例输出 #1

46

数据范围

对于 $30\%$ 的数据，$1 \le N, M \le 10$。 对于 $60\%$ 的数据，$1 \le N, M \le 100$。 对于 $100\%$ 的数据，$1 \le N, M \le 1000$，$1 \le D \le 15$，$1 \le A_{i,j} \le 1000$。