from heapq import heappush as push

from heapq import heappop as pop

def solve():

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

  group_num = 10

  

  book_map = [[] for i in range(group_num)]

  acc_map = [[0] for i in range(group_num)]



  for i in range(n):

    c,g = list(map(int,input().split()))

    push(book_map[g - 1], -c)



  for i in range(group_num):

    bmi = book_map[i]

    append = acc_map[i].append

    acc = 0

    for j in range(len(bmi)):

      acc += (pop(bmi) - j * 2)

      append(acc)

  

  dp = [[0] * (k + 1) for i in range(group_num + 1)]

  for y in range(1,k + 1):

    for x in range(1,group_num + 1):

      mp = acc_map[x - 1]

      be = dp[x - 1]

      for z in range(min(y + 1, len(mp))):

        v1 = be[y - z]

        v2 = mp[z]

        if dp[x][y] > v1 + v2:

          dp[x][y] = v1 + v2

  

  print((-dp[group_num][k]))

solve()



def solve():

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

  group_num = 10

  

  book_map = [[] for i in range(group_num)]

  acc_map = [[0] for i in range(group_num)]



  for i in range(n):

    c,g = list(map(int,input().split()))

    book_map[g - 1].append(c)



  for i in range(group_num):

    bmi = book_map[i]

    bmi.sort(reverse=True)

    append = acc_map[i].append

    acc = 0

    for j in range(len(bmi)):

      acc += (bmi[j] + j * 2)

      append(acc)

  

  dp = [[0] * (k + 1) for i in range(group_num + 1)]

  for y in range(1,k + 1):

    for x in range(1,group_num + 1):

      mp = acc_map[x - 1]

      be = dp[x - 1]

      dp[x][y] = max([be[y - z] + mp[z] for z in range(min(y + 1, len(mp)))])

  

  print((dp[group_num][k]))

solve()



from heapq import heappush as push
from heapq import heappop as pop


def solve():
    n, k = list(map(int, input().split()))
    group_num = 10
    book_map = [[] for i in range(group_num)]
    acc_map = [[0] for i in range(group_num)]
    for i in range(n):
        c, g = list(map(int, input().split()))
        push(book_map[g - 1], -c)
    for i in range(group_num):
        bmi = book_map[i]
        append = acc_map[i].append
        acc = 0
        for j in range(len(bmi)):
            acc += pop(bmi) - j * 2
            append(acc)
    dp = [[0] * (k + 1) for i in range(group_num + 1)]
    for y in range(1, k + 1):
        for x in range(1, group_num + 1):
            mp = acc_map[x - 1]
            be = dp[x - 1]
            for z in range(min(y + 1, len(mp))):
                v1 = be[y - z]
                v2 = mp[z]
                if dp[x][y] > v1 + v2:
                    dp[x][y] = v1 + v2
    print((-dp[group_num][k]))


solve()

def solve():
    n, k = list(map(int, input().split()))
    group_num = 10
    book_map = [[] for i in range(group_num)]
    acc_map = [[0] for i in range(group_num)]
    for i in range(n):
        c, g = list(map(int, input().split()))
        book_map[g - 1].append(c)
    for i in range(group_num):
        bmi = book_map[i]
        bmi.sort(reverse=True)
        append = acc_map[i].append
        acc = 0
        for j in range(len(bmi)):
            acc += bmi[j] + j * 2
            append(acc)
    dp = [[0] * (k + 1) for i in range(group_num + 1)]
    for y in range(1, k + 1):
        for x in range(1, group_num + 1):
            mp = acc_map[x - 1]
            be = dp[x - 1]
            dp[x][y] = max([be[y - z] + mp[z] for z in range(min(y + 1, len(mp)))])
    print((dp[group_num][k]))


solve()

-from heapq import heappush as push -from heapq import heappop as pop - - -        push(book_map[g - 1], -c) +        book_map[g - 1].append(c) +        bmi.sort(reverse=True) -            acc += pop(bmi) - j * 2 +            acc += bmi[j] + j * 2 -            for z in range(min(y + 1, len(mp))): -                v1 = be[y - z] -                v2 = mp[z] -                if dp[x][y] > v1 + v2: -                    dp[x][y] = v1 + v2 -    print((-dp[group_num][k])) +            dp[x][y] = max([be[y - z] + mp[z] for z in range(min(y + 1, len(mp)))]) +    print((dp[group_num][k]))