分数: 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