20160105 - 方格取数
Time Limit : 1 秒
Memory Limit : 128 MB
在 n 行、 m 列的方格矩阵中,每个方格都包含一个数字。小明可以从任意方格出发开始移动。每次移动可以移到与当前方格有一条边相邻的方格(即向上、下、左或右方向移动 1 格,且不能移出边界)。除此之外,你移动到的方格中的数字必须比当前方格中的数字更大。 请你帮助小明编程规划移动路径,使路径上经过的所有数字之和最大。 本题方格中的数据根据输入的初始数字 s 按照如下算法生成: for i = 1, 2, … n for j = 1, 2, … m s ← (s × 345) mod 19997 矩阵第 i 行第 j 列方格中的数字为(s mod 10) + 1
Input
正整数 n, m (方格的大小), s (数据生成器的初始数值)。 1 ≤ n,m ≤ 100, 1 ≤ s ≤19,997。
Output
所有合法路径中的最大数字和。
Examples
Input
4 5 97
Output
24
Input
40 50 1
Output
47
Hint
样例数据 1 对应的矩阵如下。图中路径数字之和 4 + 5 + 7 + 8 = 24。