Barr the bear is bored. He grabs the nearest piece of paper and scribbles an equation:
a1 - a2 + a3 - a4 + ... + aN-1 - aN = x.
Naturally, N has to be even for the equation to hold. Then he takes his trusty random number generator and starts generating random integers. He records the first K such integers on a card, the next K integers on another card, and so on, until he has recorded K*N integers on N cards.
He decides to align the cards nicely with the variables, each card to 1 variable. Then he picks a number from each card to be the value of the respective variable in the equation. He wonders, how can he do this such that the value x is minimised?
He does not wonder for long. After 10 seconds, he realises, "This is trivial." Can you figure out his trivial solution?
The first line contains integers N
(2 ≤ N
≤ 75,000, N
is even) and K
(1 ≤ K
≤ 100). The following N
lines contains K
space-separated integers each; the jth
integer of the ith
of these lines is an integer ai,j
that represents the jth
integer on the ith
card (1 ≤ i
, 1 ≤ j
, -2000 ≤ ai,j
The first line should contain a single integer: the minimum possible x
assuming that you align the cards and choose the numbers optimally.
Sample Input 1
Sample Output 1
Explanation for Sample Output 1
A possible optimal solution is to align the the 2nd card with a1
, the 1st card with a2
, the 4th card with a3
and the 3rd card with a4
. Then pick integers -5, 3, -10, 6 respectively.
= (-5) - 3 + (-10) - 6 = -24