최고의 팀 만들기
면접 대비시간 제한1초메모리 제한128 MB
최대 1000명의 선수 중 백 15명과 흑 15명을 골라 능력치 합을 최대화하는 문제입니다.
문제
꿍 협회는 매년 세계 체스 대회에 참가할 30명 팀을 구성한다. 팀은 백으로 플레이할 15명과 흑으로 플레이할 15명으로 이루어진다. 각 플레이어에게는 백 실력과 흑 실력이 각각 1 이상 100 이하의 정수로 주어진다. 한 플레이어는 대회 동안 백 또는 흑 중 하나의 역할로만 참가할 수 있으며, 선택되지 않을 수도 있다. 팀의 전체 능력치는 백으로 뛸 선수들의 백 실력 합과 흑으로 뛸 선수들의 흑 실력 합을 더한 값이다. 만들 수 있는 팀의 전체 능력치의 최댓값을 구하라.
입력
입력은 플레이어들의 능력치 목록으로 주어진다. 각 줄에는 두 정수 W와 B가 공백으로 구분되어 주어진다. W는 해당 플레이어가 백으로 플레이할 때의 능력치이고, B는 흑으로 플레이할 때의 능력치이다. 입력은 최소 30줄, 최대 1000줄로 이루어지며 파일의 끝까지 읽으면 된다.
출력
구성할 수 있는 팀 중 전체 능력치가 최대가 되도록 할 때, 그 최댓값을 출력한다.