Leader-based Team Distribution
Time limit2sMemory limit1024 MB
Partition N players into M teams of given sizes so the sum of each team's leader player-score (max leader-score member) is maximized.
- Level
Medium7 of 10
- Topics
- Greedy, Sorting, Dynamic programming, Combinatorics
- Solved
- No attempts yet
Problem
We want to split players into teams and play a game. The sizes of the teams are , and player has a leader score and a player score . Each player must belong to exactly one team.
The leader of a team is the player on the team with the largest leader score. If several players on a team tie for the largest leader score, only one of them becomes the leader. The team's ability is defined as the player score of its leader.
Distribute the players among the teams so that the sum of the abilities of all teams is as large as possible.
Input
The first line gives and . ()
The next lines each give two integers and . ()
The last line gives integers. The -th of them is . (, )
Output
Print the maximum possible sum of the abilities of all teams over all valid distributions of the players.