A - Collecting Coins on the Walking Path Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は N 個の地点が一列に並ぶ散歩道を歩いています。地点には左から順に 1, 2, \ldots, N の番号が付いており、番号が小さい方を左、大きい方を右と呼びます。

この散歩道には M 枚のコインが落ちており、それぞれのコインは特定の地点に置かれています。 i 枚目のコインは地点 P_i に置かれており、その価値は V_i です。同じ地点に複数のコインが置かれていることもあります。

高橋君は地点 S から出発し、地点 T まで移動します。移動の仕方は次の通りです。

  • S < T のとき：地点 S, S+1, S+2, \ldots, T の順に右方向（番号が増える方向）へ 1 地点ずつ進み、各地点をちょうど 1 回ずつ訪れます。
  • S > T のとき：地点 S, S-1, S-2, \ldots, T の順に左方向（番号が減る方向）へ 1 地点ずつ進み、各地点をちょうど 1 回ずつ訪れます。
  • S = T のとき：移動せず、地点 S にとどまります。

いずれの場合も、出発地点 S と到着地点 T は訪れた地点に含まれます。

高橋君がある地点を訪れたとき、その地点に置かれているコインをすべて拾います。

高橋君が地点 S から地点 T まで移動したとき、拾ったコインの価値の合計を求めてください。コインを 1 枚も拾わなかった場合、合計は 0 です。

制約

  • 1 \leq N \leq 10^9
  • 0 \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^4 (1 \leq i \leq M)
  • 入力はすべて整数である。

入力

N M S T
P_1 V_1
P_2 V_2
\vdots
P_M V_M
  • 1 行目には、地点の数を表す N 、コインの枚数を表す M 、出発地点を表す S 、到着地点を表す T が、スペース区切りで与えられる。
  • 続く M 行では、各コインの情報が与えられる。 M = 0 の場合、この部分は存在しない。
  • 1 + i 行目 (1 \leq i \leq M) では、 i 枚目のコインが置かれている地点の番号 P_i と、そのコインの価値 V_i が、スペース区切りで与えられる。

出力

高橋君が拾ったコインの価値の合計を 1 行で出力してください。

入力例 1

10 5 3 7
1 100
3 10
5 20
5 30
7 40

出力例 1

100

入力例 2

8 4 6 2
2 5
4 10
6 20
8 100

出力例 2

35

入力例 3

100 12 20 75
5 100
20 1
25 2
30 3
40 4
40 5
60 6
75 7
76 1000
90 9
55 10
10 11

出力例 3

38

入力例 4

1000000000 30 800000000 200000000
1 9999
1000000000 8888
800000000 10000
200000000 1
500000000 1234
750000000 4321
250000000 2222
199999999 7777
800000001 6666
600000000 3456
600000000 6544
300000000 1111
400000000 2222
700000000 3333
900000000 4444
100000000 5555
650000000 1010
550000000 2020
450000000 3030
350000000 4040
210000000 5050
790000000 6060
205000000 7070
795000000 8080
123456789 9090
987654321 123
333333333 321
666666666 654
777777777 987
222222222 789

出力例 4

73555

入力例 5

1 0 1 1

出力例 5

0

Score : 233 pts

Problem Statement

Takahashi is walking along a path with N points arranged in a line. The points are numbered 1, 2, \ldots, N from left to right, where smaller numbers are on the left and larger numbers are on the right.

There are M coins scattered along this path, each placed at a specific point. The i-th coin is placed at point P_i and has a value of V_i. Multiple coins may be placed at the same point.

Takahashi starts at point S and moves to point T. The movement rules are as follows:

  • When S < T: He moves one point at a time to the right (in the direction of increasing numbers) in the order S, S+1, S+2, \ldots, T, visiting each point exactly once.
  • When S > T: He moves one point at a time to the left (in the direction of decreasing numbers) in the order S, S-1, S-2, \ldots, T, visiting each point exactly once.
  • When S = T: He does not move and stays at point S.

In all cases, both the starting point S and the destination point T are included in the visited points.

When Takahashi visits a point, he picks up all coins placed at that point.

Find the total value of the coins Takahashi picks up when he moves from point S to point T. If he does not pick up any coins, the total is 0.

Constraints

  • 1 \leq N \leq 10^9
  • 0 \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^4 (1 \leq i \leq M)
  • 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), M (the number of coins), S (the starting point), and T (the destination point), separated by spaces.
  • The following M lines provide information about each coin. If M = 0, this part does not exist.
  • The (1 + i)-th line (1 \leq i \leq M) contains the point number P_i where the i-th coin is placed and its value V_i, separated by a space.

Output

Output the total value of the coins Takahashi picked up in a single line.

Sample Input 1

10 5 3 7
1 100
3 10
5 20
5 30
7 40

Sample Output 1

100

Sample Input 2

8 4 6 2
2 5
4 10
6 20
8 100

Sample Output 2

35

Sample Input 3

100 12 20 75
5 100
20 1
25 2
30 3
40 4
40 5
60 6
75 7
76 1000
90 9
55 10
10 11

Sample Output 3

38

Sample Input 4

1000000000 30 800000000 200000000
1 9999
1000000000 8888
800000000 10000
200000000 1
500000000 1234
750000000 4321
250000000 2222
199999999 7777
800000001 6666
600000000 3456
600000000 6544
300000000 1111
400000000 2222
700000000 3333
900000000 4444
100000000 5555
650000000 1010
550000000 2020
450000000 3030
350000000 4040
210000000 5050
790000000 6060
205000000 7070
795000000 8080
123456789 9090
987654321 123
333333333 321
666666666 654
777777777 987
222222222 789

Sample Output 4

73555

Sample Input 5

1 0 1 1

Sample Output 5

0