trang chủ / bài tập / subjcomp

Đội tuyển nhiều môn

Đề bài

Mô tả

Một cuộc thi gồm nhiều môn sắp diễn ra. Cuộc thi có m môn khác nhau, và ban tổ chức cần chọn một đội tuyển từ n thí sinh.

Mỗi thí sinh i chuyên về đúng một môn si và có mức kỹ năng ri ở môn đó (mức kỹ năng này có thể âm). Mỗi thí sinh chỉ tham gia đúng môn mà mình chuyên.

Đội tuyển được chọn một tập con khác rỗng các môn để tham gia. Ràng buộc duy nhất: số thí sinh tham gia ở mỗi môn được chọn phải bằng nhau.

Hãy chọn các thí sinh sao cho tổng mức kỹ năng của tất cả các thành viên được chọn là lớn nhất. Nếu mọi cách chọn hợp lệ (khác rỗng) đều cho tổng âm, in ra 0 (không cử đội nào đi thi).

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên n và m — số thí sinh và số môn.
  • n dòng tiếp theo, mỗi dòng chứa hai số nguyên si và ri — môn chuyên và mức kỹ năng của thí sinh thứ i.

Dữ liệu ra

  • In ra một số nguyên — tổng mức kỹ năng lớn nhất của một đội tuyển hợp lệ, hoặc 0 nếu mọi đội hợp lệ khác rỗng đều cho tổng âm.

Ràng buộc

  • 1≤n≤105
  • 1≤m≤105
  • 1≤si≤m
  • −104≤ri≤104

Ví dụ

Input Output Giải thích
6 3
2 6
3 6
2 5
3 5
1 9
3 1		 22 Chọn thí sinh 1, 2, 3, 4: hai người môn 2 và hai người môn 3, mỗi môn 2 người. Tổng 6+6+5+5=22.
5 3
2 6
3 6
2 5
3 5
1 11		 23 Chọn thí sinh 1, 2, 5: mỗi môn đúng 1 người. Tổng 6+6+11=23.
5 2
1 -1
1 -5
2 -1
2 -1
1 -10		 0 Mọi cách chọn khác rỗng đều cho tổng âm nên không cử đội đi thi.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0