Програмчлалын олимпиадын бодлогын архив

Уулын орой уулын бэл хоёрыг холбосон замын дагуу n ширхэг мод байжээ.Ерөнхийлөгч Энхбаяр, байгаль орчны сайд 2 хамтран бүгдийг тайрах шийдвэр гаргажээ.Бүх тайрсан модыг мод боловшруулах үйлдвэр рүү зөөх ёстой болсон.

Модыг зөвхөн дээрээс доош чиглэлд л зөөнө.Уулын бэлд нэг ширхэг мод боловсруулах үйлдвэр байгаа. Бидэнд замын дагуу дахиж 2 ширхэг үйлдвэр барих хөрөнгө байгаа.Таны даалгавар бол замын зардлыг хэмнэхийн тулд энэ 2-г хаана байрлуулахыг шийдэх юмаа.Нэг килограм модыг нэг метер зөөхөд нэг төгрөг зарцуулдаг.

Input

Эхны мөрөнд n (2<=n<=20 000). Моднууд дээрээс доошоо 1-ээс n хүртэл дугаарлагдсан. Дараагийн n ширхэг мөрөнд 2 тоо, w_i d_i, байна. w_i - i дугаар модны жин (килограмаар), d_i - i болон i+1 дугаар модны хоорондох зай (метерээр). 1<=w_i<=10 000, 0<=d_i<=10 000. d_n нь n-дүгээр мод болон уулын бэл дэх үйлдвэрийн хоорондох зай.

Output

Хамгийн бага зардал

Example

Input:
9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1

Output:
26