AT_past202209_m シリーズ

There is a series of manga consisting of $ N $ books. The $ i $ -th ( $ 1 \leq i \leq N $ ) book is sold for $ A_i $ yen. These books are also sold in sets. There are $ M $ sets, the $ j $ -th ( $ 1 \leq j \leq M $ ) of which is sold for $ B_j $ yen and contains the $ L_j $ -th, $ (L_j + 1) $ -th, $ \ldots $ , $ R_j $ -th books of the series. At least how many yen does one have to pay to get at least one of each of the $ N $ books?

Input is given from Standard Input in the following format: > $ N $ $ M $ $ A_1 $ $ \ldots $ $ A_N $ $ B_1 $ $ L_1 $ $ R_1 $ $ \vdots $ $ B_M $ $ L_M $ $ R_M $

Print the answer as an integer.

### Sample Explanation 1 One can get at least one of each of the $ N = 5 $ books for $ 14 $ yen as follows. This is the minimum one has to pay. - Buy the $ 1 $ -st set for $ B_1 = 4 $ yen to get the $ 1 $ -st and $ 2 $ -nd books. - Buy the $ 2 $ -nd set for $ B_2 = 7 $ yen to get the $ 2 $ -nd, $ 3 $ -rd, and $ 4 $ -th books. - Buy the $ 5 $ -th book for $ A_5 = 3 $ yen. ### 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) $ - All values in input are integers.