### 问题描述 小蓝根据藏宝图走进了一个迷宫，迷宫是一个 $N$ 行， $M$ 列的矩阵，每个格子都埋着一件古董，每个古董都有相应的价值 $Ai$ ，迷宫的入口在迷宫的左上角 `(1,1)`，出口在右下角 `(N,M)`，小蓝现在位于迷宫入口，想要拿取尽可能贵重的古董后离开。 小蓝想要带走这些古董必须要按以下的规则： - 小蓝只能向下或向右走，即位于 `(X,Y)` 时，小蓝只能走到 `(X,Y+1)` 或者 `(X+1,Y)`，且小蓝走动时不能超出迷宫范围。 - 小蓝的背包有容量上限，他的背包里最多装下 $K$ 个古董。 - 小蓝很贪婪，所以他到了某个格子，只有当背包为空，或者这个古董的价值大于等于之前拿的任一古董的价值的话，小蓝会将这个古董拿走。 请问小蓝在离开迷宫后，背包内古董的价值和最大是多少，输出一个正整数表示最大价值。 ### 输入格式 输入一行，包含三个整数 $N，M，K$，其含义如上所述。 接下来 $N$ 行，每行有 $M$ 个整数 $Ai$ 用来描述迷宫每个格子中古董的价值。 ### 输出格式 输出仅一行，包含一个整数，表示答案。 ### 样例输入 ```text 2 3 4 1 2 3 2 1 3 ``` ### 样例输出 ```text 9 ``` ### 说明 对于这个样例，小蓝的路径为 `(1,1)`$\rightarrow$`(1,2)`$\rightarrow$`(1,3)`$\rightarrow$`(2,3)`，路径上的古董全部拿取，一共拿了 $4$ 件，价值和为 $9$。 ### 评测数据规模 对于 $60\%$ 的数据，有 $1 \leq N \leq 5$，$1 \leq M \leq 5$，$1 \leq K \leq 10$。 对于 $100\%$ 的数据，有 $1 \leq N \leq 50$，$1 \leq M \leq 50$，$1 \leq K \leq 100$，$1 \leq A_i \leq 64$。