题目说明

在一个 n 行、m 列的方格矩阵中，每个格子包含一个整数。 可以从 任意一个格子 作为起点开始移动。

每次移动需满足以下条件：

• 只能移动到与当前格子 上下左右相邻 的格子；
• 不能越出矩阵边界；
• 移动到的新格子中的数值必须 严格大于 当前格子的数值。

请你规划一条合法路径，使得路径上经过的所有数字之和最大。

矩阵生成方式

矩阵并非直接输入，而是由初始值 s 按如下规则生成（按行优先）：

for i = 1..n
  for j = 1..m
    s = (s * 345) mod 19997
    a[i][j] = (s mod 10) + 1

因此，矩阵中每个元素的取值范围为 1 到 10。

输入格式

输入一行，包含三个整数 n, m, s：

• n, m 表示矩阵的行数和列数；
• s 表示数据生成器的初始值。

约束条件：

• 1 ≤ n, m ≤ 100
• 1 ≤ s ≤ 19997

输出格式

输出一个整数，表示所有合法路径中能够得到的最大数字和。

样例 1

输入：

4 5 97

输出：

24

说明（仅用于理解，不是输入）：

根据输入生成的矩阵如下：

 9  7 10 10  8
 2  9  2  5  3
 2  5  5  7  7
 5  8  4  8  5

一条取得最大值的合法路径示例如下：

4 → 5 → 7 → 8

对应的路径和为：

4 + 5 + 7 + 8 = 24

样例 2

输入：

40 50 1

输出：

47

提示

由于路径上的数值严格递增，不会形成环。 可以使用深度优先搜索结合记忆化，或等价的动态规划方法求解。