Mã Độc

Xem dạng PDF

Gửi bài giải


Điểm: 0,01 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Pengin là điệp viên của một tổ chức tình báo. Tổ chức phát hiện ~N~ máy chủ bị nhiễm mã độc. Máy chủ thứ ~i~ có mức độ nguy hiểm là ~A_i~ và hạn chót để xử lý là ~D_i~.

Mỗi ngày, Pengin chỉ có thể xử lý triệt để duy nhất một máy chủ. Nếu máy chủ ~i~ được xử lý tại ngày ~t~, Pengin sẽ nhận được số điểm uy tín là ~A_i~, với điều kiện ~t \le D_i~. Nếu ~t > D_i~, máy chủ đó tự hủy và Pengin không nhận được điểm.

Tuy nhiên, Pengin có ~K~ "Thiết bị đóng băng". Mỗi thiết bị chỉ dùng được một lần. Khi dùng một thiết bị, Pengin xử lý một máy chủ bất kỳ mà không tiêu tốn thời gian của ngày đó, tức là ngày hôm đó Pengin vẫn có thể xử lý thêm một máy chủ khác theo cách bình thường. Pengin có thể dùng nhiều thiết bị trong cùng một ngày.

Hãy tìm tổng số điểm uy tín lớn nhất có thể đạt được, xuất phát với thời gian ~t = 1~.

Input

Dòng thứ nhất chứa hai số nguyên ~N~ và ~K~ (~1 \le N \le 2 \cdot 10^5~, ~0 \le K \le N~).

Mỗi dòng trong ~N~ dòng tiếp theo chứa hai số nguyên ~A_i~ và ~D_i~ (~1 \le A_i \le 10^9~, ~1 \le D_i \le N~).

Output

Một số nguyên duy nhất là tổng điểm lớn nhất thu được.

Scoring

Subtask Điểm Giới hạn
1 ~15~ ~N \le 10~, ~K = 0~
2 ~20~ ~N \le 2000~, ~K = 0~
3 ~25~ ~K = 0~
4 ~20~ ~N \le 2000~
5 ~20~ Không có ràng buộc gì thêm

Sample Input 1

6 2
100 1
20 1
80 2
90 2
40 3
10 1

Sample Output 1

330

Notes

Trong các ngày ~1~, ~2~, ~3~, Pengin xử lý các máy chủ có điểm ~100~, ~90~, ~40~. Hai thiết bị đóng băng dùng cho các máy chủ có điểm ~80~ và ~20~. Tổng là ~330~.


Đang tải...