비밀 회선

시간 제한1초메모리 제한512 MB

요약

각 구성원의 능력치 V와 위치 X가 주어질 때 모든 쌍에 대해 |Xa - Xb| * max(Va, Vb)의 합을 구한다.

난이도: 보통10점 중 7점
유형: 정렬, 분할 정복, 누적 합
정답자: 아직 제출이 없습니다

문제

어느 동아리의 회원은 서로 비밀 회선으로 연결되어 있다. 회원은 모두 N명이고, 각 회원에게는 너드력 V와 1차원 좌표 위의 위치 X가 하나씩 주어진다. 회선을 하나 놓으려면 양쪽 회원의 너드력을 모두 견디는 특수 자재가 필요하다. 회원 a와 회원 b를 잇는 회선에 드는 자재의 개수는 두 사람 사이의 거리에 두 사람의 너드력 중 더 큰 값을 곱한 값이다.

$|X_a - X_b| \times \max(V_a, V_b)$

회원끼리 모두 친하기 때문에, 서로 다른 두 회원마다 직통 회선이 정확히 하나씩 필요하다. 회선을 전부 놓는 데 드는 자재의 총 개수를 구하라.

입력

첫째 줄에 회원 수 N ( $1 \le N \le 50000$ )이 주어진다.

둘째 줄부터 N개의 줄에 각 회원의 너드력 V와 위치 X가 공백으로 구분되어 주어진다 ( $0 \le V, X \le 50000$ ).

출력

필요한 자재의 총 개수를 한 줄에 출력한다. 총 개수는 32비트 정수 범위를 넘을 수 있다.

예제4

예제 1
입력
```
4
3 1
2 5
2 6
4 3
```
예상 출력
```
57
```
예제 2
입력
```
1
50000 50000
```
예상 출력
```
0
```
예제 3
입력
```
2
0 0
0 50000
```
예상 출력
```
0
```
예제 4
입력
```
2
50000 0
50000 50000
```
예상 출력
```
2500000000
```