제재소 두 곳

언덕 꼭대기에서 기슭까지 이어지는 길을 따라 오래된 나무 $n$그루가 심어져 있다. 이 나무들을 모두 베어 제재소로 옮기려고 한다. 목재를 낭비하지 않도록 베어낸 나무는 모두 제재소로 운반해야 한다.

목재는 오직 아래쪽(기슭 방향)으로만 운반할 수 있다. 길의 가장 아래쪽 끝에는 제재소가 하나 있다. 여기에 더해 길을 따라 제재소 두 곳을 추가로 지을 수 있으며, 운반 비용이 최소가 되도록 그 위치를 정해야 한다. 베어낸 각 나무는 자신의 위치에서 아래쪽으로 내려가 처음 만나는 제재소로 운반된다. 운반 비용은 목재 1킬로그램을 1미터 옮길 때마다 1센트가 든다.

표준 입력으로 나무의 수, 각 나무의 무게와 위치가 주어질 때, 가능한 최소 운반 비용을 구하여 표준 출력으로 출력하는 프로그램을 작성하라.

첫째 줄에 나무의 수 $n$이 주어진다 ($2 \le n \le 20000$). 나무는 언덕 꼭대기에서 기슭 방향으로 내려가며 $1, 2, \dots, n$으로 번호가 매겨져 있다. 이어지는 $n$개의 줄 중 $i$번째 줄에는 두 정수 $w_i$와 $d_i$가 공백 하나로 구분되어 주어진다. $w_i$는 $i$번 나무의 무게(킬로그램)이고 ($1 \le w_i \le 10000$), $d_i$는 $i$번 나무와 $i+1$번 나무 사이의 거리(미터)이다 ($0 \le d_i \le 10000$). 마지막 값 $d_n$은 $n$번 나무에서 길의 아래쪽 끝에 있는 제재소까지의 거리이다. 모든 나무를 길 끝의 제재소까지 운반하는 총비용은 2,000,000,000센트 미만임이 보장된다.

첫째 줄에 최소 운반 비용을 나타내는 정수 하나를 출력한다.

추가 제재소 두 곳은 나무가 있는 위치에 지을 수 있다. 각 나무는 자신과 같은 위치이거나 그보다 아래에 있는 가장 가까운 제재소로 운반된다. 아래 그림은 첫 번째 테스트 케이스의 입력에 대한 최적의 제재소 배치를 보여 준다. 나무는 무게가 적힌 원으로, 제재소는 검은색으로 표시되어 있다. 이때 최소 비용은 다음과 같이 $26$이 된다.

$1 \cdot (2 + 1) + 2 \cdot 1 + 1 \cdot (1 + 2) + 3 \cdot 2 + 2 \cdot (1 + 2 + 1) + 1 \cdot (2 + 1) + 1 \cdot 1 = 26$