A - 学校対抗マラソン大会 解説 /

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

配点 : 266 点

問題文

高橋君は、地区のマラソン大会の記録係を担当しています。この大会には様々な学校から選手が参加しており、全部で N 人の選手が出場しました。それぞれの選手には 1 から N までの番号が付けられており、選手 i（i = 1, 2, \ldots, N）は学校 C_i に所属していて、ゴールタイムは L_i 秒でした。なお、学校は 1 以上 N 以下の整数で識別され、該当する選手がいない学校番号が存在することもあります。

高橋君は、同じ学校の選手同士のゴールタイムの差を分析することにしました。具体的には、同じ学校に所属する 2 人の選手の組 (i, j)（ただし i < j）すべてについて、ゴールタイムの差の絶対値 |L_i - L_j| を求め、それらの総和

\sum_{\substack{1 \leq i < j \leq N \\ C_i = C_j}} |L_i - L_j|

を計算してください。ある学校に所属する選手が 1 人以下の場合、その学校からは条件を満たすペアが存在しないため、総和への寄与は 0 です。

例えば、学校 1 に所属する選手が 3 人いて、それぞれのゴールタイムが 2 秒、5 秒、9 秒であった場合、この学校からの寄与は |2 - 5| + |2 - 9| + |5 - 9| = 3 + 7 + 4 = 14 となります。

制約

  • 1 \leq N \leq 1000
  • 1 \leq C_i \leq N
  • 1 \leq L_i \leq 10000
  • 入力はすべて整数

入力

N
C_1 L_1
C_2 L_2
\vdots
C_N L_N
  • 1 行目には、選手の人数を表す整数 N が与えられる。
  • 続く N 行のうち i 行目（i = 1, 2, \ldots, N）では、選手 i の所属学校を表す整数 C_i と、ゴールタイムを秒単位で表す整数 L_i が、スペース区切りで与えられる。

出力

すべての学校にわたって、同じ学校に所属する選手の 2 人組のゴールタイムの差の絶対値を合計した値を、整数として 1 行で出力せよ。

入力例 1

5
1 2
1 5
1 9
2 10
2 15

出力例 1

19

入力例 2

8
1 100
2 200
1 150
3 300
2 250
1 120
3 350
2 180

出力例 2

290

入力例 3

12
1 1500
2 1800
3 2100
1 1650
2 1920
3 2250
4 3000
1 1580
2 1750
3 2180
4 3100
5 2500

出力例 3

1040

Score : 266 pts

Problem Statement

Takahashi is in charge of record-keeping for a district marathon competition. Runners from various schools participate in this competition, with a total of N runners competing. Each runner is assigned a number from 1 to N. Runner i (i = 1, 2, \ldots, N) belongs to school C_i and finished with a goal time of L_i seconds. Schools are identified by integers from 1 to N inclusive, and there may be school numbers with no corresponding runners.

Takahashi decided to analyze the differences in goal times between runners from the same school. Specifically, for all pairs (i, j) (where i < j) of two runners belonging to the same school, compute the absolute difference of their goal times |L_i - L_j|, and calculate their total sum:

\sum_{\substack{1 \leq i < j \leq N \\ C_i = C_j}} |L_i - L_j|

If a school has 1 or fewer runners, there are no pairs satisfying the condition from that school, so its contribution to the sum is 0.

For example, if school 1 has 3 runners with goal times of 2 seconds, 5 seconds, and 9 seconds, the contribution from this school is |2 - 5| + |2 - 9| + |5 - 9| = 3 + 7 + 4 = 14.

Constraints

  • 1 \leq N \leq 1000
  • 1 \leq C_i \leq N
  • 1 \leq L_i \leq 10000
  • All inputs are integers

Input

N
C_1 L_1
C_2 L_2
\vdots
C_N L_N
  • The first line contains an integer N representing the number of runners.
  • In the following N lines, the i-th line (i = 1, 2, \ldots, N) contains an integer C_i representing the school that runner i belongs to and an integer L_i representing the goal time in seconds, separated by a space.

Output

Output in a single line, as an integer, the total sum of absolute differences of goal times over all pairs of two runners belonging to the same school, across all schools.

Sample Input 1

5
1 2
1 5
1 9
2 10
2 15

Sample Output 1

19

Sample Input 2

8
1 100
2 200
1 150
3 300
2 250
1 120
3 350
2 180

Sample Output 2

290

Sample Input 3

12
1 1500
2 1800
3 2100
1 1650
2 1920
3 2250
4 3000
1 1580
2 1750
3 2180
4 3100
5 2500

Sample Output 3

1040