题目描述

在 $n$ 行 $m$ 列的方格矩阵中，每个方格都包含一个数字。小明可以从任意方格出发开始移动。每次移动可以移到与当前方格有一条边相邻的方格（即向上、下、左或右方向移动 $1$ 格，且不能移出边界）。除此之外，你移动到的方格中的数字必须比当前方格中的数字更大。

请你帮助小明编程规划移动路径，使路径上经过的所有数字之和最大。

输入格式

一行三个正整数 $n,m,s$。

本题方格 $a$ 中的数据根据输入的初始数字 $s$ 按照如下算法生成：

输出格式

所有合法路径中的最大数字和。

4 5 97

24

40 50 1

47

提示

样例 $\textbf 1$ 解释

样例数据 1 对应的矩阵如下。图中路径数字之和 $4+5+7+8=24$。

数据范围

$1\le n,m\le 100,1\le s\le 19997$。

本题原始满分为 $20\text{pts}$。