꽃 지키기

농부 존이 평소처럼 소 N마리(2 ≤ N ≤ 100,000)를 풀밭에 두고 나무를 하러 갔다. 돌아와 보니 소 떼가 정원에 들어가 그가 애지중지하던 꽃을 뜯어먹고 있었다. 피해를 최소화하려고 존은 즉시 소들을 한 마리씩 각자의 외양간으로 데려다 놓기로 했다.

소 $i$는 자기 외양간에서 $T_i$분(1 ≤ $T_i$ ≤ 2,000,000) 떨어진 곳에 있다. 또한 소 $i$는 옮겨지기를 기다리는 동안 1분에 꽃 $D_i$송이(1 ≤ $D_i$ ≤ 100)를 망가뜨린다. 존은 한 번에 소 한 마리만 데려갈 수 있다. 소 $i$를 외양간까지 데려가는 데는 $2 T_i$분이 걸린다(가는 데 $T_i$분, 돌아오는 데 $T_i$분). 존은 꽃밭에서 출발해 소를 외양간에 데려다 놓고 다시 꽃밭으로 돌아오며, 다음 소를 데리러 가는 추가 시간은 들지 않는다.

한 소를 외양간으로 옮기는 동안, 아직 옮겨지지 않은 나머지 소들은 계속 꽃을 망가뜨린다. 망가지는 꽃의 총 개수가 최소가 되도록 존이 소를 데려가는 순서를 정하고, 그때 망가지는 꽃의 최소 총 개수를 구하는 프로그램을 작성하라.

• 첫째 줄: 정수 $N$.
• 둘째 줄부터 $N+1$째 줄까지: 각 줄에 소 한 마리를 나타내는 두 정수 $T_i$와 $D_i$가 공백으로 구분되어 주어진다.

• 첫째 줄: 망가지는 꽃의 최소 총 개수를 나타내는 정수 하나.

위 예제에서 존은 소를 6, 2, 3, 4, 1, 5 순서로 데려간다. 소 6을 외양간으로 옮기는 동안 나머지 소들이 꽃 24송이를 망가뜨린다. 이어서 소 2를 옮기는 동안 28송이, 소 3, 4, 1을 옮기는 동안 각각 16, 12, 6송이가 망가진다. 마지막으로 소 5를 옮길 때는 남은 소가 없으므로 이때 망가지는 꽃은 0송이다. 따라서 총 24 + 28 + 16 + 12 + 6 = 86송이가 망가진다.