#YHDF1381. 方格取数

方格取数

问题描述

nn 行、mm 列的方格矩阵中,每个方格都包含一个数字。小明可以从任意方格出发开始移动。每次移动可以移到与当前方格有一条边相邻的方格(即向上、下、左或右方向移动 11 格,且不能移出边界)。除此之外,你移动到的方格中的数字必须比当前方格中的数字更大。 请你帮助小明编程规划移动路径,使路径上经过的所有数字之和最大。 本题方格中的数据根据输入的初始数字 ss 按照如下算法生成:

for i = 1, 2, ... n
  for j = 1, 2, ... m
    s ← (s × 345) mod 19997
矩阵第 i 行第 j 列方格中的数字为(s mod 10) + 1

输入格式

正整数 nn, mm (方格的大小), ss (数据生成器的初始数值)。 1n,m1001 ≤ n,m ≤ 1001s19,9971 ≤ s ≤ 19,997

输出格式

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

数据范围

样例 11 输入44 55 9797,就会产生如下图所示的矩阵,那么所有合法路径中最大数字和为:4+5+7+8=244 + 5 + 7 + 8 = 24
9 7 10 10 8 2 9 2 5 3 2 5 5 7 7 5 8 4 8 5

样例

输入 #1

4 5 97

输出 #1

24

输入 #2

40 50 1

输出 #2

47