피자 배달

JAG 피자는 유명한 피자 가게이다. 배달 주문이 늘어나서 예전보다 훨씬 바빠졌다.

어느 날 주문 여러 건이 같은 시각에 동시에 들어왔다. 주문은 $N$건이고 주문한 고객도 $N$명이다. $i$번째 고객이 $i$번째 주문을 했다.

가게는 고객마다 다음 정보를 알고 있다. $i$번째 고객에게 가게에서 피자를 배달하는 데 $t_i$시간이 걸리고, 배달원이 가게로 돌아오는 데도 $t_i$시간이 걸린다. 고객의 짜증 지수는 $a_i$이다. 짜증 지수가 클수록 고객은 쉽게 화를 낸다.

배달 계획은 다음 조건을 따라야 한다.

• 배달원은 한 명뿐이다.
• 배달원은 주문을 여러 건 동시에 배달할 수 없다. 한 번에 주문 하나만 배달하고, 배달을 마치면 가게로 돌아온 뒤 다음 주문을 맡는다.
• 주문을 준비하는 시간, 가게에서 배달원에게 넘기는 시간, 배달원이 고객에게 넘기는 시간은 0이다.

$i$번째 고객이 받는 스트레스는 $s_i = a_i \times (h_i + p_i)$이다. 여기서 $h_i$는 주문한 시점부터 배달이 끝날 때까지 걸린 시간이고, $p_i$는 배달이 $i$번째 고객보다 먼저 끝나는 다른 고객의 수이다.

모든 고객이 받는 스트레스의 합이 최소가 되는 계획을 구하라.

첫 줄에 고객 수 $N$이 주어진다 ($1 \le N \le 100000$).

다음 $N$개 줄에 정수 $t_i$와 $a_i$가 주어진다 ($1 \le t_i \le 1000$, $1 \le a_i \le 1000$). $t_i$는 $i$번째 고객까지의 편도 배달 시간이고, $a_i$는 그 고객의 짜증 지수이다.

모든 고객 스트레스 합의 최솟값을 한 줄에 출력한다.