Easy MaxSum
There is a rectangular table of size m rows and n columns. Each cell of the table contains a number. It is necessary to pass the table from top to bottom: starting from some cell at the top row, each time moving into one of the "lower neighboring" cells (in other words, from the cell (i, j) its possible to go to (i + 1, j - 1) or to (i + 1, j) or to (i + 1, j + 1); in the case j = n only the 1-st and 2-nd variants are possible, in the case j = 1 - only the 2-nd and 3-rd) and finish the route in any cell of the bottom row.
Write a program that finds the maximum possible sum of cell's values among all valid paths and the number of ways in which this sum is reached. For any test case the number of paths is less than 10^9.
Input
First line contains m and n (2 ≤ m ≤ 200, 2 ≤ n ≤ 40, m ≥ n) - the number of rows and columns. Each of the next m rows contains n integers (each no more than 10^6 by absolute value) - the values of the table cells.
Output
Print two numbers - the maximum sum and the number of routes.
