AT_past202209_m シリーズ

$ N $ 巻シリーズの漫画があり、 $ i \, (1 \leq i \leq N) $ 巻目は $ A_i $ 円で買うことができます。 また、この漫画はセットで買うこともできます。セットは $ M $ 種類あり、 $ j \, (1 \leq j \leq M) $ 種類目は $ B_j $ 円で、シリーズの $ L_j $ 巻目、 $ L_j + 1 $ 巻目、 $ \dots $ 、 $ R_j $ 巻目を買うことができます。 $ N $ 巻全てを $ 1 $ 冊以上手に入れるためには、最小で何円支払う必要があるか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ \ldots $ $ A_N $ $ B_1 $ $ L_1 $ $ R_1 $ $ \vdots $ $ B_M $ $ L_M $ $ R_M $

答えを出力せよ。

### Sample Explanation 1 次のようにすると $ 14 $ 円で $ N = 5 $ 巻全てを $ 1 $ 冊以上手に入れることができます。これが最小です。 - $ B_1 = 4 $ 円で $ 1 $ 種類目のセットを買う。 $ 1 $ 巻目および $ 2 $ 巻目を手に入れる。 - $ B_2 = 7 $ 円で $ 2 $ 種類目のセットを買う。 $ 2 $ 巻目、 $ 3 $ 巻目、 $ 4 $ 巻目を手に入れる。 - $ A_5 = 3 $ 円で $ 5 $ 巻目を買う。 ### Constraints - $ 1 \leq N, M \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq 10^9 \, (1 \leq i \leq N) $ - $ 1 \leq B_j \leq 10^9 \, (1 \leq j \leq M) $ - $ 1 \leq L_j \leq R_j \leq N \, (1 \leq j \leq M) $ - 入力は全て整数