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 obsessivecompulsive 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 NM of them will have no partners; ignore their heights.
INPUT FORMAT:
* Line 1: Two spaceseparated 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 FORMAT:
* 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
SAMPLE OUTPUT :
4
INPUT DETAILS:
Five bulls + seven cows with various heights: Bulls: 10 10 12 13 16 Cows: 6 7 9 10 11 12 17
OUTPUT DETAILS :
Here is one way to achieve a total difference of 4: Bulls: 10 10 12 13 16 Cows: 6 7 9 10 11 12 17
hide comments
excel_blaze:
20180617 22:02:19
pretty simple.Just a lot of WA due to limiting value. try something in the order of 10^12


sahil_1994:
20170921 14:38:10
Do you have to consider the case N>M ?


kshubham02:
20170830 09:10:20
@awesome_me the possible answer can be as large as 5000*10^6, so make sure your limiting variable is at least that big. 

shubham8_:
20170623 12:03:23
Those getting wa also check for the case when n = m :) 

j_nash:
20170602 21:29:58
make sure you are taking min variable long enough to handle all values in dp array(hint for those who are getting WA on test case 15)


Sigma Kappa:
20170528 22:39:42
Somehow my assert (m > n) failed, but never mind, got Accepted with O(n^2). Does not look like Gold problem at all, hmm... 

deepak_bulani1:
20170327 08:55:05
take dp array as long long int!! 

samyak3:
20161208 17:15:51
@theph0enix : Greedy approach will not work when a bull has two choices of pairing with same height difference on different sides. i.e a Bull of height H has a choice to pair with two cows of height Hd and H+d . You will never know which choice will give you optimal solution. 

theph0enix:
20160719 10:18:25
Why doesn't the greedy approach work here? 

awesome_me:
20160714 14:27:38
getting wrong ans after or on case 15. Tried using long and scanf and without scanf as well. Simple O(m*n) approach. Somebody please help. 
Added by:  Se7s 
Date:  20130515 
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 clisp LISP sbcl D ERL FSHARP GO ICON ICK LUA NEM NICE NODEJS OCAML PERL6 PIKE PRLGswi SCALA SCM guile SCM qobi SED ST TCL WHITESPACE 
Resource:  USACO 2008 Gold 