F - 天秤とコイン (Balance and Coins)
Editorial
/ 
/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点: 100 点
この問題は入力ファイルのサイズが大きく，低速な言語で満点を得るのは難しいので注意せよ．
問題
天秤の左側の皿に N 枚のコインが縦に積まれており，上から順にコイン 1, コイン 2 , \cdots, コイン N と呼ぶことにする．これらのコインは酸化などによって毎日質量が変化する．i 日目のコイン j の質量は M_{i,j} である．
あなたは D 日間にわたって毎日以下の遊びをする．
- 天秤の左側の皿に積まれているコインを上から好きな枚数だけ右側の皿に移動する．1 枚も移動させなくても構わない．
- 天秤を釣り合わせるのに必要な分銅の質量を G とする．G は左右の皿に積まれているコインの合計質量の差の絶対値である．
- あなたはコスト G を払う．
D 日間にわたって払う必要のある合計コストの最小値を求めるプログラムを作成せよ．
制約
- 1 \leq N \leq 2\,000．
- 1 \leq D \leq 2\,000．
- 1 \leq M_{i,j} \leq 1\,000\,000\,000 (1 \leq i \leq D, 1 \leq j \leq N)．
小課題
- (8 点) N = 2．
- (8 点) N = 3．
- (14 点) N \leq 10，D \leq 10．
- (24 点) N \leq 200，D \leq 200．
- (46 点) 追加の制約はない．
入力
入力は以下の形式で標準入力から与えられる．
N D
M_{1,1} M_{1,2} ... M_{1,N}
M_{2,1} M_{2,2} ... M_{2,N}
\vdots
M_{D,1} M_{D,2} ... M_{D,N}
出力
標準出力に，D 日間にわたって払う必要のある合計コストの最小値を 1 行で出力せよ．
入力例 1
3 4 10 8 3 5 7 8 9 6 1 2 8 9
出力例 1
14
以下のように操作を行うと，払う合計コストは 14 となり，このときが最小である． また，この入力例は小課題 2, 3, 4, 5 の制約を満たす．
- 1 日目にはコインを 1 枚移動する．払うコストは |10 - (8+3)| = 1 である．
- 2 日目にはコインを 1 枚も移動しない．払うコストは |5 - (7+8)| = 10 である．
- 3 日目にはコインを 1 枚も移動しない．払うコストは |9 - (6+1)| = 2 である．
- 4 日目にはコインを 1 枚移動する．払うコストは |(2+8) - 9| = 1 である．
入力例 2
10 8 50 8 226 426 123 30 114 304 230 994 402 230 316 555 193 95 547 66 171 1000 399 30 24 177 97 325 315 1 361 993 606 973 94 32 391 116 64 782 784 631 759 1000 130 503 81 538 260 41 71 118 1000 148 223 149 113 1 110 366 56 113 1000 245 104 383 171 27 244 34 204 121 55 1000 32 151 59 44 270 386 36 104
出力例 2
6733
この入力例は小課題 3, 4, 5 の制約を満たす．
入力例 3
1 10 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
10000000000
この入力例は小課題 3, 4, 5 の制約を満たす． 出力が 32 ビット整数型に収まらない場合があることに注意せよ．