Alternative paths#4637
You are given a rectangular table with rows and columns. Each cell in the table contains a natural number not greater than . A traveler needs to navigate from the top-left corner to the bottom-right corner of this table, moving only one cell to the right or one cell down at each step. There are numerous paths to choose from. For each path, you can calculate the sum of the numbers in the cells that are traversed. Among these sums, there is a maximum value. We consider a path good if its sum is either the maximum possible or differs from the maximum by no more than . The number of good paths will not exceed 10^9.
Your task is to write a program that determines the maximum possible sum and counts the number of good paths.
The first line contains three integers: (2 \leq M \leq 200), (2 \leq N \leq 200), and (0 \leq K \leq 200). Each of the next lines contains numbers, representing the values in the respective cells of the table.
The output should consist of two lines. The first line should display the maximum possible sum. The second line should show the number of paths where the sum of the numbers differs from the maximum by no more than .
Example 1