一个“纯职业小组”定义为由 3 名同职业的士兵组成的队伍。

判断是否有解

遍历所有职业计算出最大队伍数量。

res = 0
for i in range(n):
    res += b[i] // 3
if res < k:
    print(-1)
    continue

有解

假设有：

假设 $k = 1$，如果想要多选一些人，那就是不希望太快凑出队伍，可以先选 $1$ 个 $a$，$2$ 个 $b$，$2$ 个 $c$，$2$ 个 $d$（选两个是因为如果三个，就凑成一支队伍了）。

这时：

已选 $7$ 人，接下来再选一个 $c$ 或者 $d$，即可凑成一支队伍。

根据上述分析，以及贪心思想，我们可以先将所有队伍取出 $2$ 个人，若队伍为 $1$ 人则取 $1$ 人，此时不构成一支队伍。

好的，接下来我们要如何做？

先选出所有的 $<3$ 的人头，这些都是白送的 /doge。

• 如果 $k = 1$，那就只能再选一个人，就成一个队伍了。
• 如果 $k > 1$，
• 如果有一个剩余 $\leq 3$ 个人的职业，那就先选 $1$ 个构成一支队伍，然后可以白嫖两个 /doge，因为再选两个，是不会构成一支队伍的，但是可以导致我们的答案更优。
• 如果有一个剩余 $\leq 2$ 个人的职业，那就先选 $1$ 个构成一支队伍，然后可以白嫖一个，因为再选一个，是不会构成一支队伍的，但是可以导致我们的答案更优。
• 如果有一个剩余 $\leq 1$ 个人的职业，那就选 $1$ 个构成一支队伍。

很显然，根据贪心的策略，有 $3$ 选 $3$，无 $3$ 选 $2$，无 $2$ 选 $1$。

那么如何处理 $k = 1$ 的情况，我们可以直接将读入的 $k$ 直接 $k -= 1$，$res += 1$，因为，如果有解的情况下，我们刚开始白嫖的时候，一定会白嫖到最少一种职业有 $2$ 个人，那么再选一个就会导致直接构成一支队伍，但是 $res$ 只有 $+1$，和前面的贪心分析不合，故可以特殊处理。

T = int(input())
for _ in range(T):
    n, k = map(int, input().split())
    h = {}
    for i in range(n):
        a, b = map(int, input().split())
        if a not in h:
            h[a] = 0
        h[a] += b

    b = []
    for x in h:
        b.append(h[x])

    n = len(b)

    cnt = 0
    res = 0
    for i in range(n):
        cnt += b[i] // 3
        u = min(b[i], 2)
        b[i] -= u
        res += u

    if cnt < k:
        print(-1)
        continue

    c1, c2, c3 = 0, 0, 0
    for x in b:
        c3 += x // 3
        x %= 3
        if x == 1:
            c1 += 1
        elif x == 2:
            c2 += 1

    k -= 1
    res += 1

    v = min(k, c3)
    k -= v
    c3 -= v
    res += v * 3

    v = min(k, c2)
    k -= v
    c2 -= v
    res += v * 2

    v = min(k, c1)
    k -= v
    c1 -= v
    res += v * 1

    print(res)