Nhà vua vừa mở hội mấy ngày đêm, già trẻ trai gái các làng đều nô nức tham dự. Trên các nẻo đường, quần áo mớ ba mớ bảy dập dìu tuôn về kinh như nước chảy. Hai mẹ con Cám cũng sắm sửa quần áo đẹp để đi trẩy hội. Thấy Tấm cũng muốn đi, mụ dì ghẻ nguýt dài. Sẵn có chén gạo trong góc tường, mụ đổ ra sàn và bắt Tấm phải nhặt từng hạt gạo và bỏ vào hai hũ. Biết rằng chén gạo có đúng K hạt gạo và hạt gạo thứ i khi được bỏ vào hũ thứ nhất sẽ có độ ngon là ai , khi được bỏ vào hũ thứ hai sẽ có độ ngon là bi.

Dì ghẻ yêu cầu Tấm chia đúng N hạt gạo vào hũ thứ nhất và M hạt gạo vào hũ thứ hai sao cho độ ngon là lớn nhất. Số gạo còn dư sẽ được đem đi cho gà trong vườn. Vì số lượng hạt gạo quá nhiều nên Tấm gặp khó khăn trong việc phân loại.

Yêu cầu: Hãy giúp Tấm tính tổng độ ngon lớn nhất khi bỏ gạo vào hai hũ nhé.

Dữ liệu:

• Dòng đầu tiên chứa ba số nguyên dương K, N, M (K ≤ 10^3, N + M ≤ K)
• Dòng thứ i trong K dòng tiếp theo chứa hai số nguyên dương ai, bi (1 ≤ ai, bi ≤ 10^5) là độ ngon tương ứng của hạt thứ i khi bỏ vào hũ thứ nhất và hũ thứ hai.

Kết quả:

Đưa ra một số nguyên duy nhất là tổng độ ngon của các hạt gạo trong hai hũ.

Ví dụ:

Input

4 2 1
4 9
3 5
7 2
5 5

Output

21 

GIẢI THÍCH

• Hũ thứ nhất sẽ chứa hạt gạo thứ 3 và 4 do đó có độ ngon là 7 + 5 = 12.
• Hũ thứ hai sẽ chứa hạt gạo thứ 1 do đó có độ ngon là 9. Tổng độ ngon sẽ là 12 + 9 = 21.

Ràng buộc:

• Subtask 1 (25% số điểm): K ≤ 15
• Subtask 2 (25% số điểm): K, M ≤ 10^3, N = 1
• Subtask 3 (25% số điểm): K ≤ 400
• Subtask 4 (25% số điểm): Không có ràng buộc gì thêm.

Bản PDF