AT_otemae2019_f 天秤とコイン (Balance and Coins)

[problemUrl]: https://atcoder.jp/contests/otemae2019/tasks/otemae2019_f 天秤の左側の皿に $ N $ 枚のコインが縦に積まれており，上から順にコイン $ 1 $, コイン $ 2 $ , $ \cdots $, コイン $ N $ と呼ぶことにする．これらのコインは酸化などによって毎日質量が変化する．$ i $ 日目のコイン $ j $ の質量は $ M_{i,j} $ である． あなたは $ D $ 日間にわたって毎日以下の遊びをする． - 天秤の左側の皿に積まれているコインを上から好きな枚数だけ右側の皿に移動する．$ 1 $ 枚も移動させなくても構わない． - 天秤を釣り合わせるのに必要な分銅の質量を $ G $ とする．$ G $ は左右の皿に積まれているコインの合計質量の差の絶対値である． - あなたはコスト $ G $ を払う． $ D $ 日間にわたって払う必要のある合計コストの最小値を求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる． > $ 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\ \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) $． ### 小課題 1. ($ 8 $ 点) $ N\ =\ 2 $． 2. ($ 8 $ 点) $ N\ =\ 3 $． 3. ($ 14 $ 点) $ N\ \leq\ 10 $，$ D\ \leq\ 10 $． 4. ($ 24 $ 点) $ N\ \leq\ 200 $，$ D\ \leq\ 200 $． 5. ($ 46 $ 点) 追加の制約はない． ### Sample Explanation 1 以下のように操作を行うと，払う合計コストは $ 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 $ である． ### Sample Explanation 2 この入力例は小課題 $ 3,\ 4,\ 5 $ の制約を満たす． ### Sample Explanation 3 この入力例は小課題 $ 3,\ 4,\ 5 $ の制約を満たす． 出力が $ 32 $ ビット整数型に収まらない場合があることに注意せよ．