C - Farm Harvest Festival Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は広大な農園を経営しています。

農園には N 個の区画が一列に並んでおり、各区画には 1 から N までの番号が付けられています。区画 i (1 \leq i \leq N) には果物の木が植えられており、そこから収穫できる果物の量は A_i キログラムです。

収穫祭の期間中、高橋君は M 回の収穫作業を行います。j 回目 (1 \leq j \leq M) の収穫作業では、区画 L_j から区画 R_j までの連続する全ての区画を対象に果物を収穫します。

各区画の果物は一度収穫するとなくなります。そのため、ある区画が複数回の収穫作業の対象に含まれていたとしても、その区画から得られる収穫量は最初の1回分、すなわち A_i キログラムのみです。

言い換えると、M 回の収穫作業のうち少なくとも1回は対象となった区画全ての A_i の合計が、高橋君の得る総収穫量となります。この総収穫量を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
  • 入力はすべて整数

入力

N M
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • 1 行目には、区画の数 N と収穫作業の回数 M が空白区切りで与えられる。
  • 2 行目には、各区画から収穫できる果物の量 A_1, A_2, \ldots, A_N が空白区切りで与えられる。
  • 続く M 行のうち j 行目 (1 \leq j \leq M) には、j 回目の収穫作業の対象となる区画の範囲の左端 L_j と右端 R_j が空白区切りで与えられる。

出力

高橋君が得る果物の総収穫量を 1 行で出力せよ。

入力例 1

5 3
10 20 30 40 50
1 3
2 4
4 5

出力例 1

150

入力例 2

7 4
5 12 8 3 15 9 6
1 2
4 6
2 5
1 7

出力例 2

58

入力例 3

10 6
100 250 180 90 320 150 200 80 170 260
1 3
5 7
2 4
6 9
1 1
8 10

出力例 3

1800

Score : 366 pts

Problem Statement

Takahashi manages a vast farm.

The farm has N plots arranged in a row, numbered from 1 to N. Plot i (1 \leq i \leq N) has a fruit tree planted in it, and the amount of fruit that can be harvested from it is A_i kilograms.

During the harvest festival, Takahashi performs M harvesting operations. In the j-th (1 \leq j \leq M) harvesting operation, he harvests fruit from all consecutive plots from plot L_j to plot R_j.

The fruit in each plot is gone once harvested. Therefore, even if a plot is included in multiple harvesting operations, the yield obtained from that plot is only from the first time, namely A_i kilograms.

In other words, the total harvest Takahashi obtains is the sum of A_i over all plots that were targeted by at least one of the M harvesting operations. Find this total harvest.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
  • All inputs are integers

Input

N M
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • The first line contains the number of plots N and the number of harvesting operations M, separated by a space.
  • The second line contains the amounts of fruit harvestable from each plot A_1, A_2, \ldots, A_N, separated by spaces.
  • In the following M lines, the j-th line (1 \leq j \leq M) contains the left endpoint L_j and right endpoint R_j of the range of plots targeted by the j-th harvesting operation, separated by a space.

Output

Output the total harvest of fruit that Takahashi obtains, in a single line.

Sample Input 1

5 3
10 20 30 40 50
1 3
2 4
4 5

Sample Output 1

150

Sample Input 2

7 4
5 12 8 3 15 9 6
1 2
4 6
2 5
1 7

Sample Output 2

58

Sample Input 3

10 6
100 250 180 90 320 150 200 80 170 260
1 3
5 7
2 4
6 9
1 1
8 10

Sample Output 3

1800