Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P191SUMC - Cuộc thi

Time limit: 2s

Một cuộc thi lập trình đang đến! Cuộc thi có m nội dung mà người tham gia có thể lựa chọn. Đó là lý do tại sao Okami (leader) phải thành lập một đoàn thi đấu từ các thành viên trong đội của mình.

Anh có n thành viên trong đội của mình. Đối với thành viên thứ i, anh ta biết người này chuyên về nội dung Si và trình độ chuyên môn Ri (Ri có thể âm).

Thể lệ của cuộc thi yêu cầu mỗi đoàn phải chọn một số tập hợp con các nội dung họ sẽ tham gia. Hạn chế duy nhất là số lượng người trong đội tham gia vào mỗi nội dung được chọn phải giống nhau.

Okami quyết định rằng mỗi thành viên được chọn sẽ chỉ tham gia vào nội dung mà anh ta chuyên. Bây giờ Okami tự hỏi mình phải chọn ai để tối đa hóa tổng số cấp độ kỹ năng của tất cả các thành viên, hoặc bỏ qua cuộc thi năm nay nếu mọi cách hợp lệ có tổng âm.

(Tất nhiên, Okami không có bất kỳ khoản tiền dư nào nên mỗi thành viên mà anh ta chọn phải tham gia cuộc thi).

Input :

- Dòng đầu tiên chứa hai số nguyên n và m (1 ≤ n ≤ 105, 1≤ m ≤ 105) - số lượng thành viên và số lượng nội dung.

- N dòng tiếp theo chứa hai số nguyên trên mỗi dòng: Si và Ri (1 ≤ Si ≤ m, −104 ≤ Ri ≤ 104) – nội dung chuyên môn và trình độ độ kỹ năng của thành viên thứ i.

Output :   

- In một số nguyên duy nhất - tổng số kỹ năng tối đa của các thành viên thành một đội hợp lệ (theo quy tắc ở trên) hoặc 0 nếu mọi cách hợp lệ đều có tổng âm.

Example :

Input

Ouput

6 3

2 6

3 6

2 5

3 5

1 9

3 1

22

5 2

1 -1

1 -5

2 -1

2 -1

1 -10

0

Giải thích:

- Trong ví dụ đầu tiên, tối ưu để chọn các thành viên 1, 2, 3, 4, vì vậy hai trong số họ chuyên về nội dung số 2 và hai người khác trong số họ chuyên về nội dung số 3. Tổng trình độ chuyên môn là 6 + 6 + 5 + 5 = 22.

- Trong ví dụ thứ hai, không thể có được tổng không âm.


Được gửi lên bởi:adm
Ngày:2019-07-13
Thời gian chạy:1s-2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2023-02-08 02:57:10
ở vd1 sao không phải là 1 2 3 4 6 nhỉ... 3 người chuyên 3,2 người chuyên 2 và tổng là 23. vì đề bài không đề cập đến giới hạn số người tham gia mà nhỉ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.