宝石を並び替え，\(A_i\) が降順になるようにします． 宝石 \(1,2,\cdots,N\) をこの順に追加し，追加するたびに最適解を計算し直すことにします． ここで以下の主張が成立します．

-☆ 宝石を削る操作をundoしないでも最適解が得られる

☆の証明

フローで定式化して議論を行うとできます． 次のようなグラフを考えます．

• 各 \(1 \leq x \leq N, 0 \leq y \leq K\) に対して頂点 \((x,y)\) が存在
• 各 \(1 \leq x \leq N-1\) に対して，容量 \(\infty\) でコスト \(0\) の辺 \((x,0) \to (x+1,0)\) が存在
• 各 \(1 \leq x \leq N-1, 1 \leq y \leq K\) に対して，容量 \(\infty\) でコスト \(W_y\) の辺 \((x+1,y) \to (x,y)\) が存在
• 各 \(1 \leq x \leq N, 1 \leq y \leq K\) に対して，容量 \(\infty\) でコスト \(0\) の辺 \((x,y) \to (x,y-1)\) が存在

宝石 \(i\) の追加は，頂点 \((B_i,K+1-A_i)\) から頂点 \((N+1-i,0)\) への最短路パスへフローを \(1\) 流すことに対応します． 今，最短路がコスト負の押し戻しを含んでしまったとします． ここで，パスを適切に組み替えることによって，コスト負の押し戻しを用いない最短路パスが得られることを示します．

押し戻しが \((x,y) \to (x+1,y)\) であったとします． 押し戻しが起きているということは，当然もとはここから \(y=0\) へ向かうフローが存在したということです． このフローのパスを適当に \(1\) つとり，\(P\) とおきます． また，今考えている最短路を \(Q\) とおきます． \(P\) と \(Q\) が最初に交わるタイミングに注目します． \(P\) の左上側から \(Q\) が入ってくるのか，あるいは右下側から入ってくるのかで場合分けします．

詳細は省略しますが，場合分け後は以下のように証明できます．

• 左上側: \(P\) と \(Q\) が最後に交わるタイミングに注目する． 最初に交わった点から最後に交わる点まで，\(P\) を通って直接移動する方法で損しないため，\(Q\) をそのようなパスに組み替えるとよい．

• 右下側: \(P\) と \(Q\) が交わったあと，どこかで必ず \((z,w) \to (z,w+1)\) という移動が存在する． このような移動の中で最初のものを考える． これもまた押し戻しなので，もともと何らかのパスの一部であったはず．このパスを \(R\) とおく．\(Q\) と \(R\) が初めて交わったタイミング（これは \((z,w)\) より前であることがわかる）から \((z,w)\) へ \(R\) をたどって直接向かうと，損しないことになる．

なお厳密に証明する際は，マンハッタン距離最小の最短路をとるといった工夫でパスの組み換えがいつか停止することを導く必要があります．

☆証明終了

宝石を一個ずつ足してそのたびに最適解を更新する方法を考えます．

position \(x\) が star であるとは，以下の条件を満たすこととします．

• 大きさが \(x\) 以上の宝石の個数がちょうど \(N+1-x\) 個．

今新たに大きさ \(B_i\) の宝石を追加したとします． \(x \leq B_i\) を満たす任意の star \(x\) について，何らかの宝石が大きさ \(x\) 以上から \(x\) 未満へと変化する必要があります．

宝石を一個追加した際の最適解の変化を考え，大きさの変化した宝石を \(i_1,\cdots,i_t\) とします． 大きさ \(a \to b\) と変化した宝石と \(b \to c\) と変化した宝石がある場合，前者の価値は後者より真に大きい（ような解をとった）としてよいです．

大きさ \(a \to b \to c \to d\) のような変化をする宝石のグループを考えます． 各グループはサイズ \(K\) 以下です． そして，グループの最後の宝石の大きさは，(何かしらの既存のstarの大きさ)\(-1\) であり，それは新しい star になります． さもなくば，宝石の大きさを余計に削っていることになり，最適性に違反するからです．

一度 star になった position は以後ずっと star のままです． 以上より，全操作を通じて宝石のサイズが変化する回数の総和は \(O(NK)\) とわかります．

よってあとは，サイズ変化すべき宝石を効率よく列挙することができれば良いです．

宝石を \(1\) 個追加するときの最適な変化を求める DP を考えます． \(dp[i][j]=\) 「position \(i\) 以上を処理し，もともと大きさ \(i+1\) 以上だった種類 \(j\) の宝石を今大きさ \(i\) まで削っている」ときのコストの最小値，として，\(i=N,\cdots,1\) と処理すればよいです．（今削り中の宝石がないという状態に対応する \(j=-1\) も必要）

これを plus-min 行列で定式化すれば，segtree に乗せることができます．なお，実際には解を復元するために最小値以外のデータも持つ必要がありますが，やることはあまり変わりません．

各ノードが \(O(K^2)\) のデータを持ち，ノードのマージには \(O(K^3)\) かかります． よって計算量は全体で \(O(NK^4 \log N)\) になります．

回答例(C++)