Strange Draft

In 2150, the Kureyo Baseball Organization (hereafter KBO) approved the founding of its 100th team. Until then, players were picked one at a time in zigzag order based on the previous season's standings. But as the number of teams grew, the draft took too long, so KBO announced the following new draft rules.

• The $N$ players who applied for the draft are arranged in an arbitrary order that considers factors such as school, tournament results, and physical traits.
• Each player is described by an integer $P_i$ ($1 \le P_i \le 9$), their fixed defensive position, and an integer $A_i$, their defensive ability.
• When it is a team's turn, it picks $K$ consecutive players from the list and removes those players from the list.
• The $K$ selected players must include at least one player who can play each of the nine defensive positions.

You are the manager of the Twins, who finished last the previous season. To fix the team's chronic defensive weakness, you plan to rebuild around defensive ability next season, so this draft matters a lot. You make the first pick of $K$ players.

Given the defensive position and defensive ability of each of the $N$ players, listed in the order of the applicant list, write a program that picks $K$ players so that the sum of the best defensive ability at each position is maximized. The draft is always possible.

The input consists of $T$ test cases. The first line contains $T$.

The first line of each test case contains the number of applicants $N$ and the number of players $K$ that can be picked at once, separated by a space. ($9 \le K \le N \le 100\,000$) Then $N$ lines follow, each containing the defensive position $P_i$ ($1 \le P_i \le 9$) and defensive ability $A_i$ ($1 \le A_i \le 100$) of each player, separated by a space.

For each test case, print on its own line the maximum possible sum of the best defensive ability at each position that can be obtained in this draft.