F. Lost in the Album Store
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Lost in the Supermarket
The Clash, London Calling (Remastered)

George was perusing the local album store when he received an urgent message: a club was handing out free lollipops on Speedway! Determined to take advantage of such an opportunity, George decided to escape the album store as quickly as possible.

He found himself in row $$$n$$$ and column $$$m$$$, the southeast corner of the store, and wants to get to row $$$1$$$ column $$$1$$$, the exit in the northwest corner. In this store, each grid cell in row $$$i$$$ and column $$$j$$$ has a record of value $$$r_{i,j}$$$. When George takes a step in a direction, he considers shopping more and pauses for a time equal to the square of the sum of record values that are in front of him along the row or column in which he moved. For example, if George is in position $$$(i, j)$$$ and takes a step to position $$$(i - 1, j)$$$, he waits a time equal to $$$(\sum^{i-2}_{q=1} r_{q,j})^2$$$. Likewise, if he takes a step to position $$$(i, j - 1)$$$, he waits a time equal to $$$(\sum^{j-2}_{q=1} r_{i,q})^2$$$. George can move only towards the exit, so he can move only north or west.

What's the minimum time in which George can exit the album store?

Input

The first line contains two integers, $$$n$$$ and $$$m\ (1 \leq n, m \leq 1000)$$$ — the row and column George starts in.

The next $$$n$$$ lines each contain $$$m$$$ integers, with the $$$j^\text{th}$$$ element of the $$$i^\text{th}$$$ line denoting $$$r_{i,j}\ (0 \leq r_{i,j} \leq 50)$$$ — the value of the record in row $$$i$$$ and column $$$j$$$.

Output

Output a single integer, the minimum time required to reach the exit.

Example
Input
3 4
5 2 3 4
3 3 2 2
0 1 1 6
Output
5
Note

George starts at position $$$(3, 4)$$$, which is on the $$$6$$$.

He takes his first step to $$$(3, 3)$$$ and waits a time equal to $$$(1 + 0)^2 = 1$$$.

He takes his second step to $$$(3, 2)$$$ and waits a time equal to $$$0^2 = 0$$$.

He then takes a step to $$$(2, 2)$$$ and waits a time equal to $$$2^2 = 4$$$.

From here, he can take either path to $$$(1, 1)$$$, both of which have zero cost.