A - A Walk Along the Cherry Blossom Trees Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は、 N 個の地点が一直線上に並んだ道を散歩しています。地点は左から順に 1, 2, \ldots, N と番号が付けられており、番号が 1 異なる地点同士が隣接しています。

この道沿いには M 本の桜の木が植えられています。 i 番目の桜の木は地点 P_i に植えられており、高橋君がその地点を訪れると V_i 枚の花びらが落ちてきて、高橋君はそのすべてを受け取ります。各地点には桜の木は高々 1 本しか植えられていません。

高橋君は地点 S からスタートし、地点 T まで移動します。高橋君は S から T に向かって隣接する地点へ 1 地点ずつ進み、途中で引き返すことはありません。したがって、高橋君が訪れる地点は、スタート地点とゴール地点を含めて、以下のとおりです。

  • S \leq T のとき： S, S+1, \ldots, T
  • S > T のとき： S, S-1, \ldots, T

S = T の場合、高橋君は移動せず地点 S のみを訪れます。

高橋君は一方向にのみ進むため、各地点を訪れるのはちょうど 1 回です。高橋君が地点 S から地点 T まで移動する間に受け取る花びらの総枚数を求めてください。

制約

  • 1 \leq N \leq 10^9
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq S \leq N
  • 1 \leq T \leq N
  • 1 \leq P_i \leq N (1 \leq i \leq M)
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq M)
  • P_i \neq P_j (i \neq j)
  • 入力はすべて整数である

入力

N M
S T
P_1 V_1
P_2 V_2
\vdots
P_M V_M
  • 1 行目には、地点の数を表す N と、桜の木の本数を表す M が、スペース区切りで与えられる。
  • 2 行目には、スタート地点を表す S と、ゴール地点を表す T が、スペース区切りで与えられる。
  • 3 行目から M + 2 行目では、各桜の木の情報が与えられる。
  • 2 + i 行目には、 i 番目の桜の木が植えられている地点 P_i と、その木から落ちる花びらの枚数 V_i が、スペース区切りで与えられる。

出力

高橋君が地点 S から地点 T まで移動する間に受け取る花びらの総枚数を 1 行で出力せよ。

入力例 1

10 5
3 8
1 10
3 5
5 7
8 2
10 100

出力例 1

14

入力例 2

100 12
40 15
5 12
10 7
15 100
18 30
20 8
25 50
30 3
35 20
40 200
41 9
60 15
90 1

出力例 2

411

入力例 3

1000000000 25
999999920 999999970
1 111
2 222
100000000 333
123456789 444
400000000 555
500000000 666
700000000 777
800000100 888
999999999 999
999999910 4
999999919 70
999999920 100
999999923 1
999999930 500000000
999999934 20
999999940 300
999999945 999999999
999999950 42
999999955 17
999999960 250000000
999999966 6
999999970 8
999999971 90
999999972 3
999999980 5

出力例 3

1750000493

Score : 200 pts

Problem Statement

Takahashi is taking a walk along a road with N points arranged in a straight line. The points are numbered 1, 2, \ldots, N from left to right, and points whose numbers differ by 1 are adjacent to each other.

Along this road, M cherry blossom trees are planted. The i-th cherry blossom tree is planted at point P_i, and when Takahashi visits that point, V_i petals fall down, all of which Takahashi receives. At most one cherry blossom tree is planted at each point.

Takahashi starts at point S and moves to point T. He proceeds one adjacent point at a time from S toward T, without ever turning back. Therefore, the points Takahashi visits, including the start and goal points, are as follows:

  • When S \leq T: S, S+1, \ldots, T
  • When S > T: S, S-1, \ldots, T

If S = T, Takahashi does not move and only visits point S.

Since Takahashi moves in only one direction, he visits each point exactly once. Find the total number of petals Takahashi receives while moving from point S to point T.

Constraints

  • 1 \leq N \leq 10^9
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq S \leq N
  • 1 \leq T \leq N
  • 1 \leq P_i \leq N (1 \leq i \leq M)
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq M)
  • P_i \neq P_j (i \neq j)
  • All input values are integers

Input

N M
S T
P_1 V_1
P_2 V_2
\vdots
P_M V_M
  • The first line contains N, the number of points, and M, the number of cherry blossom trees, separated by a space.
  • The second line contains S, the start point, and T, the goal point, separated by a space.
  • From the 3rd line to the (M + 2)-th line, information about each cherry blossom tree is given.
  • The (2 + i)-th line contains P_i, the point where the i-th cherry blossom tree is planted, and V_i, the number of petals that fall from that tree, separated by a space.

Output

Print in one line the total number of petals Takahashi receives while moving from point S to point T.

Sample Input 1

10 5
3 8
1 10
3 5
5 7
8 2
10 100

Sample Output 1

14

Sample Input 2

100 12
40 15
5 12
10 7
15 100
18 30
20 8
25 50
30 3
35 20
40 200
41 9
60 15
90 1

Sample Output 2

411

Sample Input 3

1000000000 25
999999920 999999970
1 111
2 222
100000000 333
123456789 444
400000000 555
500000000 666
700000000 777
800000100 888
999999999 999
999999910 4
999999919 70
999999920 100
999999923 1
999999930 500000000
999999934 20
999999940 300
999999945 999999999
999999950 42
999999955 17
999999960 250000000
999999966 6
999999970 8
999999971 90
999999972 3
999999980 5

Sample Output 3

1750000493