이상한 드래프트

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

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

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

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

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

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

각 테스트 케이스마다 한 줄에 하나씩, 각 수비 위치별로 가장 뛰어난 선수들의 수비 능력의 합의 최댓값을 출력한다.