时间限制： 1.0 秒

空间限制： 512 MB

题目描述

在一个古老的魔法森林中，有一个由 $n\times m$ 个魔法石组成的网格。每个魔法石都蕴含一定的魔法能量（非负整数），这些能量可以帮助森林守护者 Bob 增强他的魔力，其中第 行第 列魔法石的能量为 $w_{i,j}$。Bob 从网格的左下角出发，需要到达右上角的圣坛进行仪式。由于森林中的魔法规则，他只能向右或向上移动（向左或向下会破坏魔法流动）。每当 Bob 经过一个魔法石时，他会吸收其魔法能量。Bob 希望尽可能多地收集魔法能量，以便在仪式中释放强大的魔法。请帮助 Bob 找到一条路径，使得吸收的魔法能量之和最大。

以下图为例，Bob 从左下角 $(3,1)$ 出发，行走的路径是 $(3,1),(3,2),(3,3),(2,3),(1,3),(1,4)$，一共取得 $1+2+5+9+2+1=20$ 单位的能量，可以证明这条路径吸收的魔法能量之和最大。

输入格式

从标准输入读入数据。

由于测试数据读入量较大，本题将使用统一的随机数生成器生成测试数据。输入第一行包含三个正整数 $n,m,seed$，其中 $n$ 和 $m$ 的意义由题面所示，$seed$ 为测试样例用于生成随机数的种子。

接下来，选手应使用统一的随机数生成器，并调用其中的 next_INT() 方法共计 $n\times m$ 次。next_INT() 方法前 $m$ 次调用依次返回 $w_{1,1},w_{1,2},\cdots,w_{1m}$，接下来 $m$ 次调用依次返回 $w_{2,1},w_{2,2},\cdots,w_{2,m}$，以此类推，直到生成所有的 $w_{i,j}$。形式化地，第 $k$ 次调用 next_INT() 方法返回的是 $w_{i,j}$，其中 $i=\lfloor (k-1)/m \rfloor+1,~j=\lfloor [(k-1)\bmod m] +1 \rfloor$。

随机数生成器的具体使用方法详见说明部分。

输出格式

输出到标准输出。

输出一个整数，表示魔法能量的最大值。

3 4 114514

2402788932

样例 1 解释

由随机数生成器生成的 $3\times 4$ 矩阵如下：

$$\left[\begin{matrix} 646759049 & 556330580 & 158790051 & 405150374 \\ 434304461 & 4226424008 & 508696967 & 210362682 \\ 201454417 & 24727164 & 159464363 & 367401230 \end{matrix} \right] $$

总共收集到 $201454417+434304461+646759049+556330580+158790051+405150374=2402788932$ 单位的魔法能量。

子任务

对于 $30\%$ 的数据，满足 $1\le m,n\le 10$；

对于 $100\%$ 的数据，满足 $1\le m,n\le 2000,~0\le w_{i,j}\le 10^9,~0\le seed\le 10^9$。

说明

选手可根据参赛语言自选相应的随机数生成器版本。

对于 C++ 选手，可使用输入的种子初始化 RNG 对象，然后通过调用对象的 next_INT() 方法生成下一个随机数。

#include <iostream>
// C++ 选手统一使用的随机数生成器
class RNG
{
private:
    // 所有选手使用的参数固定不变，不要修改
    unsigned long long seed;
    static const unsigned long long a = 1664525;
    static const unsigned long long c = 1013904223;
    static const unsigned long long m = 1ULL << 32;
    static const unsigned long long range = 1e9;

public:
    RNG(unsigned long long s) { seed = s; }
    unsigned long long next_INT()
    {
        seed = (a * seed + c) % m;
        return seed % range;
    }
};
// 示例代码
int main()
{
    int seed;
    std::cin >> seed;
    RNG rng(seed);                            // 设置随机数生成器的种子
    std::cout << rng.next_INT() << std::endl; // 生成下一个随机数并输出
    return 0;
}

对于 C 选手，可使用输入的种子通过 init_RNG(RNG *rng, unsigned long long s) 函数初始化 RNG 结构体，然后通过调用 next_INT(RNG *rng) 函数生成下一个随机数。

#include <stdio.h>
// C 选手统一使用的随机数生成器
typedef struct
{
    unsigned long long seed;
} RNG;
// 所有选手使用的参数固定不变，不要修改
const unsigned long long A = 1664525ULL;
const unsigned long long C = 1013904223ULL;
const unsigned long long M = 1ULL << 32;
const unsigned long long RANGE = 1000000000ULL;
// 初始化随机数生成器
void init_RNG(RNG *rng, unsigned long long s)
{
    rng->seed = s;
}
// 生成下一个随机整数
unsigned long long next_INT(RNG *rng)
{
    rng->seed = (A * rng->seed + C) % M;
    return rng->seed % RANGE;
}
// 示例代码
int main(void)
{
    unsigned long long seed;
    scanf("%lld", &seed);
    RNG rng;
    init_RNG(&rng, seed);             // 设置随机数生成器的种子
    printf("%lld\n", next_INT(&rng)); // 生成下一个随机数并输出
    return 0;
}

对于 python 选手，可使用输入的种子初始化 RNG 对象，然后通过调用对象的 next_INT() 方法生成下一个随机数。

# python 选手统一使用的随机数生成器
class RNG:
    # 所有选手使用的参数固定不变，不要修改
    a = 1664525
    c = 1013904223
    m = 1 << 32
    range = int(1e9)
    def __init__(self, s):
        self.seed = s
    def next_INT(self):
        self.seed = (RNG.a * self.seed + RNG.c) % RNG.m
        return self.seed % RNG.range

# 示例代码
def main():
    seed = int(input())
    rng = RNG(seed) # 设置随机数生成器的种子
    print(rng.next_INT()) # 生成下一个随机数并输出

if __name__ == "__main__":
    main() 

对于 java 选手，可使用输入的种子初始化 RNG 对象，然后通过调用对象的 next_INT() 方法生成下一个随机数。

import java.util.Scanner;

// java 选手统一使用的随机数生成器
class RNG {
    // 所有选手使用的参数固定不变，不要修改
    private long seed;
    private static final long a = 1664525L;
    private static final long c = 1013904223L;
    private static final long m = 1L << 32;
    private static final long range = (long) 1e9;
    
    public RNG(long s) {
        seed = s;
    }

    public long next_INT() {
        seed = (a * seed + c) % m;
        return seed % range;
    }
}

// 示例代码
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long seed = sc.nextLong();
        RNG rng = new RNG(seed); // 设置随机数生成器的种子
        System.out.println(rng.next_INT()); // 生成下一个随机数并输出
        sc.close();
    }
}