Problem1417--PIPI运货Ⅱ

1417: PIPI运货Ⅱ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 59  Solved: 15
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI财大气粗的依靠,便是他的运货业务。
PIPI想在一个n*m的镇上建立一个运货站,每次PIPI的马车从运货站出发,马车只能进行上下左右的移动,然后到达目标地点。但是有些地方需要运货多次,有些地方不需要运货,所以PIPI会得到一份关于运货次数的地图A。
出于节约成本低碳环保考虑,PIPI将运货站建在哪能使马车运货所走的距离之和最少,请求出这个最少距离之和。
PS:运货站可以建在镇上任何地方。

Input

第一行两个正整数n,m,其中n,m<=1000。
接下来n行,每行m个非负整数,其中Aij表示(i,j)处需要运货Aij次,Aij<=1000。

Output

输出PIPI马车运货所走的最少距离之和。

Sample Input

2 2
1 1
1 0

Sample Output

2

Source/Category