27588번 - Restaurant Opening 다국어

It is said that the three most important factors for determining whether or not a business will be successful are location, location, and location. The Incredible Cooks Preparing Cuisine are opening a new restaurant in the International City Promoting Cooking, and they have hired you to find the optimal location for their restaurant.

You decide to model the city as a grid, with each grid square having a specified number of people living in it. The distance between two grid squares $(r_1,c_1)$ and $(r_2,c_2)$ is $|r_1-r_2|+|c_1-c_2|.$ In order to visit the restaurant, each potential customer would incur a cost equal to the minimum distance from the grid square in which they live to the grid square containing the proposed location of the restaurant. The total cost for a given restaurant location is defined as the sum of the costs of everyone living in the city to visit the restaurant.

Given the current city layout, compute the minimum total cost if the Incredible Cooks Preparing Cuisine select their next restaurant location optimally.

The first line of input contains two integers, $n$ and $m$ ($1 < n,m \le 50$), where $n$ is the number of rows in the city grid and $m$ is the number of columns.

Each of the next $n$ lines contains $m$ integers $g_{ij}$ ($0\le g_{ij}\le 50$), which specifies the number of people living in the grid square at row $i$, column $j$.

Output a single integer, which is the total cost if the restaurant is selected optimally.