077 - Distance Sum 解説 /

実行時間制限: 1 sec / メモリ制限: 1024 MB

配点: 1000

問題文

2 次元座標上にN個の点があります。i番目の点の座標は(X_i, Y_i)です。\mathcal{dist} (i, j)i番目の点とj番目の点の間のマンハッタン距離とするとき、次式の値を求めるプログラムを作成してください。ただし、座標(x_1 , y_1)と座標(x_2,y_2)の間のマンハッタン距離は|x_1 − x_2| + |y_1 − y_2|で定義されます。

\sum_{i=1}^{N} \sum_{j=i+1}^{N} \mathcal{dist} (i,j)

制約

  • 2 \leq N \leq 200000
  • -10^5 \leq X_i , Y_i \leq 10^5
  • X_i,Y_iは整数

入力

入力は以下の形式で標準入力から与えられます。

N
X_1 Y_1
X_2 Y_2
:
X_N Y_N

出力

式の値を出力してください。


入力例 1

2
1 2
10 20

出力例 1

27