#!/usr/bin/env python3
import sys
from collections import defaultdict
from itertools import accumulate
import heapq

def solve(N: int, K: int, t: "List[int]", d: "List[int]"):
    sushi = defaultdict([])
    for i in range(N):
        sushi[t[i]].append(d[i])

    A = [] # 各ネタでいちばんおいしい寿司のおいしさ
    B = [] # 各ネタで2番目以降においしい寿司のおいしさリスト
    
    for v in sushi.values():
        v.sort(reverse=True)
        A.append(v[0])
        B.extend(v[1:])
    A.sort(reverse=True)
    B.sort(reverse=True)

    X = [0] + [x for x in accumulate(A)] # X[i]: Aからうまい順にi個選んだ時のおいしさ合計
    Y = [0] + [y for y in accumulate(B)] # Y[j]: Bからうまい順にj個選んだ時のおいしさ合計

    res = 0
    for i in range(1, min(len(X), K + 1)):
        if K - i < len(Y):
            res = max(res, X[i] + Y[K - i] + i ** 2) 
            # B[:i]に含まれるネタが、A[i+1:]に含まれていた場合、実際のネタ数はiより多いが、
            # その場合はiを多くとったほうが、より美味しさが大きくなる。
            # そのためres[i]が答えになりえないため、無視して良い。
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    t = [int()] * (N)  # type: "List[int]" 
    d = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        t[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, K, t, d)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import defaultdict
from itertools import accumulate
import heapq

def solve(N: int, K: int, t: "List[int]", d: "List[int]"):
    sushi = defaultdict(list)
    for i in range(N):
        sushi[t[i]].append(d[i])

    A = [] # 各ネタでいちばんおいしい寿司のおいしさ
    B = [] # 各ネタで2番目以降においしい寿司のおいしさリスト
    
    for v in sushi.values():
        v.sort(reverse=True)
        A.append(v[0])
        B.extend(v[1:])
    A.sort(reverse=True)
    B.sort(reverse=True)

    X = [0] + [x for x in accumulate(A)] # X[i]: Aからうまい順にi個選んだ時のおいしさ合計
    Y = [0] + [y for y in accumulate(B)] # Y[j]: Bからうまい順にj個選んだ時のおいしさ合計

    res = 0
    for i in range(1, min(len(X), K + 1)):
        if K - i < len(Y):
            res = max(res, X[i] + Y[K - i] + i ** 2) 
            # B[:i]に含まれるネタが、A[i+1:]に含まれていた場合、実際のネタ数はiより多いが、
            # その場合はiを多くとったほうが、より美味しさが大きくなる。
            # そのためres[i]が答えになりえないため、無視して良い。
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    t = [int()] * (N)  # type: "List[int]" 
    d = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        t[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, K, t, d)

if __name__ == '__main__':
    main()