import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] = [long(input_raw[0]), long(input_raw[1])]
    sushi = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [t, d] = [long(input_raw[0]), long(input_raw[1])]
        sushi.append((d, t))

    sushi.sort(reverse=True)

    already_eat = set([])
    max_score = 0L
    count = 0
    not_eat_list = deque([])
    eat_list = deque([])
    for i in range(N):
        if sushi[i][1] not in already_eat:
            already_eat.add(sushi[i][1])
            max_score += sushi[i][0]
            eat_list.append(i)
        else:
            not_eat_list.append(i)

        if len(already_eat) == K:
            break
    count = len(already_eat)

    if count < K:
        while 1:
            if count >= K :
                break
            if len(not_eat_list) <= 0:
                break
            i =not_eat_list.popleft()
            eat_list.appendleft(i)
            max_score += sushi[i][0]
            already_eat.add(sushi[i][1])
            count += 1



    now_kind = len(already_eat)
    max_score += now_kind * now_kind
    now_score = max_score
    for new_idx in not_eat_list:
        if len(eat_list) == 0 :
            break
        eated_idx = eat_list.pop()
        already_eat.remove(sushi[eated_idx][1])
        already_eat.add(sushi[new_idx][1])

        new_kind = len(already_eat)
        now_score =  now_score - (now_kind * now_kind) + (new_kind *new_kind) - sushi[eated_idx][0] + sushi[new_idx][0]
        now_kind = new_kind
        max_score =max(max_score, now_score)


    print max_score




if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] = [long(input_raw[0]), long(input_raw[1])]
    sushi = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [t, d] = [long(input_raw[0]), long(input_raw[1])]
        sushi.append((d, t))

    sushi.sort(reverse=True)

    already_eat = set([])
    max_score = 0L
    count = 0
    not_eat_list = deque([])
    eat_list = deque([])
    for i in range(N):
        if sushi[i][1] not in already_eat:
            already_eat.add(sushi[i][1])
            max_score += sushi[i][0]
            eat_list.append(i)
        else:
            not_eat_list.append(i)

        if len(already_eat) == K:
            break
    count = len(already_eat)

    if count < K:
        while 1:
            if count >= K :
                break
            if len(not_eat_list) <= 0:
                break
            i =not_eat_list.popleft()
            eat_list.appendleft(i)
            max_score += sushi[i][0]
            already_eat.add(sushi[i][1])
            count += 1



    now_kind = len(already_eat)
    max_score += now_kind * now_kind
    now_score = max_score
    if len(not_eat_list) > 0:
        for new_idx in not_eat_list:
            if len(eat_list) == 0 :
                break
            eated_idx = eat_list.pop()
            if sushi[eated_idx][1] in already_eat:
                already_eat.remove(sushi[eated_idx][1])
            already_eat.add(sushi[new_idx][1])

            new_kind = len(already_eat)
            now_score =  now_score - (now_kind * now_kind) + (new_kind *new_kind) - sushi[eated_idx][0] + sushi[new_idx][0]
            now_kind = new_kind
            max_score =max(max_score, now_score)


    print max_score




if __name__ == '__main__':
    main()