DCOWS - Dancing Cows


It's the spring dance and, in a rare occurrence, the N (1 ≤ N ≤ 5000) bulls have been invited to dance with the M (N < M ≤ 5000) cows (as long as they stay on their very best behavior).

Farmer John, almost obsessive-compulsive in his organization of dances, wants the spectacle to be as visually attractive as possible. Thus, he wants to pair up the N bulls with cow partners such that the total of all the magnitudes of differences in height is minimized. Bulls have heights B_i (1 ≤ B_i ≤ 1,000,000) and cows have height C_i (1 ≤ C_i ≤ 1,000,000). Of course, some cows will be unmatched since N-M of them will have no partners; ignore their heights.

Input

  • Line 1: Two space-separated integers: N and M.
  • Lines 2..N+1: Line i+1 contains a single integer: B_i.
  • Lines N+2..M+N+1: Line i+N+1 contains a single integer: C_i.

Output

  • Line 1: A single integer that is the minimum of the sum of the absolute value of the height differences that can be achieved.

Sample

Input:
5 7
10
16
12
10
13
7
17
12
10
9
6
11

Input:
4

Explanation

There are five bulls + seven cows with various heights:

  • Bulls: 10 10 12 13 16
  • Cows: 6 7 9 10 11 12 17

Here is one way to achieve a total difference of 4:

  • Bulls: 10 10 12 13 16
  • Cows: 9 10 11 12 17, with 6 7 unmatched.

hide comments
Chandan Mittal: 2013-06-06 23:31:53

@p-setter
repeatedly getting WA at judge 14 :(
my submission id is 9439777,please tell if my O/P are correct for the rest of the cases

also in the best solution's, many have exceeded the time limit(more than 1s)
please see to it asap

Last edit: 2013-06-08 00:22:42
♘Prabhat: 2013-05-31 18:58:46

great problem !!!!!!!

Pushkar Mishra: 2013-05-21 06:38:13

A simple question. But I am getting WA.
Please check the source ID 9309916.
Thank you.

Hasan Jaddouh: 2013-05-17 06:09:57

طيب من وين جبت المسألة؟

Hussain Kara Fallah: 2013-05-16 21:50:26

@Hasan
tests are official testcases !

Hasan Jaddouh: 2013-05-16 21:50:26

من وين جبت المسألة؟ ما عم لاقي المسألة على النت
رفعت التستات صح؟ لأنو عم آخذ WA

Last edit: 2013-05-16 19:12:58

Added by:Se7s
Date:2013-05-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ADA95 ASM32 ASM64 GAWK BASH BF CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP GO ICON ICK LUA NEM NICE NODEJS OCAML PERL6 PIKE PRLG-swi SCALA SCM guile SCM qobi SED ST TCL WHITESPACE
Resource:USACO 2008 Gold