C - フリーマーケットの相乗効果 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は文化祭でフリーマーケットの運営を担当しています。フリーマーケットには N 個の出店ブースがあり、1 から 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 で定義されます。

高橋君は、コラボレーションが成立するすべてのペアについて、相乗効果の総和を求めたいと考えています。

N 個のブースについて、それぞれの座標と集客力が与えられるので、コラボレーションが成立するすべてのブースのペア (i, j) (1 \leq i < j \leq N) について、相乗効果 S_i \times S_j の総和を求めてください。

制約

  • 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
  • 1 行目には、ブースの数 N と、コラボレーションが成立する座標の差の上限 D が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目 (1 \leq i \leq N) には、ブース i の座標 X_i と集客力 S_i が、スペース区切りで与えられる。

出力

コラボレーションが成立するすべてのペアの相乗効果の総和を 1 行で出力せよ。

入力例 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

Score : 366 pts

Problem Statement

Takahashi is in charge of running a flea market at a school festival. The flea market has N vendor booths, numbered from 1 to N.

The booths are arranged on a straight line. Booth i (1 \leq i \leq N) has coordinate X_i and attractiveness S_i.

As a festival event, nearby booths will conduct collaboration sales with each other. Specifically, for a pair of two distinct booths (i, j) (1 \leq i < j \leq N), if the absolute difference in their coordinates |X_i - X_j| is at most D, customers can easily go back and forth between both booths, so the collaboration is established. If |X_i - X_j| is greater than D, the collaboration is not established.

The "synergy" of a pair where collaboration is established is defined as the product of the attractiveness values of the two booths: S_i \times S_j.

Takahashi wants to find the total sum of synergy over all pairs where collaboration is established.

Given the coordinate and attractiveness of each of the N booths, find the sum of the synergy S_i \times S_j over all pairs of booths (i, j) (1 \leq i < j \leq N) where collaboration is established.

Constraints

  • 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)
  • All X_i are distinct
  • All input values are integers
  • It is guaranteed that the answer (the total sum of synergy) is at most 2^{63} - 1

Input

N D
X_1 S_1
X_2 S_2
\vdots
X_N S_N
  • The first line contains the number of booths N and the upper limit D on the coordinate difference for collaboration to be established, separated by a space.
  • The i-th of the following N lines (1 \leq i \leq N) contains the coordinate X_i and attractiveness S_i of booth i, separated by a space.

Output

Print the total sum of synergy over all pairs where collaboration is established, in a single line.

Sample Input 1

3 3
1 2
3 3
7 4

Sample Output 1

6

Sample Input 2

4 10
1 1
2 2
5 3
8 4

Sample Output 2

35

Sample Input 3

8 5
0 3
2 7
4 1
8 5
10 2
15 6
17 4
20 8

Sample Output 3

162

Sample Input 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

Sample Output 4

4875

Sample Input 5

1 1000000000
500000000 10000

Sample Output 5

0