리더 기반 팀 분배
시간 제한2초메모리 제한1024 MB
N명의 선수를 정해진 크기의 M개 팀으로 나눌 때, 각 팀에서 리더 점수가 가장 높은 선수의 플레이어 점수 합을 최대로 만든다.
문제
플레이어 명을 개의 팀으로 나누어 게임을 진행하려 한다. 각 팀의 인원수는 이고, 번째 플레이어는 리더 점수 와 플레이어 점수 를 가진다. 각 플레이어는 정확히 한 팀에 속해야 한다.
각 팀의 리더는 팀에 속한 플레이어 중 리더 점수가 가장 큰 사람이다. 한 팀에서 리더 점수가 가장 큰 플레이어가 여러 명이면 그중 한 명만 리더가 된다. 팀의 능력은 리더의 플레이어 점수로 정의한다.
플레이어를 각 팀에 적절히 분배해 모든 팀의 능력 합을 최대한 크게 만들어 보자.
입력
첫째 줄에 , 이 주어진다. ()
이어지는 개의 줄에 걸쳐 두 정수 와 가 주어진다. ()
마지막 줄에는 개의 정수가 주어진다. 번째 수는 이다. (, )
출력
플레이어를 각 팀에 적절히 분배했을 때 모든 팀의 능력 합의 최댓값을 출력한다.