問題をグラフの最小カットとして定式化します．

まず，グラフの始点 \(S\) と終点 \(T\) を用意します．

各 \(1 \leq i \leq N\) について，長さ \(M\) のパスを用意し，それを \(S=V_{i,0} \to V_{i,1} \to \cdots \to V_{i,M}=T\) とします． 各 \(1 \leq k \leq M\) について \(V_{i,k} \to V_{i,k-1}\) に容量 \(\infty\) の辺を貼ることで，\(V_{i,k}\) は最初のいくつかがカットの \(S\) 側，残りが \(T\) 側，という形になります．

辺 \(V_{i,k-1}\) と \(V_{i,k}\) の間でカットすることと，\(A_{i,k}\) を選ぶことを対応させます． \(V_{i,k-1} \to V_{i,k}\) に容量 \(C_{i,k}\) の辺を貼ることで，\(A_{i,k}\) を選ぶコストを表現することができます．

次に，\(|x_i-x_j| \times W_{i,j}\) のコストに対応する辺を追加します． このコストは，以下のように言い換えることができます．

• 各整数 \(a\) について以下のコストがかかる
  • \(x_i \leq a\) かつ \(a+1 \leq x_j\) なら \(W_{i,j}\) のコスト
  • \(x_j \leq a\) かつ \(a+1 \leq x_i\) なら \(W_{i,j}\) のコスト

「\(x_i \leq a\) かつ \(a+1 \leq x_j\)」という条件は，適切な \(0 \leq p,q \leq M\) を用いて，「\(V_{i,p}\) がカットの \(T\) 側かつ \(V_{j,q}\) がカットの \(S\) 側」と言い換えることができます．よって \(V_{j,q} \to V_{i,p}\) に容量 \(W_{i,j}\) の辺を貼ることでこの条件に対応するコストを表現できます．

同じ \(p,q\) を使う \(a\) をまとめることで，ひとつの組 \((i,j)\) に対し，追加すべき辺は \(O(M)\) 本になります．

これでグラフを作ることができたので，あとはこれの最小カット\(=\)最大流を求めればよいです．

このグラフの頂点数は \(O(NM)\)，辺数は \(O(N^2M)\) なので，Dinic のアルゴリズムを使うことで，\(O(N^4M^3)\) 時間でこの問題は解けます．