貪欲に解く方針です．

問題は以下のように言い換えられます．

• \(2K\) 個の相異なる整数 \(a_1,a_2,\ldots,a_l,b_1,b_2,b_m,c_1,c_2,\ldots,c_n\) を選ぶときの \((X_{a_1}+\ldots+X_{a_l})+(Y_{b_1}+\ldots+Y_{b_m})+(Z_{c_1}+\ldots+Z_{c_n})\) の最大値
  • ただし \(l,m,n\) は 偶数 である必要がある

一旦 \(l,m,n\) が偶数であるという条件を無視した場合を考えます．\(a_j=i\) となる \(j\) が存在するとき，\(i\) は「\(X\) として選ばれている」とします．

\(\max(X_i,Y_i,Z_i)\) が大きい \(2K\) 個の \(i\) のうち，\(\max(X_i,Y_i,Z_i)=X_i\) となる \(i\) を \(X\) として選ばれている状態にし，その個数を \(\mathrm{cnt}_X\) とします． 同様に，\(\max(X_i,Y_i,Z_i)=Y_i\) (かつ \(Y_i>X_i\)) となる \(i\) を \(Y\) として選ばれている状態にし，その個数を \(\mathrm{cnt}_Y\) にします．それ以外の \(i\) を \(Z\) として選ばれている状態にし，その個数を \(\mathrm{cnt}_Z\) とします．\(\mathrm{cnt}_X+\mathrm{cnt}_Y+\mathrm{cnt}_Z=2K\) です．

もし \(\mathrm{cnt}_X,\mathrm{cnt}_Y,\mathrm{cnt}_Z\) がすべて偶数の場合は，「\(l,m,n\) が偶数」という条件を満たしているので，\(\max(X_i,Y_i,Z_i)\) の大きい方から \(2K\) 個の総和が本問題の答えです．そうでない場合，\(\mathrm{cnt}_X,\mathrm{cnt}_Y,\mathrm{cnt}_Z\) のうちいずれか \(2\) つは奇数で，残りの \(1\) つは偶数になります．以下では \(\mathrm{cnt}_X,\mathrm{cnt}_Y\) が奇数の場合を考えます．

このとき，以下の \(6\) 種類を試せば十分です．

1. \(X\to Y\)
2. \(Y\to X\)
3. \(X\to Z,Z\to Y\)
4. \(Y\to Z,Z\to X\)
5. \(X\to Z,Y\to Z\)
6. \(Z\to X, Z\to Y\)

ここで，\(X\to Y\) は「\(X\) として選ばれているものを \(1\) つ減らし，新たに \(Y\) として選ばれるものを \(1\) つ増やす」ことを意味します．

これが十分である理由は，\(X-Y,Y-Z,Z-X\) 間の移動は高々 \(1\) 回ずつしか起きないからです．

これら \(6\) 種類の場合分けをそれぞれ計算しても良いですが，複雑なためミスしやすいかと思います．そこで dp によってこれらの場合分けをまとめて計算する方針を紹介します．

\(dp[i][dx][dy][dz]\) を「\(l,m,n\) が偶数という条件を無視して選んだ状態から，\(1,2,\ldots,i\) の中で \(X,Y,Z\) として選ばれているものを それぞれ \(dx,dy,dz\) 個変動させたときの，答えの差分の最大値」とします．上の場合分けで十分なことから \(-2\leq dx,dy,dz\leq 2\) の範囲を調べれば十分です．

例えば \(i\) が \(X\) として選ばれている場合の遷移は次のようになります（\(\leftarrow\) は chmax を意味します）．

• \(dp[i][dx][dy][dz]\leftarrow dp[i-1][dx][dy][dz]\) （\(X\) として選ばれている状態を変更しない）
• \(dp[i][dx-1][dy][dz]\leftarrow dp[i-1][dx][dy][dz]-X[i]\) （\(X\) として選ばれている状態をやめる）
• \(dp[i][dx-1][dy+1][dz]\leftarrow dp[i-1][dx][dy][dz]-X[i]+Y[i]\) （\(X\) として選ばれている状態から \(Y\) として選ばれている状態に変更する）
• \(dp[i][dx-1][dy][dz+1]\leftarrow dp[i-1][dx][dy][dz]-X[i]+Z[i]\) （\(X\) として選ばれている状態から \(Z\) として選ばれている状態に変更する）

これらが計算し終わった後，\(dx+dy+dz=0,(\mathrm{cnt}_X+dx)\equiv 0\pmod 2, (\mathrm{cnt}_Y+dy)\equiv 0\pmod 2,(\mathrm{cnt}_Z+dz)\equiv 0\pmod 2\) を満たす \(dx,dy,dz\) の中で \(dp[N][dx][dy][dz]\) が最大のものが，答えの差分の最大値となります．

この dp は \(\mathrm{cnt}_X,\mathrm{cnt}_Y,\mathrm{cnt}_Z\) の偶奇によらず行うことができます．

実装例