CSES 3411 ↗

All Manhattan Distances

Sum of the Manhattan distances over all point pairs.

0
submissions
—
best score

Given a set of points, calculate the sum of all Manhattan distances between two point pairs.

Input

The first line has an integer n: the number of points.

The following n lines describe the points. Each line has two integers x and y. You can assume that each point is distinct.

Output

Print the sum of all Manhattan distances.

Constraints

  • 1≤n≤2⋅105
  • −109≤x,y≤109

Example

Input:

5
1 1
3 2
2 4
2 1
4 5

Output:

36

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/AllManhattanDistances/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.