monede

The safe of the Romanian Bank is comprised of N rows of M drawers of equal sizes, placed one next to another. In the morning, when the bank opens, all the drawers will be closed. During the day the bank will receive money (coins) and the bank's employees will place the coins in the drawers in random order. At the end of the day a robot has to rearrange the coins in such a way that all open drawers contain the same number of coins. It will disregard closed drawers. The robot only moves horizontally or vertically. The effort made by the robot to move P coins is equal to P*nr, where nr is the number of drawers the robot passes by.

Task

Write a program that finds the minimum effort made by the robot to rearrange the coins. The existence of a solution is guaranteed.

Input Data

Line one of input file monede.in contains positive integers N M separated by a single space.
The following N lines contain M positive integers separated by spaces representing the number of coins in the drawers. If the number of coins is 0 that means that the drawer is closed and that it will be disregarded by the robot.

Output Data

Output file monede.out will contain a single line with the minimum effort written on it.

Constraints

• 1 < N, M < 128
• 2 < number of open drawers < 128
• 0 < number of coins in a drawer < 1024

Example

Time limit: 0.4 seconds/test

Fechete Dan Ionut
University of Bucharest, Mathematics & IT Department
mailto:f.dan.ionut@gmail.com