Giải bài trực tuyến

English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/sails

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ẽ.

Yêu cầu

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.

Dữ liệu

Dòng đầu tiên chứa một số nguyên N (2 ≤ N ≤ 100 000), số cộ 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 ≤ H ≤ 100 000, 1 ≤ K ≤ 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.

Kết quả

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).

Ví dụ

Dữ liệu
6 
3 2 
5 3 
4 1 
2 1 
4 3 
3 2

Kết quả
10