Độ khó: Trung bình (2/4 điểm)

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Sáng nay, tiệm sửa đồng hồ của thầy Sơn nhận cùng lúc ~N~ chiếc đồng hồ của ~N~ khách hàng (tất cả được giao ở thời điểm ~0~). Chiếc đồng hồ thứ ~i~ cần đúng ~t_i~ phút để sửa xong.

Thầy Sơn làm một mình nên chỉ sửa được một chiếc tại một thời điểm; khi đã bắt đầu sửa chiếc nào thì phải sửa xong chiếc đó rồi mới chuyển sang chiếc khác, giữa hai chiếc không có thời gian nghỉ.

Theo cam kết của tiệm, khách hàng thứ ~i~ được đền bù ~w_i~ nghìn đồng cho mỗi phút chờ, tính từ thời điểm ~0~ đến lúc đồng hồ của họ sửa xong. Nghĩa là nếu đồng hồ thứ ~i~ sửa xong tại thời điểm ~C_i~ thì tiệm phải đền ~w_i \times C_i~ nghìn đồng cho khách đó.

Hãy giúp thầy Sơn chọn thứ tự sửa đồng hồ sao cho tổng tiền đền bù ~\sum_{i=1}^{N} w_i \times C_i~ là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 2 \times 10^5)~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~t_i~ và ~w_i~ ~(1 \le t_i, w_i \le 10^4)~.

Kết quả

Một số nguyên duy nhất là tổng tiền đền bù nhỏ nhất (đơn vị: nghìn đồng).

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 8~.
• Subtask 2 (~30\%~ số điểm): ~w_i = 1~ với mọi ~i~.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 2 giây.

Sample Input 1

3
3 1
1 2
4 6

Sample Output 1

40

Giải thích

Sửa theo thứ tự đồng hồ ~2 \to 3 \to 1~:

• Đồng hồ ~2~ xong tại phút ~1~, đền ~2 \times 1 = 2~.
• Đồng hồ ~3~ xong tại phút ~1 + 4 = 5~, đền ~6 \times 5 = 30~.
• Đồng hồ ~1~ xong tại phút ~5 + 3 = 8~, đền ~1 \times 8 = 8~.

Tổng cộng ~2 + 30 + 8 = 40~, không có thứ tự nào cho tổng nhỏ hơn.

Nguồn: Đề tự luyện HSG Tin học lớp 9 (đề tự soạn).