matrix

Given a matrix with $n$ rows and $m$ columns ( $n+m$ is an odd number ), at first , you begin with the number at top-left corner (1,1) and you want to go to the number at bottom-right corner (n,m). And you must go right or go down every steps. Let the numbers you go through become an array $a_1, a_2, ... , a_{2k}$. The cost is $a_1*a_2+a_3*a_4+...+a_{2k-1}*a_{2k}$. What is the minimum of the cost?

Several test cases(about $5$)

For each cases, first come 2 integers, $n,m(1 \leq n \leq 1000,1 \leq m \leq 1000)$

N+m is an odd number.

Then follows $n$ lines with $m$ numbers $a_i,j ( 1 \leq a_i \leq 100)$

For each cases, please output an integer in a line as the answer.

2 3
1 2 3
2 2 1
2 3
2 2 1
1 2 4

4
8

BestCoder Round #63 (div.2)