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 ≤ iN, 1 ≤ jK, -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