Bài 16.5. Lập Kế Hoạch Nhiệm Vụ - [Độ khó: Khá]

Bạn là quản lý dự án và đang có một danh sách các nhiệm vụ cần hoàn thành. Mỗi nhiệm vụ có một "độ ưu tiên" (hay điểm thưởng) và một "thời gian thực hiện" dự kiến. Bạn chỉ có thể chọn thực hiện tối đa K nhiệm vụ do giới hạn về nguồn lực. Để tối đa hóa tổng điểm thưởng đạt được, bạn quyết định rằng sẽ luôn ưu tiên các nhiệm vụ có độ ưu tiên cao hơn. Nếu hai nhiệm vụ có cùng độ ưu tiên, bạn ưu tiên nhiệm vụ có thời gian thực hiện ngắn hơn để hoàn thành sớm hơn các nhiệm vụ quan trọng tương đương.

Hãy viết chương trình tính tổng điểm thưởng tối đa bạn có thể đạt được.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên dương N (\(1 \le N \le 10^5\)) và K (\(1 \le K \le N\)), lần lượt là tổng số nhiệm vụ và số nhiệm vụ tối đa có thể thực hiện. N dòng tiếp theo, mỗi dòng chứa hai số nguyên: THOI_GIAN và DIEM_THUONG.

• THOI_GIAN: Số nguyên dương (\(1 \le THOI\_GIAN \le 10^9\)).
• DIEM_THUONG: Số nguyên dương (\(1 \le DIEM\_THUONG \le 10^9\)).

OUTPUT FORMAT

In ra một số nguyên duy nhất là tổng điểm thưởng tối đa có thể đạt được.

Ví dụ:

Input:

5 3
10 100
5 150
8 100
12 80
6 150

Output:

400

Giải thích:

• N = 5, K = 3. Các nhiệm vụ: (10, 100), (5, 150), (8, 100), (12, 80), (6, 150).
• Quy tắc sắp xếp:
  1. DIEM_THUONG giảm dần.
  2. Nếu DIEM_THUONG bằng nhau, THOI_GIAN tăng dần.
• Sắp xếp các nhiệm vụ theo quy tắc:
  • Nhiệm vụ (5, 150) và (6, 150) có DIEM_THUONG cao nhất (150). Giữa chúng, (5, 150) có THOI_GIAN ngắn hơn (5 < 6), nên nó đứng trước. -> (5, 150) -> (6, 150)
  • Nhiệm vụ (10, 100) và (8, 100) có DIEM_THUONG 100. Giữa chúng, (8, 100) có THOI_GIAN ngắn hơn (8 < 10), nên nó đứng trước. -> (8, 100) -> (10, 100)
  • Nhiệm vụ (12, 80) có DIEM_THUONG thấp nhất (80). -> (12, 80)
• Danh sách nhiệm vụ đã sắp xếp: (5, 150), (6, 150), (8, 100), (10, 100), (12, 80).
• Vì K = 3, ta chọn 3 nhiệm vụ đầu tiên từ danh sách đã sắp xếp:
  • (5, 150)
  • (6, 150)
  • (8, 100)
• Tổng điểm thưởng: \(150 + 150 + 100 = 400\).