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马车运货所走的最少距离之和。