Almost maximum#10003
You have a rectangular table with rows and columns, filled with natural numbers not greater than . Your task is to traverse from the top-left corner to the bottom-right corner, moving only right or down, while summing the numbers in the cells you pass through. The objective is to find the maximum possible sum you can collect this way.
Additionally, we define a path as "almost maximum" if the sum of the numbers collected differs from the maximum sum by no more than (0 \le K \le 100). These paths must also start at the top-left corner and end at the bottom-right corner, with movements restricted to right or down. Your task is to determine how many such almost maximum paths exist. Since this number can be very large, you should output the remainder when this number is divided by .
The first line contains three natural numbers: (2 \le N \le 300), (2 \le M \le 300), and (0 \le K \le 100). Each of the next lines contains natural numbers, each not exceeding , representing the table's contents. Numbers in a row are separated by a single space.
The first line should display a single natural number: the maximum sum that can be collected by moving according to the rules from the top-left to the bottom-right corner. The second line should display a single integer: the remainder when the number of almost maximum paths is divided by .
Example 1
Example 2