C - ボーナスエリア付きダーツ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君はダーツ大会の得点集計を担当しています。

この大会では、青木君が合計 N 回ダーツを投げます。i 回目の投擲（とうてき）では、ダーツが刺さった位置のダーツボードの中心からの距離 D_i が記録されます。

このダーツ大会には特殊な得点ルールがあります。ダーツボード上には M 個の「ボーナスエリア」が設定されています。j 番目のボーナスエリアは、ダーツボードの中心からの距離が L_j 以上 R_j 以下であるリング状の領域です。なお、ボーナスエリア同士が重なっていることもあります。

各投擲の得点は次のように計算されます。

  • ダーツが刺さった位置の中心からの距離 D_i が、M 個のボーナスエリアのうち少なくとも 1 つに含まれる場合（すなわち、L_j \leq D_i \leq R_j を満たす j が 1 つ以上存在する場合）、その投擲の得点は 2 \times D_i です。複数のボーナスエリアに同時に含まれる場合でも、得点は 2 \times D_i のままです。
  • いずれのボーナスエリアにも含まれない場合、その投擲の得点は D_i です。

青木君が N 回投げた結果が与えられるので、高橋君に代わって得点の合計を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • 0 \leq L_j \leq R_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数である。

入力

N M
D_1 D_2 \ldots D_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • 1 行目には、投擲回数を表す整数 N とボーナスエリアの数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各投擲でダーツが刺さった位置のダーツボードの中心からの距離を表す整数 D_1, D_2, \ldots, D_N が、スペース区切りで与えられる。
  • 3 行目から 2+M 行目までの M 行では、各ボーナスエリアの範囲が与えられる。
  • 2 + j 行目 (1 \leq j \leq M) では、j 番目のボーナスエリアの下限 L_j と上限 R_j が整数としてスペース区切りで与えられる。

出力

得点の合計を整数として 1 行で出力せよ。

入力例 1

3 2
5 10 15
3 7
12 20

出力例 1

50

入力例 2

4 1
1 2 3 4
2 3

出力例 2

15

入力例 3

5 3
0 100 50 75 200
0 60
40 80
150 300

出力例 3

750

入力例 4

10 4
1000000000 500000000 0 999999999 250000000 750000000 100 200 300 400
0 100
999999998 1000000000
200 300
500000000 750000000

出力例 4

6750001598

入力例 5

1 1
0
0 0

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi is in charge of scoring at a darts tournament.

In this tournament, Aoki throws darts a total of N times. For the i-th throw, the distance D_i from the center of the dartboard to where the dart lands is recorded.

This darts tournament has a special scoring rule. On the dartboard, M "bonus areas" are defined. The j-th bonus area is a ring-shaped region consisting of all points whose distance from the center of the dartboard is at least L_j and at most R_j. Note that bonus areas may overlap with each other.

The score for each throw is calculated as follows:

  • If the distance D_i from the center to where the dart lands is contained in at least one of the M bonus areas (that is, if there exists at least one j such that L_j \leq D_i \leq R_j), the score for that throw is 2 \times D_i. Even if the dart is contained in multiple bonus areas simultaneously, the score remains 2 \times D_i.
  • If it is not contained in any bonus area, the score for that throw is D_i.

Given the results of Aoki's N throws, calculate the total score on behalf of Takahashi.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • 0 \leq L_j \leq R_j \leq 10^9 (1 \leq j \leq M)
  • All input values are integers.

Input

N M
D_1 D_2 \ldots D_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • The first line contains an integer N representing the number of throws and an integer M representing the number of bonus areas, separated by a space.
  • The second line contains integers D_1, D_2, \ldots, D_N representing the distances from the center of the dartboard to where the dart landed for each throw, separated by spaces.
  • The next M lines (from line 3 to line 2+M) give the range of each bonus area.
  • The (2 + j)-th line (1 \leq j \leq M) contains the lower bound L_j and upper bound R_j of the j-th bonus area as integers separated by a space.

Output

Output the total score as an integer on a single line.

Sample Input 1

3 2
5 10 15
3 7
12 20

Sample Output 1

50

Sample Input 2

4 1
1 2 3 4
2 3

Sample Output 2

15

Sample Input 3

5 3
0 100 50 75 200
0 60
40 80
150 300

Sample Output 3

750

Sample Input 4

10 4
1000000000 500000000 0 999999999 250000000 750000000 100 200 300 400
0 100
999999998 1000000000
200 300
500000000 750000000

Sample Output 4

6750001598

Sample Input 5

1 1
0
0 0

Sample Output 5

0