AT_abc363_g [ABC363G] Dynamic Scheduling

[problemUrl]: https://atcoder.jp/contests/abc363/tasks/abc363_g 長さ $ N $ の数列 $ D=(D_1,\ D_2,\ \dots,\ D_N),\ P=(P_1,\ P_2,\ \dots,\ P_N) $ が与えられます。 $ Q $ 個のクエリを与えられる順に処理してください。クエリは以下の形式で与えられます。 - `c x y` : $ D_c $ を $ x $ に、$ P_c $ を $ y $ に変更する。そして、次の問題を解いて答えを出力する。 > $ 1 $ から $ N $ までの番号がついた $ N $ 個の仕事があります。 > あなたは今日 (これを $ 1 $ 日目とする) から $ 1 $ 日あたり $ 1 $ 個の仕事を選んで終わらせることを $ N $ 日間行います。 > 仕事 $ i $ は $ D_i $ 日目までに終わらせると $ P_i $ の報酬を貰えます。($ D_i $ 日目までに終わらせなかった場合は何も無い) > 仕事をやる順番を上手く選んだ時の報酬の総和の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。ここで $ \mathrm{query}_i $ は $ i $ 番目のクエリを意味する。 > $ N $ $ Q $ $ D_1 $ $ D_2 $ $ \dots $ $ D_N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の形式で与えられる。 > $ c $ $ x $ $ y $

$ Q $ 行出力せよ。$ i $ 行目には $ i $ 番目のクエリの答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ 1\ \leq\ D_i\ \leq\ N $ - $ 1\ \leq\ P_i\ \leq\ 10^9 $ - $ 1\ \leq\ c\ \leq\ N $ - $ 1\ \leq\ x\ \leq\ N $ - $ 1\ \leq\ y\ \leq\ 10^9 $ - 入力される値は全て整数 ### Sample Explanation 1 $ 1 $ 番目のクエリは次のようになります。 - $ D_3 $ を $ 1 $ に、$ P_3 $ を $ 4 $ に更新する。$ D\ =\ (1,\ 2,\ 1),\ P\ =\ (3,\ 6,\ 4) $ になる。 - 小問題では、$ 1 $ 日目に仕事 $ 3 $ を、$ 2 $ 日目に仕事 $ 2 $ を、$ 3 $ 日目に仕事 $ 1 $ を行うという手順が最適な手順の $ 1 $ つで、この時の報酬の総和は $ 10 $ であるから、これを出力する。 $ 2 $ 番目のクエリは次のようになります。 - $ D_2 $ を $ 3 $ に、$ P_2 $ を $ 9 $ に更新する。$ D\ =\ (1,\ 3,\ 1),\ P\ =\ (3,\ 9,\ 4) $ になる。 - 小問題では、$ 1 $ 日目に仕事 $ 3 $ を、$ 2 $ 日目に仕事 $ 1 $ を、$ 3 $ 日目に仕事 $ 2 $ を行うという手順が最適な手順の $ 1 $ つで、この時の報酬の総和は $ 13 $ であるから、これを出力する。