Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

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 ≤ 10⁵, 1≤ m ≤ 10⁵) - 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 ≤ S_i ≤ m, −10⁴ ≤ Ri ≤ 10⁴) – 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.