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?
Input
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 ≤
N, 1 ≤
j ≤
K, -2000 ≤
ai,j ≤ 2000).
Output
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
4 2
-2 3
-5 -3
3 6
-10 7
Sample Output 1
-24
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.
x = (-5) - 3 + (-10) - 6 = -24