C - Treasure Chest Collection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君はダンジョンの探索をしています。

ダンジョンには一直線の通路があり、数直線上の N 個の異なる位置に宝箱が置かれています。i 番目の宝箱は座標 X_i にあり、C_i 枚のコインが入っています。

高橋君は魔法の杖を持っており、j = 1, 2, \ldots, M の順に合計 M 回この杖を振ります。j 回目に杖を振ると、座標が L_j 以上 R_j 以下の範囲にある宝箱のうち、まだ空になっていないものすべてから、中に入っているコインをすべて回収します。コインを回収された宝箱は空になり、それ以降に杖を振った際にその宝箱が範囲に含まれていても、コインは得られません。

M 回すべて杖を振り終わった後に、高橋君が回収したコインの合計枚数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq X_i \leq 10^9
  • すべての宝箱の座標は互いに異なる（i \neq k ならば X_i \neq X_k）
  • 1 \leq C_i \leq 10^9
  • 1 \leq L_j \leq R_j \leq 10^9
  • 入力はすべて整数
  • 答えは 2^{63} - 1 以下であることが保証される（64ビット符号付き整数に収まる）

入力

N M
X_1 C_1
X_2 C_2
\vdots
X_N C_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • 1 行目には、宝箱の個数 N と杖を振る回数 M が、スペース区切りで与えられる。
  • 続く N 行では、各宝箱の情報が与えられる。
  • このうち i 行目では、i 番目の宝箱の座標 X_i と入っているコインの枚数 C_i が、スペース区切りで与えられる。
  • 続く M 行では、杖を振るたびの範囲が与えられる。
  • このうち j 行目では、j 回目に杖を振るときの範囲の左端 L_j と右端 R_j が、スペース区切りで与えられる。

出力

回収したコインの合計枚数を 1 行で出力してください。

入力例 1

3 2
1 10
3 20
5 30
1 3
2 5

出力例 1

60

入力例 2

5 3
2 100
4 200
7 300
10 400
15 500
1 5
3 10
8 20

出力例 2

1500

入力例 3

8 5
1 10
3 50
5 100
8 200
12 300
20 400
25 500
1000000000 999999999
1 5
1 5
10 15
7 25
999999999 1000000000

出力例 3

1000001559

Score : 366 pts

Problem Statement

Takahashi is exploring a dungeon.

The dungeon has a straight corridor, and there are treasure chests placed at N distinct positions on a number line. The i-th treasure chest is located at coordinate X_i and contains C_i coins.

Takahashi has a magic wand, and he waves it a total of M times, in order j = 1, 2, \ldots, M. When he waves the wand for the j-th time, he collects all the coins from every treasure chest that is located at a coordinate between L_j and R_j (inclusive) and has not yet been emptied. A treasure chest from which coins have been collected becomes empty, and even if that treasure chest falls within the range of a subsequent wand wave, no coins will be obtained from it.

Determine the total number of coins Takahashi has collected after all M waves of the wand.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq X_i \leq 10^9
  • All treasure chest coordinates are distinct (X_i \neq X_k if i \neq k)
  • 1 \leq C_i \leq 10^9
  • 1 \leq L_j \leq R_j \leq 10^9
  • All input values are integers
  • It is guaranteed that the answer is at most 2^{63} - 1 (fits in a 64-bit signed integer)

Input

N M
X_1 C_1
X_2 C_2
\vdots
X_N C_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • The first line contains the number of treasure chests N and the number of wand waves M, separated by a space.
  • The following N lines give the information for each treasure chest.
  • The i-th of these lines contains the coordinate X_i of the i-th treasure chest and the number of coins C_i it contains, separated by a space.
  • The following M lines give the range for each wand wave.
  • The j-th of these lines contains the left endpoint L_j and right endpoint R_j of the range for the j-th wand wave, separated by a space.

Output

Print the total number of collected coins on a single line.

Sample Input 1

3 2
1 10
3 20
5 30
1 3
2 5

Sample Output 1

60

Sample Input 2

5 3
2 100
4 200
7 300
10 400
15 500
1 5
3 10
8 20

Sample Output 2

1500

Sample Input 3

8 5
1 10
3 50
5 100
8 200
12 300
20 400
25 500
1000000000 999999999
1 5
1 5
10 15
7 25
999999999 1000000000

Sample Output 3

1000001559