分数: 366 分
问题陈述
高桥负责在学园祭期间经营跳蚤市场。跳蚤市场有 N 供应商摊位,编号从 1 to N.
展位呈直线排列。展位 i (1 \leq i \leq N) 有 坐标 X_i 和 吸引力 S_i.
作为节日活动,附近摊位之间会进行联名促销。具体来说,对于两个不同的展位 (i, j) (1 \leq i < j \leq N),如果它们的坐标的绝对差 |X_i - X_j| 最多是 D,客户可以轻松地在两个展位之间来回,从而建立了合作。如果 |X_i - X_j| 大于 D,协作未建立。
“协同作用“建立合作的一对被定义为两个展位吸引力值的乘积: S_i \times S_j.
Takahashi 希望找到所有已建立合作的对的协同效应总和。
给定每个的坐标和吸引力 N 展位,求协同效应之和 S_i \times S_j 所有对展位 (i, j) (1 \leq i < j \leq N) 建立协作。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq D \leq 10^9
- 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq S_i \leq 10^4 (1 \leq i \leq N)
- 全部 X_i 是不同的
- 所有输入值均为整数
- 保证答案(协同总和)最多为 2^{63} - 1
输入
N D X_1 S_1 X_2 S_2 \vdots X_N S_N
- 第一行包含展位数量 N 和上限 D 上要建立的协作的坐标差,以空格分隔。
- 的 i- 以下各项 N 行 (1 \leq i \leq N) 包含坐标 X_i 和吸引力 展位 S_i 展位数量 i,用空格分隔。
输出
在一行中打印建立协作的所有对的协同总和。
示例输入 1
3 3 1 2 3 3 7 4
示例输出 1
6
示例输入 2
4 10 1 1 2 2 5 3 8 4
示例输出 2
35
示例输入 3
8 5 0 3 2 7 4 1 8 5 10 2 15 6 17 4 20 8
示例输出 3
162
示例输入 4
15 100 10 50 200 30 350 80 500 20 610 90 750 40 880 60 1000 10 1050 70 1200 100 1350 25 1500 55 1600 35 1700 45 1800 15
示例输出 4
4875
示例输入 5
1 1000000000 500000000 10000
示例输出 5
0