ドアが存在する行を小さい順に \(A'_1, \cdots, A'_{|A'|}\) とし，\(A'_i\) 行目でドアがある列番号を小さい順に \(B'_{i,\ 1} \cdots, B'_{i,\ |B'_i|}\) とおきます．

以下の \(2\) つの場合における答えのうち小さいほうが答えです．

\(W\) 列目のエレベーターを使用しない場合

各行における，\(1\) 列目から最も遠いドアまでの距離の \(2\) 倍 (往復分) の総和が最小コストとなります．

すなわち，\(\displaystyle \sum_{i=1}^{|A'|} 2 (B'_{i,\ |B'|} - 1)\) が答えです．

\(W\) 列目のエレベーターを使用する場合

行 \(A_i\) における動きは以下の \(3\) 通りとしてよいです．

• \(1\) 列目から \(W\) 列目まで移動する
• \(W\) 列目から \(1\) 列目まで移動する
• \(1\) 列目から列 \(B'_{i,\ j+0}\) まで行って \(1\) 列目に帰ってくる．また，\(W\) 列目から列 \(B'_{i,\ j+1}\) まで行って \(W\) 列目に帰ってくる (\(0 \leq j \leq |B'_i|\))

\(3\) 番目の動きにおいて，\(B'_{i,\ 0} = 1\)，\(B'_{i,\ |B'_1|+1} = W\) を番兵としておくものとします．

「\(1\) 列目から \(W\) 列目まで移動する．また，\(W\) 列目から \(1\) 列目まで移動する」という動きも可能ですが，これを禁止しても最適解は悪化しません．

\(1,2\) 番目の動きのコストはともに \(W-1\) であり，\(3\) 番目の動きのコストの最小値は \(\displaystyle \min_{j} \left( 2 (W-1) - 2 (B'_{i,\ j+1} - B'_{i,\ j+0}) \right)\) です．

全体における動きの制約として，\(1\) 番目と \(2\) 番目の動きを \(1\) 回以上の等しい回数おこなう必要があり，逆にこれを満たせば動き方が構築できます．\(1,2\) 番目の動きのコストは等しいので，動きの制約は以下のように言い換えられます．

• \(|A'|\) 個の整数があり，\(i\) 個目は \(a_i\) である．これらのうち正の偶数個を \(W-1\) に置き換えるとき，総和の最小値は何になるか？

ここで，\(a_i\) は \(3\) 番目の動きの最小コスト \(a_i := \displaystyle \min_{j} \left( 2 (W-1) - 2 (B'_{i,\ j+1} - B'_{i,\ j+0}) \right)\) です．

言い換え後の問題は，ソートとループによって ABC-C 程度の難易度で解けます．この問題の答えがそのまま元の答えになります．

原案：sheyasutaka