def solve(string):

    n, k, *td = list(map(int, string.split()))

    td = sorted([(t, d) for t, d in zip(td[::2], td[1::2])], key=lambda x: x[1], reverse=True)

    max_variety = len(set([c[0] for c in td]))

    choice = td[:k]

    count = [0] * n

    for _c in choice:

        count[_c[0] - 1] += 1

    variety = set([c[0] for c in choice])

    ans = [len(variety)**2 + sum([c[1] for c in choice])]

    i_remove, i_append = k - 1, k

    while len(variety) < min(max_variety, k):

        while td[i_append][0] in variety:

            i_append += 1

        while count[td[i_remove][0] - 1] == 1:

            i_remove -= 1

        variety.add(td[i_append][0])

        count[td[i_remove][0] - 1] -= 1

        ans.append(ans[-1] - td[i_remove][1] + td[i_append][1] + 2 * len(variety) - 1)

        i_remove -= 1

        i_append += 1

    return str(max(ans))





if __name__ == '__main__':

    n, m = list(map(int, input().split()))

    print((solve('{} {}\n'.format(n, m) + '\n'.join([eval(input()) for _ in range(n)]))))

def solve(string):

    n, k, *td = list(map(int, string.split()))

    td = sorted([(t, d) for t, d in zip(td[::2], td[1::2])], key=lambda x: x[1], reverse=True)

    max_variety = len(set([c[0] for c in td]))

    choice = td[:k]

    r = []

    variety = set([])

    base = 0

    for _c in choice:

        base += _c[1]

        if _c[0] in variety:

            r.append(_c[1])

        else:

            variety.add(_c[0])

    base += len(variety)**2

    i = k

    ans = [base]

    while len(variety) < min(max_variety, k):

        while td[i][0] in variety:

            i += 1

        variety.add(td[i][0])

        ans.append(ans[-1] - r.pop() + td[i][1] + 2 * len(variety) - 1)

    return str(max(ans))





if __name__ == '__main__':

    n, m = list(map(int, input().split()))

    print((solve('{} {}\n'.format(n, m) + '\n'.join([eval(input()) for _ in range(n)]))))

def solve(string):
    n, k, *td = list(map(int, string.split()))
    td = sorted(
        [(t, d) for t, d in zip(td[::2], td[1::2])], key=lambda x: x[1], reverse=True
    )
    max_variety = len(set([c[0] for c in td]))
    choice = td[:k]
    count = [0] * n
    for _c in choice:
        count[_c[0] - 1] += 1
    variety = set([c[0] for c in choice])
    ans = [len(variety) ** 2 + sum([c[1] for c in choice])]
    i_remove, i_append = k - 1, k
    while len(variety) < min(max_variety, k):
        while td[i_append][0] in variety:
            i_append += 1
        while count[td[i_remove][0] - 1] == 1:
            i_remove -= 1
        variety.add(td[i_append][0])
        count[td[i_remove][0] - 1] -= 1
        ans.append(ans[-1] - td[i_remove][1] + td[i_append][1] + 2 * len(variety) - 1)
        i_remove -= 1
        i_append += 1
    return str(max(ans))


if __name__ == "__main__":
    n, m = list(map(int, input().split()))
    print(
        (solve("{} {}\n".format(n, m) + "\n".join([eval(input()) for _ in range(n)])))
    )

def solve(string):
    n, k, *td = list(map(int, string.split()))
    td = sorted(
        [(t, d) for t, d in zip(td[::2], td[1::2])], key=lambda x: x[1], reverse=True
    )
    max_variety = len(set([c[0] for c in td]))
    choice = td[:k]
    r = []
    variety = set([])
    base = 0
    for _c in choice:
        base += _c[1]
        if _c[0] in variety:
            r.append(_c[1])
        else:
            variety.add(_c[0])
    base += len(variety) ** 2
    i = k
    ans = [base]
    while len(variety) < min(max_variety, k):
        while td[i][0] in variety:
            i += 1
        variety.add(td[i][0])
        ans.append(ans[-1] - r.pop() + td[i][1] + 2 * len(variety) - 1)
    return str(max(ans))


if __name__ == "__main__":
    n, m = list(map(int, input().split()))
    print(
        (solve("{} {}\n".format(n, m) + "\n".join([eval(input()) for _ in range(n)])))
    )

-    count = [0] * n +    r = [] +    variety = set([]) +    base = 0 -        count[_c[0] - 1] += 1 -    variety = set([c[0] for c in choice]) -    ans = [len(variety) ** 2 + sum([c[1] for c in choice])] -    i_remove, i_append = k - 1, k +        base += _c[1] +        if _c[0] in variety: +            r.append(_c[1]) +        else: +            variety.add(_c[0]) +    base += len(variety) ** 2 +    i = k +    ans = [base] -        while td[i_append][0] in variety: -            i_append += 1 -        while count[td[i_remove][0] - 1] == 1: -            i_remove -= 1 -        variety.add(td[i_append][0]) -        count[td[i_remove][0] - 1] -= 1 -        ans.append(ans[-1] - td[i_remove][1] + td[i_append][1] + 2 * len(variety) - 1) -        i_remove -= 1 -        i_append += 1 +        while td[i][0] in variety: +            i += 1 +        variety.add(td[i][0]) +        ans.append(ans[-1] - r.pop() + td[i][1] + 2 * len(variety) - 1)