Buggy python submission (verdict: Time Limit Exceeded):
import sys
def 解():
    input = sys.stdin.readline
    N,K = [int(_) for _ in input().split()]
    aP = sorted([[int(_) for _ in input().split()] for _ in range(N)],key=lambda x:x[1],reverse=True)
    dP = {}
    for t,d in aP:
        if t in dP:
            dP[t].append(d)
        else:
            dP[t] = [d]
    iSall = len(dP.keys())
    dS = set()
    aPK = aP[:K]
    for x in aPK:
        dS.add(x[0])
    iSum = sum(x[1] for x in aPK)
    i種類 = len(dS)
    iTotal = iSum + i種類**2
    if iSall == len(dS): #種類を増やす余地がない
        print(iTotal)
        exit()
    else: #種類を増やす余地があるとき
        #とりあえず地図を作る
        dPK = {}
        for t,d in aPK:
            if t in dPK :
                dPK[t].append(d)
            else:
                dPK[t] = [d]
        vT = set()
        for nt,nd in aP[K:]:
            if nt not in dS:
                for i in range(K-1,-1,-1):
                    t,d = aPK[i]
                    if t not in vT:
                        dPK[t].sort()
                        vT.add(t)
                    aT = dPK[t]
                    if 1 < len(aT):
                        iNewTotal = iSum - d + nd  + (i種類+1)**2
                        if iTotal < iNewTotal:
                            iTotal = iNewTotal
                        del dPK[t][0]
                        dPK[nt]=[nd]
                        aPK[i]=[nt,nd]
                        i種類 += 1
                        iSum = iSum -d +nd
                        dS.add(nt)
                        break
        print(iTotal)
解()


Fixed submission:
import sys
def 解():
    input = sys.stdin.readline
    N,K = [int(_) for _ in input().split()]
    aP = sorted([[int(_) for _ in input().split()] for _ in range(N)],key=lambda x:x[1],reverse=True)
    dP = {}
    for t,d in aP:
        if t in dP:
            dP[t].append(d)
        else:
            dP[t] = [d]
    iSall = len(dP.keys())
    dS = set()
    aPK = aP[:K]
    for x in aPK:
        dS.add(x[0])
    iSum = sum(x[1] for x in aPK)
    i種類 = len(dS)
    iTotal = iSum + i種類**2
    if iSall == len(dS): #種類を増やす余地がない
        print(iTotal)
        exit()
    else: #種類を増やす余地があるとき
        #とりあえず地図を作る
        dPK = {}
        for t,d in aPK:
            if t in dPK :
                dPK[t].append(d)
            else:
                dPK[t] = [d]
        vT = set()
        j = K - 1
        for nt,nd in aP[K:]:
            if i種類 == iSall:
                break
            if nt not in dS:
                #for i in range(K-1,-1,-1):
                for i in range(j,-1,-1):
                    t,d = aPK[i]
                    if t not in vT:
                        dPK[t].sort()
                        vT.add(t)
                    aT = dPK[t]
                    if 1 < len(aT):
                        iNewTotal = iSum - d + nd  + (i種類+1)**2
                        if iTotal < iNewTotal:
                            iTotal = iNewTotal
                        del dPK[t][0]
                        dPK[nt]=[nd]
                        aPK[i]=[nt,nd]
                        i種類 += 1
                        iSum = iSum -d +nd
                        dS.add(nt)
                        break
                j=i-1
        print(iTotal)
解()