\(A_i = p, B_i = q\) である要素を \((p, q)\) 型と呼ぶことにします。 このとき、\(N\) 個の要素は \((0, 0)\) 型、\((0, 1)\) 型、\((1, 0)\) 型、\((1, 1)\) 型に分類されます。

もしある一つの要素が、\(0 \rightarrow 1\) と変化しその後 \(1 \rightarrow 0\) と変化したとすると、それら \(2\) 回の操作を行わないようにすることで合計費用をより小さくすることができます。 よって、最適な操作手順における各要素の値の変化は、その型に応じて下記の通りに限られます。

• \((0, 0)\) 型 : \(0\) から変化しない。
• \((0, 1)\) 型 : \(0 \rightarrow 1\) とちょうど \(1\) 回変化する。
• \((1, 0)\) 型 : \(1 \rightarrow 0\) とちょうど \(1\) 回変化する。
• \((1, 1)\) 型 : 下記の (A) または (B) のどちらかである。
  • (A) \(1\) から変化しない。
  • (B) \(1 \rightarrow 0\) 、\(0 \rightarrow1\) とそれぞれちょうど \(1\) 回ずつ変化する。

\((1, 1)\) 型の各要素について (A) と (B) のどちらであるかが一度固定されれば、その場合の最適な操作手順は下記の \((\star)\) に一意に定まります。

\((\star)\) \(1 \rightarrow 0\) の操作を \(C\) の値が大きい要素に対するものから順に行い、 その後、\(0 \rightarrow 1\) の操作を \(C\) の値が小さい要素に対するものから順に行う。

実際、上記に反する操作手順については、適切に選んだ \(2\) 個の操作の順序を交換することで、合計費用をより小さくすることができます。

また、\((1, 1)\) 型の要素の個数を \(m\) とおくとき、各要素の (A) と (B) の選択は下記を満たすもののみを考えれば十分です。

ある整数 \(0 \leq h \leq m\) が存在して、\((1, 1)\) 型の要素のうち \(C\) の値が小さいものから \(h\) 個は (A) を選択し、それ以外は (B) を選択する。

実際、もし \((1, 1)\) 型のある \(2\) 要素 \(A_i, A_j\) が、\(C_i \lt C_j\) であるにもかかわらず、\(A_i\) は (B) を選択し、\(A_j\) は (A) を選択していた場合、\(A_i\) と \(A_j\) の役割を交換することで、合計費用をより小さくすることができます。

よって本問題の答えを求めるには、上記の \(h\) として、\(h = 0, 1, 2, \ldots, m\) のすべての場合で \((\star)\) を試し、その合計費用の最小値を求めれば良いです。

具体的には、\((1, 1)\) 型の各要素の (A) と (B) の選択を固定したとき（特に \(h\) を固定したとき）の \((\star)\) にかかる合計費用は、

\[ \sum_{l = 1}^X (l-1)C_{i_l} + \sum_{l = 1}^Y lC_{j_l} + (X+Y)\sum_{l=1}^Z C_{k_l} \]

で与えられます。 ただし上式では、\(1\to 0\) の操作を行う回数が \(X\) で対象要素の \(C\) が降順に \(C_{i_1} \geq C_{i_2} \geq \cdots \geq C_{i_X}\) 、 \(0 \to 1\) の操作を行う回数が \(Y\) で対象要素の \(C\) が降順に \(C_{j_1} \geq C_{j_2} \geq \cdots \geq C_{j_Y}\) 、 (A) を選択する \((1,1)\) 型の要素が \(Z\) 個でそれらの \(C\) が \(C_{k_1}, C_{k_2}, \ldots, C_{k_Z}\) であるとします。

全ての \(h = 0, 1, 2, \ldots, m\) について独立に上式の計算を行うと計算時間が過大になりますが、\(h = 0\) からはじめ、\(h\) を \(1\) 増加させるたびに、それによる費用の差分のみを更新する（そのために必要な累積和等を適切に前計算しておく）ことで、実行制限時間に間に合わせることができます。