Minimum Inflation

CAIN organization plans to build a new town on Mars for K families by constructing K adjacent buildings, one for each family. For each family, there are N different building designs available. The buildings are built side‐by‐side so that their bases are collinear. After construction, the city must be inflated and enclosed within a glass wall. The glass wall can only enclose a rectangular region; hence, the inflated area is rectangular.

Assume that each building has a width of 1 and its area equals its height. Let the chosen heights be \(h_1, h_2, \dots, h_K\) and let \(M = \max\{h_1, h_2, \dots, h_K\}\). The inflation amount is defined as the difference between the area of the enclosing rectangle and the sum of the building areas:

[ \text{Inflation} = K \times M - \sum_{i=1}^{K} h_i. ]

Your task is to choose one design for each building (each building has N candidate heights) in order to minimize the inflation amount. Note that the rectangular envelope’s height is determined by the maximum chosen height and, in order for a candidate value \(M\) to be feasible, at least one building must be built with height equal to \(M\>.

inputFormat

The first line contains two integers K and N, where K is the number of buildings (families) and N is the number of available designs for each building.

Then follow K lines, each containing N space-separated integers representing the available heights for that building.

outputFormat

Output a single integer representing the minimum inflation amount.

sample

3 2
3 5
4 2
3 3

2