M - series

Contest Duration: 2022-09-03(Sat) 04:00 - 2022-09-03(Sat) 09:00 (local time) (300 minutes) Back to Home

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$

出力

答えを出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

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

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

入力例 2Copy

Copy

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

出力例 2Copy

Copy

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 1Copy

Copy

Sample Output 1Copy

Copy

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 2Copy

Copy

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

Sample Output 2Copy

Copy