31410번 - 제독 작전

문제

부대에 미확인 오염 물질이 발생해 위기에 빠졌다! 오염 물질은 부대 내의 수직선 위의 서로 다른 $N$개의 위치에 발생했으며, 그중 $i$번째 오염 물질의 오염도는 $p_i$이며 $x_i$ 위치에 발생했다. 오염 물질을 정화하기 위해서는 제독병이 오염 물질의 위치까지 이동하여 제독 장비를 사용해 오염도 이상의 제독제를 뿌려야 한다. 이를 위해 제독병은 서둘러 제독 장비에 제독제를 충전하기로 했다.

그러나 제독제를 충전하러 가던 중 실수로 제독 장비를 떨어뜨려 밑부분에 금이 가버렸고, 이 때문에 제독 장비를 사용할 때마다 금이 점점 커져 1ドル$분마다 제독 장비를 사용했던 횟수만큼의 제독제가 제독 장비에서 흘러내릴 것이다. 흘러내린 제독제는 더 이상 오염 물질을 정화하는 데 사용할 수 없다.

제독병이 제독을 시작할 수직선 위의 위치는 임의로 정할 수 있으며, 시작할 위치에서 가까운 순서대로 오염 물질을 정화하려 한다. 시작 위치와의 거리가 같은 오염 물질이 있다면, 거리가 같은 오염 물질의 정화 순서는 임의로 정할 수 있다. 제독병은 1ドル$분에 1ドル$만큼의 거리를 이동할 수 있으며, 제독병이 제독 장비를 사용하면 현재 제독병의 위치에 있는 오염 물질에 제독제를 뿌릴 수 있다. 제독 장비를 한 번 사용할 때 뿌릴 수 있는 제독제의 양에는 제한이 없으며 시간이 소요되지 않는다.

제독병은 미확인 오염 물질을 분석하기 위해 아무 곳이나 한 곳을 남겨 두고 나머지 $N-1$개의 오염 물질을 제독을 시작할 위치에서 가까운 순서대로 정화하려고 하며, 이를 위해 충전해야 할 제독제의 양을 최소화하고자 한다. 제독병을 위해 금이 간 제독 장비를 사용하여 $N-1$개의 오염 물질을 정화하기 위해 충전해야 할 최소 제독제의 양을 계산해 주자.

입력

첫 번째 줄에 오염 물질의 개수를 의미하는 정수 $N$이 주어진다. $(2 \leq N \leq 100,000円)$

이후 $N$개의 줄에 걸쳐, 각 오염 물질의 위치를 의미하는 정수 $x_i$와 오염도를 의미하는 정수 $p_i$가 공백으로 구분되어 주어진다. $(-10^9 \leq x_i \leq 10^9; 1 \leq p_i \leq 10^9)$

오염 물질의 위치가 중복되는 입력은 주어지지 않는다.

출력

금이 간 제독 장비를 사용하여 $N-1$개의 오염 물질을 정화하기 위해 충전해야 할 최소 제독제의 양을 출력한다.

제한

힌트