Maximum Sum with number of ways

There is a rectangular grid of size n rows and m columns. Each cell of the grid contains one integer. You can start the route from any cell of the top row. Each time you can move to one of the "lower neighbouring" cells (in other words, from the cell number (i, j) its possible to go either to (i + 1, j - 1), or to (i + 1, j) or to (i + 1, j + 1); in the case j = m the last of the three options becomes impossible, in the case j = 1 the first option becomes impossible). And you can finish the route at any cell of the bottom row.

Write a program that finds the maximum possible sum of the values on the cells traversed among all the possible paths and the number of paths in which this amount is reached.

Input

The first line contains numbers n and m (1 ≤ n, m ≤ 200) - the number of rows and columns. Each of the next n lines contains m integers (each number is no more than 10^6 by absolute value) - the values of the cells in the grid.

It is known that the required number of paths with maximum sum does not exceed 10^9.

Output

Print two numbers - the maximum possible sum and the number of paths.

Examples

Note

In the first test the maximum value 42 can be obtained only in one way: 15 + 9 + 9 + 9). In the second test the maximum value 111 can be obtained in three ways: a[1][3] = 100, a[2][2] = 1, a[3][1] = 10, or a[1][3] = 100, a[2][3] = 10, a[3][2] = 1, or a[1][3] = 100, a[2][3] = 10, a[3][3] = 1.