Một chiếc thuyền buồm mới dành cho cướp biển đang được đóng. Thuyền có \(N\) cột buồm, mỗi cột được chia thành các đoạn có độ dài một đơn vị; chiều cao của cột bằng số đoạn của nó. Mỗi cột được gắn một số cánh buồm, mỗi cánh chiếm vừa đúng một đoạn. Có thể đặt các cánh buồm trên một cột vào các đoạn khác nhau tùy ý, nhưng mỗi đoạn chỉ được gắn nhiều nhất một cánh buồm.

Các cách bố trí buồm khác nhau tạo ra lực đẩy khác nhau khi đón gió. Những cánh buồm nằm phía trước các cánh buồm khác ở cùng độ cao nhận được ít gió hơn và tạo ra ít lực đẩy hơn. Với mỗi cánh buồm, định nghĩa độ kém hiệu quả của nó là tổng số cánh buồm nằm phía sau nó và ở cùng độ cao. Hai khái niệm phía trước và phía sau được xác định theo hướng của thuyền: trong hình minh họa, phía trước ở bên trái, phía sau ở bên phải.

Tổng độ kém hiệu quả của một cách bố trí là tổng độ kém hiệu quả của tất cả các cánh buồm.

Thuyền trong hình có \(6\) cột buồm với chiều cao lần lượt là \(3,5,4,2,4,3\), tính từ phía trước (front, bên trái hình) ra phía sau (back, bên phải hình). Cách bố trí này có tổng độ kém hiệu quả bằng \(10\). Số ghi trong mỗi cánh buồm là độ kém hiệu quả của riêng cánh buồm đó.

Cho chiều cao và số cánh buồm của từng cột, hãy tìm tổng độ kém hiệu quả nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\), là số cột buồm trên thuyền.

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

Dữ liệu ra

Ghi một số nguyên duy nhất: tổng độ kém hiệu quả nhỏ nhất có thể.

Lưu ý dùng kiểu số nguyên \(64\) bit để tính toán và xuất kết quả, chẳng hạn long long trong C/C++ hoặc int64 trong Pascal.

Ràng buộc

• \(2\le N\le 100\,000\).
• \(1\le H\le 100\,000\).
• \(1\le K\le H\).

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Các ví dụ trong đề không tính điểm.

Ví dụ

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

10

Nguồn

IOI 2007.