Bob is on a game show, and he's about to earn up to a thousand dollars™!

The game show consists of a large \(N\) by \(M\) grid consisting of digits from \(0\) to \(9\), Bob starts from the top left corner of the grid and has to make his way down to the bottom right corner. For all tiles in the grid Bob can walk to its neighboring tiles that share a common side. This would be represented as going left, right, up, and down in the grid.

The prize of the show is \(1\,000\) dollars subtracted by the amount of "debt" he racks up from the grid. For every grid tile he visits he subtracts the tile's value from the prize money. For example, stepping on a grid with a digit of 6 will subtract \(6\) from \(1\,000\), updating the prize money to \(994\).

What's the maximum amount of money Bob can earn in the game show? Note that the prize money cannot go below \(0\) dollars.

Python users are recommended to submit their solution in PyPy over Python.

Input Specification

The first line of the input will contain two integers \(N\) and \(M\) \((1 \le N, M \le 1\,000)\), indicating the dimensions of the grid.

The next \(N\) lines will each contain a string of \(M\) digits from \(0\) to \(9\), representing the grid used in the game show.

Both the starting tile and ending tile will always be a \(0\) tile.

Output Specification

Output an integer, representing the maximum amount of money Bob can earn.

Sample Input 1

2 3
082
140

Sample Output 1

995

Sample Explanation 1

Bob can earn \(995\) dollars with the following steps:

• Bob walks to the 1 tile, costing him \(1\) dollar. The prize money is now \(999\).
• Bob walks to the 4 tile, costing him \(4\) dollars. The prize money is now \(995\).
• Bob walks to the 0 tile. This marks the end of the game show and Bob wins \(995\) dollars.