문제

2150년, Kureyo Baseball Organization(이하 KBO)은 100번째 구단의 창단을 승인하였다. 그 전까지는 지난 시즌의 순위에 따라 지그재그식으로 한 선수씩 선발하는 식이었지만, 구단이 매우 많아지면서 드래프트가 너무 오랜 시간이 걸리게 되자 KBO는 다음과 같은 새로운 드래프트 룰을 발표하였다.

• 드래프트를 신청한 선수 N명은 출신 학교, 대회 입상 성적, 신체 조건 등의 다양한 요소를 고려한 임의의 순서로 정렬된다.
• 각 선수는 자신의 고유 수비 위치를 나타내는 정수인 P_i (1 <= P_i <= 9) 와 수비 능력을 나타내는 정수인 A_i로 표현된다.
• 각 구단은 자신의 드래프트 차례가 오면 선수들의 목록에서 연속된 K명을 뽑고 해당 선수들을 목록에서 지운다.
• 이 때 선택된 K명 안에는 각 아홉 가지의 수비 위치에 대해 해당 위치를 수비할 수 있는 선수가 반드시 적어도 한 명씩 포함되어야 한다.

당신은 전년도에 꼴찌를 한 '쌍둥이들'의 감독으로 이번 드래프트에서 가장 먼저 K명의 선수를 선택하게 되었다. 쌍둥이들의 고질적 수비 불안을 해소하기 위해 다음 시즌에는 수비 능력 위주로 팀을 리빌딩할 예정이기 때문에, 이번 드래프트는 매우 중요하다.

N명의 선수들의 수비 위치와 수비 능력이 드래프트 신청자 목록에 주어진 순서대로 주어질 때, 각 수비 위치에서 가장 뛰어난 선수들의 능력의 총 합이 최대가 되도록 K명을 뽑는 프로그램을 작성하라. 단, 드래프트가 불가능한 경우는 없다고 가정한다.