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(list(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)

解()

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)

    dS = set()

    aPK = aP[:K]

    for t,d in aPK:

        dS.add(t)

    dSall = dS.copy()

    for t,d in aP[K:]:

        dSall.add(t)

    iSall = len(dSall)



    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)

解()

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(list(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)


解()

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,
    )
    dS = set()
    aPK = aP[:K]
    for t, d in aPK:
        dS.add(t)
    dSall = dS.copy()
    for t, d in aP[K:]:
        dSall.add(t)
    iSall = len(dSall)
    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)


解()

-    dP = {} -    for t, d in aP: -        if t in dP: -            dP[t].append(d) -        else: -            dP[t] = [d] -    iSall = len(list(dP.keys())) -    for x in aPK: -        dS.add(x[0]) +    for t, d in aPK: +        dS.add(t) +    dSall = dS.copy() +    for t, d in aP[K:]: +        dSall.add(t) +    iSall = len(dSall)