M - series Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

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 冊以上手に入れるためには、最小で何円支払う必要があるか求めてください。

制約

  • 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)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 \ldots A_N
B_1 L_1 R_1
\vdots
B_M L_M R_M

出力

答えを出力せよ。

入力例 1

5 3
5 4 6 2 3
4 1 2
7 2 4
14 2 5

出力例 1

14

次のようにすると 14 円で N = 5 巻全てを 1 冊以上手に入れることができます。これが最小です。

  • B_1 = 4 円で 1 種類目のセットを買う。1 巻目および 2 巻目を手に入れる。
  • B_2 = 7 円で 2 種類目のセットを買う。2 巻目、3 巻目、4 巻目を手に入れる。
  • A_5 = 3 円で 5 巻目を買う。

入力例 2

6 3
3 1 4 1 5 9
3 1 2
12 4 6
10 3 4

出力例 2

19

Score : 6 points

Problem Statement

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?

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.

Input

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

Output

Print the answer as an integer.

Sample Input 1

5 3
5 4 6 2 3
4 1 2
7 2 4
14 2 5

Sample Output 1

14

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.

Sample Input 2

6 3
3 1 4 1 5 9
3 1 2
12 4 6
10 3 4

Sample Output 2

19