28339번 - 이상한 드래프트

문제

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

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

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

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

입력

입력은 $T$개의 테스트 케이스로 구성된다. 입력의 첫 줄에는 $T$가 주어진다.

각 테스트 케이스 첫 줄에는 드래프트를 신청한 선수의 수 $N$과 드래프트로 한 번에 뽑을 수 있는 사람의 수 $K$가 공백으로 구분되어 주어진다. (9ドル ≤ K ≤ N ≤ 100,000円$) 그 후 $N$줄에 각 선수들의 수비 위치 $P_i$ (1ドル ≤ P_i ≤ 9$)와 수비 능력 $A_i$ (1ドル ≤ A_i ≤ 100$)가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스마다 한 줄에 하나씩 이번 드래프트에서 얻을 수 있는 각 수비 위치별로 가장 뛰어난 선수들의 수비 능력의 총 합의 최대값을 출력한다.

제한

힌트