← 返回题目列表

AtCoder · awc0011_a

A. 沿着樱花树散步

中文机器翻译题面 查看原题

分数: 200 分

问题陈述

高桥正在一条路上散步, N 点排列成一条直线。点已编号 1, 2, \ldots, N 从左到右,以及编号不同的点 1 彼此相邻。

沿着这条路, M 种植樱花树。的 i第棵樱花树已种植于点 P_i,当高桥访问该点时, V_i 花瓣落下,高桥全部收到。每个点最多种植一棵樱花树。

高桥从点开始 S 并移动到点 T。他一次从一个相邻的点出发 S 朝 T,义无反顾。因此,高桥访问的点,包括起点和终点如下:

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

If S = T,高桥不动,只访问点 S.

由于 Takahashi 仅向一个方向移动,因此他只访问每个点一次。求高桥从点移动时收到的花瓣总数 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
  • 第一行包含 N,点数,以及 M,樱花树的数量,以空格分隔。
  • 第二行包含 S,起点,以及 T,目标点,以空格分隔。
  • 从第 3 行到 (M + 2)第行,给出了每棵樱花树的信息。
  • 的 (2 + i)第行包含 P_i,该点 i第棵樱花树被种植,并且 V_i,从该树掉落的花瓣数量,以空格分隔。

输出

在一行中打印高桥从点移动时收到的花瓣总数 S 点 T.


示例输入 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