分类讨论问题

#由于输入过大，使用常规的input会超时

import sys

data=sys.stdin.read().split()

T=int(data[0])

p=1

N=int(2e5+5)

while T>0:

    T-=1

    n,k=int(data[p]),int(data[p+1])

    p+=2

    lt=[0]*N

    for i in range(n):

        x,y=int(data[p]),int(data[p+1])

        p+=2

        lt[x]+=y

    q=0

    l1=0

    l2=0

    bg=0

    t=0

    ans=0

    for i in range(N):

        y=lt[i]

        if y>=3:

            bg+=1

            q+=y//3

            if y%3==1:

                l1+=1

            elif y%3==2:

                l2+=1

            t+=y//3-1

        else:

            ans+=y

    if q<k:

        print(-1)

    else:

        if k<=t+1:

            print(ans+(k-1)*3+2*bg+1)

        elif k>t+1 and k<=t+1+l2:

            u=k-(t+1)

            print(ans+(k-1)*3+2*(bg-u)+2*u+1)

        elif k>t+1+l2 and k<=t+1+l2+l1:

            u=k-(t+1+l2)

            print(ans+(k-1)*3+2*(bg-l2-u)+2*l2+u+1)

        else:

            u=k-(t+1+l2+l1)

            print(ans+(k-1)*3+2*(bg-l2-l1-u)+2*l2+l1+1)