Bọn cướp biển đang đóng một chiếc tàu mới. Chiếc tàu này có ~N~ cột buồm chia thành các đoạn độ dài đơn vị, độ cao của một cột buồm bằng số đoạn thẳng trên cột buồm. Mỗi cột buồm có một số lá buồm, mỗi lá buồm nằm gọn trên một đoạn độ dài đơn vị. Các lá buồm trên một cột có thể được phân bố tùy ý vào các đoạn khác nhau trên cột buồm, nhưng mỗi đoạn chỉ được chứa đúng một lá buồm.

Mỗi cách sắp đặt lá buồm khác nhau sẽ tạo ra một lực đẩy gió khác nhau khi thuyền ra khơi. Các lá buồm đằng trước các lá buồm khác ở cùng độ cao sẽ nhận được ít gió hơn và tạo ít lực đẩy hơn. Với mỗi lá buồm, ta định nghĩa độ kém hiệu quả của nó là tổng số lá buồm có cùng độ cao ở phía sau nó. Chú ý là "phía trước" và "phía sau" phụ thuộc vào hướng của con thuyền: trong hình vẽ dưới đây, "phía trước" nghĩa là ở bên trái, "phía sau" nghĩa là ở bên phải.

Độ kém hiệu quả của cả con thuyền là tổng độ kém hiệu quả của mỗi lá buồm.

Con thuyền này có ~6~ cột buồm, với độ cao ~3~, ~5~, ~4~, ~2~, ~4~ và ~3~ từ phía trước (bên trái của hình vẽ) đến phía sau.

Cách sắp xếp các lá buồm này cho độ kém hiệu quả là ~10~. Độ kém hiệu quả của mỗi lá buồm được ghi trên lá buồm đó trên hình vẽ. Viết chương trình nhập vào độ cao và số lá buồm trên mỗi trong số ~N~ cột buồm, xác định độ kém hiệu quả nhỏ nhất có thể của con thuyền.

Input

Dòng đầu tiên chứa một số nguyên ~N~ (~2 \leq N \leq 10^5~), số cột buồm của con thuyền.

Mỗi trong số ~N~ dòng tiếp theo chứa hai số nguyên ~H~ và ~K~ (~1 \leq H \leq 10^5~, ~1 \leq K \leq H~), độ cao và số lá buồm trên cột buồm tương ứng. Các cột buồm được cho theo thứ tự từ phía trước đến phía sau của con thuyền.

Output

In ra một số nguyên duy nhất, độ kém hiệu quả nhỏ nhất cỏ thể của con thuyền.

Chú ý: dùng kiểu số nguyên ~64~ bit để tính và in kết quả (long long trong C/C++, int64 trong Pascal).

Sample Input

6
3 2
5 3
4 1
2 1
4 3
3 2

Sample Output

10