Table of numbers

Submit solution
Points: 3 (partial)
Time limit: 1.0s
Memory limit: 67M
Author:
creator
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

You are given a \(m\)x\(n\) grid, each cell contains a number (cell's value) represented by a matrix \((a_{ij})_{n*m}\) (indexed from \(1\)). From cell \((i, j)\) (cell at row \(i\) column \(j\)) you can go to cell \((i + 1, j)\) if its value is greater than \(0\), the same applies to cell \((i, j + 1)\). Each time stop at a cell, its value is added to calculate the cost of your path.

Your task is to find the minimum cost when you move from the top left corner to the bottom right corner of the table, and the number of paths with that cost.

Input

The first line contains two integer \(m\) and \(n\) \((1 \le m, n \le 2000)\), number of rows and number of columns.

The next \(m\) lines each contain \(n\) non-negative integers not exceeding \(1000\) describing rows of matrix.

Output

Two integers, respectively are the minimum cost and number of paths with that cost.

Note: It is guaranteed that the number of paths is positive and does not greater than \(10^9\).

Subtask

\(30\%\) of testcases have \(m*n \le 100\), all cell's values are positive.

Example

Input:

3 5
1 1 1 2 5
5 9 1 1 0
8 0 1 1 1

Output:

7 2
QDUY

Comments