\(L\) を座標の最大値 \((=2 \times 10^5)\) とします． また，\(g_x\) (\(0 \leq x \leq L\)) を，\(g_x=\sum |B_i-x| - \sum |A_i-x|\) とします． \(A\) を適切に変更することで，すべての \(x\) に対して \(g_x \geq 0\) とできればよいです．

まず，最初に \(A_i=0\) に変更したと仮定します． すると行える操作は，以下のようになります．

• \(A_i\) の値を \(1\) 増やす．この際のコストは，\(org\) を \(A_i\) の入力で与えられた値，\(cur\) を現在の \(A_i\) の値とすると，\(C_i \times (2 \times (cur-org) +1)\)

\(D_{i,x}\) を，\(A_i=x\) のときに \(A_i\) をインクリメントするコストとします．

ある \(A_i\) が \(x \rightarrow x+1\) と変化した際，\(g_0,g_1,\cdots,g_x\) は \(1\) 減少し，\(g_{x+1},\cdots,g_L\) は \(1\) 増加します． ここで，問題を次のように言い換えることができます．

• 以下の操作を繰り返し，\(g\) のすべての要素を \(0\) 以上にせよ． そして，そのコストの総和を最小化せよ．
• 操作：ある \(i\) と \(x\) を選ぶ．同じ \((i,x)\) のペアは一度しか選べない． コスト \(D_{i,x}\) を払う．そして，\(g_0,g_1,\cdots,g_x\) は \(1\) 減少させ，\(g_{x+1},\cdots,g_L\) は \(1\) 増加させる．

本来は，\((i,x)\) を選ぶ前に \((i,x-1)\) を選ぶ必要がある，という条件があります．しかし，コストの値と，\(g_x\) の増減の様子から，その条件を課さなくても答えが変わらないことがわかります．

上記の問題を解きます． まず，全体で操作をする回数は，\(\sum B_i\) 回です． \(f(x)\) を，何らかの \(i\) について \((i,x)\) を選んだ個数，とします． \(g_x\) が全て非負，という条件を \(f(x)\) で書き直すことができます．全体の操作回数が定まっていることに注意すると，この条件は，ある整数列 \(E_x\) を用いて，以下のように言い換えられます．

• すべての \(x\) について，\(\sum_{p=x}^L f(p) \leq E_x\).

これでまず，多項式時間の解法が得られます． 具体的には，整数の多重集合 \(S\) を用意し，\(x\) の降順に以下の操作をすればよいです．

• すべての \(i\) について，\(D_{i,x}\) を \(S\) に追加する．
• \(S\) の要素のうち，小さい方から \(E_x\) を残し，残りを削除する．

この操作を愚直に行っていては間に合いません． そこで，\(S\) を次のようにして管理してみます．

• 整数 \(t\)，整数の配列 \(offset\) を保持する．
• \(t\) 以上の要素は，\(S\) に含まれない．
• \(t\) 未満の値 \(v\) が \(S\) に含まれる個数は，\(offset[v]+getcnt(v,x)\) である． ここで，\(getcnt(v,x)\) は，\(D_{i,p}=v\) を満たす \((i,p)\) (\(x \leq p\)) の個数である．

すると，\(x+1 \rightarrow x\) と変化させる際，以下の操作をすればよいです．

• \(E'_x=E_x-E_{x+1}\) とする．
• \(D_{i,x}<t\) を満たす \(i\) の個数を \(V\) とする．
• \(V>E'_x\) の場合は，\(t\) を \(1\) ずつ減少させて，\(S\) のサイズがちょうど \(E_x\) になる場所を探す．
• \(V<E'_x\) の場合は，\(t\) を \(1\) ずつ増加させて，\(S\) のサイズがちょうど \(E_x\) になる場所を探す．

このアルゴリズムの計算量を評価します． ボトルネックは，\(t\) を増減させるパートです．

まず，\(t\) を \(1\) 増減させるたびにかかる計算量を考えるます．\(K=max(C_i)\) とすると，これは \(O(K)\) でできます． 例えば，\(getcnt\) は一回あたり \(O(K)\) で計算できます． （前計算として，\(C_i\) の値ごとに分類し，累積和を求めておけばよいです） その他の操作もすべて \(O(K)\) で行えます．

最後に，\(t\) が増減する回数が合計で \(O(LK)\) であることを示します．

\(F_x\) を，\(D_{1,x},D_{2,x},\cdots,D_{N,x}\) の中で \(E'_x\) 番目に小さい数，とします． まず，\(E'_x\) について考えると，これは，\(x<B_i\) を満たす \(i\) の個数だとわかります．特に，\(E'_x \leq N\), \(E'_x \leq E_{x-1}\) です． 次に，\(\sum_{x=L}^1 |F_x-F_{x-1}|\) が \(O(LK)\) であることを示します． そもそも \(F_x\) の値が \(O(LK)\) なので，\(F_x\) の減少分の総和を抑えることができればよいです． \(F'_{x-1}\) を，\(D_{1,x-1},D_{2,x-1},\cdots,D_{N,x-1}\) の中で \(E'_x\) 番目に小さい数，とします． そして，\(D_{i,,x}\) の定義に注目すると，\(F_x-K \leq F'_{x-1} \leq F_{x-1}\) が得られます．よって，\(F_x\) の増減の総量が \(O(NL)\) で抑えられました．

最後に，\(dist=|F_x-t|\) とします．\(t\) を \(1\) 増減させるたびに，\(dist\) は \(1\) 減少することがわかります． また，\(F_x\) の増減が \(O(LK)\) なので，\(dist\) が増加する総量も合計で \(O(LK)\) です．よって示されました．

よって，このアルゴリズムの計算量は \(O(N+LK^2)\) になります．