oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

equation Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

equation.html

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

Tags

Sorting

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100153s32MBAverage
2013s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o equation -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.