AT_abc127_d [ABC127D] Integer Cards

[problemUrl]: https://atcoder.jp/contests/abc127/tasks/abc127_d $ N $ 枚のカードがあり、$ i $ 番目のカードには整数 $ A_i $ が書かれています。 あなたは、$ j\ =\ 1,\ 2,\ ...,\ M $ について順に以下の操作を $ 1 $ 回ずつ行います。 操作: カードを $ B_j $ 枚まで選ぶ($ 0 $ 枚でもよい)。選んだカードに書かれている整数をそれぞれ $ C_j $ に書き換える。 $ M $ 回の操作終了後に $ N $ 枚のカードに書かれた整数の合計の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $ $ B_1 $ $ C_1 $ $ B_2 $ $ C_2 $ $ \vdots $ $ B_M $ $ C_M $

$ M $ 回の操作終了後に $ N $ 枚のカードに書かれた整数の合計の最大値を出力せよ。

### 制約 - 入力は全て整数である。 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ M\ \leq\ 10^5 $ - $ 1\ \leq\ A_i,\ C_i\ \leq\ 10^9 $ - $ 1\ \leq\ B_i\ \leq\ N $ ### Sample Explanation 1 $ 2 $ 番目のカードに書かれた整数を $ 5 $ に書き換えることで、$ 3 $ 枚のカードに書かれた整数の合計が $ 5\ +\ 5\ +\ 4\ =\ 14 $ となり、このときが最大です。 ### Sample Explanation 4 出力が $ 32 $ bit 整数型に収まらない場合があります。