CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = sys.stdin.readline
N, K = list(map(int, input().split()))

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = list(map(int, input().split()))
    sushi_array.append([t - 1, d])
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
    sushi_count[sushi[0]] += 1

ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

now_kind += 1
while now_kind <= sushi_kind:
    for sushi in sushi_array[add_index:]:
        if sushi_count[sushi[0]] == 0:
            kiso += sushi[1]
            sushi_count[sushi[0]] = 1
            break
        add_index += 1
    else:
        break
    for sushi in sushi_array[remove_index::-1]:
        if sushi_count[sushi[0]] >= 1:
            kiso -= sushi[1]
            sushi_count[sushi[0]] -= 1
            break
        remove_index -= 1
    else:
        break
    # print(kiso + now_kind * now_kind)
    ans = max(ans, kiso + now_kind * now_kind)
    now_kind += 1

print(ans)

# Optimized solution
import sys
input = sys.stdin.readline
N, K = list(map(int, input().split()))

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = list(map(int, input().split()))
    sushi_array.append([t - 1, d])
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
can_remove = []
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
        sushi_count[sushi[0]] = 1
    else:
        can_remove.append(sushi[1])

    # print(sushi_count)
ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

# print(ans, kiso, now_kind)
now_kind += 1

for sushi in sushi_array[add_index:]:
    if len(can_remove) == 0 or now_kind > sushi_kind:
        break
    if sushi_count[sushi[0]] == 0:
        kiso += sushi[1] - can_remove.pop()
        sushi_count[sushi[0]] = 1
        # print(ans, kiso, now_kind)
        ans = max(ans, kiso + now_kind * now_kind)
        now_kind += 1
    else:
        continue

print(ans)
# Original solution
import sys
input = sys.stdin.readline
N, K = list(map(int, input().split()))

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = list(map(int, input().split()))
    sushi_array.append([t - 1, d])
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
can_remove = []
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
        sushi_count[sushi[0]] = 1
    else:
        can_remove.append(sushi[1])

    # print(sushi_count)
ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

# print(ans, kiso, now_kind)
now_kind += 1

for sushi in sushi_array[add_index:]:
    if len(can_remove) == 0 or now_kind > sushi_kind:
        break
    if sushi_count[sushi[0]] == 0:
        kiso += sushi[1] - can_remove.pop()
        sushi_count[sushi[0]] = 1
        # print(ans, kiso, now_kind)
        ans = max(ans, kiso + now_kind * now_kind)
        now_kind += 1
    else:
        continue

print(ans)

# Optimized solution
import sys
input = sys.stdin.readline
N, K = list(map(int, input().split()))

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = list(map(int, input().split()))
    sushi_array.append([t - 1, d])
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
    sushi_count[sushi[0]] += 1

ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

now_kind += 1
while now_kind <= sushi_kind:

    while add_index < N:
        sushi = sushi_array[add_index]
        # print(sushi)
        add_index += 1
        if sushi_count[sushi[0]] == 0:
            kiso += sushi[1]
            sushi_count[sushi[0]] = 1
            break

    else:
        break
    while remove_index >= 0:
        sushi = sushi_array[remove_index]
        # print(sushi)
        remove_index -= 1
        if sushi_count[sushi[0]] > 1:
            kiso -= sushi[1]
            sushi_count[sushi[0]] -= 1
            break
    else:
        break
    # print(ans,kiso,now_kind * now_kind)
    ans = max(ans, kiso + now_kind * now_kind)
    now_kind += 1

print(ans)
# Original solution
import collections
import heapq
import operator
import sys

input = sys.stdin.readline

ri = lambda: int(eval(input()))
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, k = ril()
ls = rils(n)
ls.sort(key=operator.itemgetter(1), reverse=True)
counter = collections.Counter()
ls0 = []
ls1 = []
base = 0
for i, (t, d) in enumerate(ls):
    if i < k:
        heapq.heappush(ls0, (d, t))
        counter[t] += 1
        base += d
    else:
        if t not in counter:
            heapq.heappush(ls1, (-d, t))

m = len(counter)
res = base + m**2

for i in range(k):
    ok = False
    while ls0:
        d, t = heapq.heappop(ls0)
        counter[t] -= 1
        if counter[t] > 0:
            base -= d
            ok = True
            break
    if not ok:
        break

    ok = False
    while ls1:
        d, t = heapq.heappop(ls1)
        if t not in counter:
            counter[t] += 1
            base += -d
            ok = True
            break
    if not ok:
        break

    res = max(res, base + (m + i + 1)**2)
print(res)

# Optimized solution
import collections
import heapq
import operator
import sys

input = sys.stdin.readline

ri = lambda: int(eval(input()))
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, k = ril()
ls = rils(n)
ls.sort(key=operator.itemgetter(1), reverse=True)
counter0 = collections.Counter()
counter1 = collections.Counter()
ls0 = []
ls1 = []
base = 0
for i, (t, d) in enumerate(ls):
    if i < k:
        if counter0[t] > 0:
            heapq.heappush(ls0, (d, t))
        counter0[t] += 1
        base += d
    else:
        if t not in counter0 and t not in counter1:
            heapq.heappush(ls1, (-d, t))
            counter1[t] += 1

m = len(counter0)
res = base + m**2

for _ in range(k):
    if len(ls0) == 0 or len(ls1) == 0:
        break
    d, _ = heapq.heappop(ls0)
    base -= d
    d, _ = heapq.heappop(ls1)
    base += -d
    m += 1
    res = max(res, base + m**2)
print(res)
# Original solution
import collections
import heapq
import operator
import sys

input = sys.stdin.readline

ri = lambda: int(eval(input()))
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, k = ril()
ls = rils(n)
ls.sort(key=operator.itemgetter(1), reverse=True)
counter0 = collections.Counter()
counter1 = collections.Counter()
ls0 = []
ls1 = []
base = 0
for i, (t, d) in enumerate(ls):
    if i < k:
        if counter0[t] > 0:
            heapq.heappush(ls0, (d, t))
        counter0[t] += 1
        base += d
    else:
        if t not in counter0 and t not in counter1:
            heapq.heappush(ls1, (-d, t))
            counter1[t] += 1

m = len(counter0)
res = base + m**2

for _ in range(k):
    if len(ls0) == 0 or len(ls1) == 0:
        break
    d, _ = heapq.heappop(ls0)
    base -= d
    d, _ = heapq.heappop(ls1)
    base += -d
    m += 1
    res = max(res, base + m**2)
print(res)

# Optimized solution
import heapq
import operator
import sys

input = sys.stdin.readline

ri = lambda: int(eval(input()))
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, k = ril()
ls = rils(n)
ls.sort(key=operator.itemgetter(1), reverse=True)
selected0 = set()
selected1 = set()
ls0 = []
ls1 = []
base = 0
for i, (t, d) in enumerate(ls):
    if i < k:
        if t in selected0:
            heapq.heappush(ls0, (d, t))
        selected0.add(t)
        base += d
    else:
        if t not in selected0 and t not in selected1:
            heapq.heappush(ls1, (-d, t))
            selected1.add(t)

m = len(selected0)
res = base + m**2

for _ in range(k):
    if len(ls0) == 0 or len(ls1) == 0:
        break
    d, _ = heapq.heappop(ls0)
    base -= d
    d, _ = heapq.heappop(ls1)
    base += -d
    m += 1
    res = max(res, base + m**2)
print(res)
# Original solution
import collections

n, k = list(map(int, input().split()))
h = []
for i in range(n):
    a, b = list(map(int, input().split()))
    h.append((a,b))
h.sort(key=lambda x: -x[1])
fav=h[0:k]
tb={}
for t,d in sorted(h[k:], key=lambda x: (-x[0], -x[1])):
    tb[t] = tb.get(t, []) + [d]
alt = []
for t,ds in list(tb.items()):
    alt.append((t,max(ds)))
alt.sort(key=lambda x: -x[1])

# print("h: ",h)
# print("fav: ",fav)
# print("alt: ",alt)


var = len(set([x[0] for x in fav]))

bestscore = var**2 + sum([x[1] for x in fav])

while(len(alt) > 0):
    c = collections.Counter([x[0] for x in fav])
    temp = sorted([x for x in fav if c[x[0]] > 1], key=lambda x: -x[1])
    if(len(temp) == 0):
        break
    while(len(alt) > 0):
        t1, d1 = alt.pop(0)
        if(c[t1] == 0):
            break
    if(c[t1] != 0):
        break
    t2, d2 = temp[-1]


    fav.remove((t2,d2))
    fav.append((t1, d1))
    var += 1

    bestscore = max(bestscore, var**2 + sum([x[1] for x in fav]))

    # print("fav: ",fav)
    # print("alt: ",alt)

print(bestscore)

# Optimized solution
n, k = list(map(int, input().split()))
h = []
for i in range(n):
    t, d = list(map(int, input().split()))
    h.append((t,d))
h.sort(key=lambda x: -x[1])

taste = 0
typen = 0
typecnt = {}
bad = []


for i in range(k):
    typecnt[h[i][0]] = typecnt.get(h[i][0], 0) + 1
    if(typecnt[h[i][0]] == 1):
        typen += 1
    else:
        bad.append(h[i][1])
    taste += h[i][1]

# print(h)
# print(typecnt)
# print(bad)

ans = taste + typen**2

for i in range(k, n):
    if(len(bad) == 0):
        break
    cnt = typecnt.get(h[i][0], 0)
    if(cnt != 0):
        continue
    else:
        typecnt[h[i][0]] = cnt + 1
    typen += 1
    taste -= bad.pop()
    taste += h[i][1]
    ans = max(ans, taste + typen**2)

print(ans)
# Original solution
import itertools

N, K = list(map(int, input().split()))
menu = {}

for i in range(N):
    t, d = list(map(int, input().split()))
    menu[i] = (t, d)

def manzoku(s):
    manzoku = sum([menu[i][1] for i in s]) + len(set([menu[i][0] for i in s]))**2
    return manzoku

#K sushi
shushi = itertools.combinations(menu, K)
print((max([manzoku(c) for c in shushi])))


# Optimized solution
N, K = list(map(int, input().split()))
menu_ = []

for i in range(N):
    t, d = list(map(int, input().split()))
    menu_.append((t, d))

menu = sorted(menu_, key = lambda x:x[1], reverse=True)
neta = set()
duplicates = []

for m in menu[:K]:
    if m[0] in neta:
        duplicates.append(m[1])
    else:
        neta.add(m[0])

p = sum([d for (t, d) in menu[:K]]) + len(neta)**2
ans = p

for m in menu[K:]:
    if m[0] not in neta and duplicates:
        neta.add(m[0])
        duplicate = duplicates.pop()
        
        p += (m[1] - duplicate) + 2 * len(neta) - 1 
        #print(ans, p)
        ans = max(ans, p)

print(ans)
# Original solution
N, K = list(map(int, input().split()))
nums = [[] for i in range(N)]
for i in range(N):
    t, d = list(map(int, input().split()))
    t -= 1
    nums[t].append(d)
maxs = []
rest = []
for i in range(N):
    nums[i].sort(reverse=True)
    if len(nums[i]) > 0:
        maxs.append(nums[i][0])
        rest = rest + nums[i][1:]
maxs.sort(reverse=True)
if len(maxs) > K:
    maxs = maxs[:K]
    rest = rest + maxs[K:]
rest.sort(reverse=True)
other = []
idx = 0
while len(maxs)+len(other) < K:
    other.append(rest[idx])
    idx += 1
rest = rest[idx:]

types = len(maxs)
for i,r in enumerate(rest):
    diff = types*types - pow(types-1, 2)
    if diff < r-maxs[len(maxs)-1-i]:
        maxs[len(maxs)-1-i] = r
        types -= 1
    else:
        break
ans = types*types
for num in maxs:
    ans += num
for num in other:
    ans += num
print(ans)


# Optimized solution
import sys
input = sys.stdin.readline

N, K = list(map(int, input().split()))
nums = [[] for i in range(N)]
for i in range(N):
    t, d = list(map(int, input().split()))
    t -= 1
    nums[t].append(d)
maxs = []
rest = []
for i in range(N):
    nums[i].sort(reverse=True)
    if len(nums[i]) > 0:
        maxs.append(nums[i][0])
        for n in nums[i][1:]:
            rest.append(n)
        #rest = rest + nums[i][1:]
maxs.sort(reverse=True)
if len(maxs) > K:
    maxs = maxs[:K]
    for n in maxs[K:]:
        rest.append(n)
    #rest = rest + maxs[K:]
rest.sort(reverse=True)
other = []
idx = 0
while len(maxs)+len(other) < K:
    other.append(rest[idx])
    idx += 1
rest = rest[idx:]

types = len(maxs)
#print(maxs)
#print(rest)
for i,r in enumerate(rest):
    diff = types*types - pow(types-1, 2)
    if diff < r-maxs[len(maxs)-1-i]:
        maxs[len(maxs)-1-i] = r
        types -= 1
    else:
        break
ans = types*types
for num in maxs:
    ans += num
for num in other:
    ans += num
print(ans)
# Original solution
import heapq
n,k = list(map(int,input().split()))
L = []
for i in range(n):
    t,d = list(map(int,input().split()))
    L.append([d,t])
L.sort()
ans = []
cur = [0]*n
heap = []
var = 0
for i in range(k):
    if cur[L[n-i-1][1]-1] == 0:
        ans.append(L[n-i-1][0])
        cur[L[n-i-1][1]-1] = 1
        var += 1
    else:
        heapq.heappush(heap, L[n-i-1])
temp = 0
for i in range(len(ans)):
    temp += ans[i]
for i in range(len(heap)):
    temp += heap[i][0]
temp += var**2
now = temp
for i in range(n-k):
    if len(heap) != 0:
        a = heapq.heappop(heap)
        if cur[L[n-k-i-1][1]-1] == 0:
            ans.append(L[n-k-i-1][0])
            cur[L[n-k-i-1][1]-1] = 1
            now -= var**2
            now -= a[0]
            var += 1
            now += var**2
            now += L[n-k-i-1][0]
            temp = max(temp, now)
        else:
            heapq.heappush(heap, a)
print(temp)


# Optimized solution
import heapq
n,k = list(map(int,input().split()))
L = []
for i in range(n):
    t,d = list(map(int,input().split()))
    L.append([d,t])
L.sort()
ans = []
cur = [0]*n
heap = []
var = 0
for i in range(k):
    if cur[L[n-i-1][1]-1] == 0:
        ans.append(L[n-i-1][0])
        cur[L[n-i-1][1]-1] = 1
        var += 1
    else:
        heapq.heappush(heap, L[n-i-1])
temp = 0
for i in range(len(ans)):
    temp += ans[i]
for i in range(len(heap)):
    temp += heap[i][0]
temp += var**2
now = temp
for i in range(n-k):
    if len(heap) != 0:
        a = heapq.heappop(heap)
        if cur[L[n-k-i-1][1]-1] == 0:
            cur[L[n-k-i-1][1]-1] = 1
            now -= var**2
            now -= a[0]
            var += 1
            now += var**2
            now += L[n-k-i-1][0]
            temp = max(temp, now)
        else:
            heapq.heappush(heap, a)
print(temp)
# Original solution
import itertools
import heapq
N, K = [int(x) for x in input().split()]
orig_td = [tuple([int(x) for x in input().split()]) for _ in range(N)]
td = sorted(orig_td.copy(), key=lambda x: x[1], reverse=True)
INF = 10**9
# print(td)


def score(a):
    kiso = sum([x[1] for x in a])
    bonus = len(set([x[0] for x in a]))**2
    return kiso + bonus


first = []
second = []
kind = set()
for i in range(K):
    if td[i][0] not in kind:
        first.append(td[i])
        kind.add(td[i][0])
    else:
        second.append(td[i])

best_ans = sum([x[1] for x in first + second]) + len(first)**2

for k in range(K, N):
    if len(second) == 0:
        break
    if td[k][0] in kind:
        continue

    a = second.pop(-1)
    kind.add(td[k][0])
    first.append(td[k])
    ans = sum([x[1] for x in first + second]) + len(first)**2
    # print(first, second, ans)
    if best_ans < ans:
        best_ans = ans
print(best_ans)


# Optimized solution
N, K = [int(x) for x in input().split()]
td = sorted([[int(x) for x in input().split()] for _ in range(N)],
            key=lambda x: x[1], reverse=True)
INF = 10**9
# print(td)

first = []
second = []
kind = set()
for i in range(K):
    if td[i][0] not in kind:
        first.append(td[i])
        kind.add(td[i][0])
    else:
        second.append(td[i])

yummy = sum([x[1] for x in first + second])
best_ans = yummy + len(kind)**2

for k in range(K, N):
    if len(second) == 0:
        break
    if td[k][0] in kind:
        continue

    a = second.pop(-1)
    yummy -= a[1]
    kind.add(td[k][0])
    first.append(td[k])
    yummy += td[k][1]
    ans = yummy + len(kind)**2
    # print(first, second, ans)
    if best_ans < ans:
        best_ans = ans
print(best_ans)
# Original solution
from heapq import heappop, heappush

n, nTake = list(map(int, input().split()))
a = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: (-x[1], x[0]))

totalTaste = 0
same = []
types = set()
for i in range(nTake):
    type, taste = a[i]
    totalTaste += taste
    if type not in types:
        types.add(type)
    else:
        heappush(same, taste)

rem = []
typesRem = set()
for i in range(nTake, n):
    type, taste = a[i]
    if type not in types and type not in typesRem:
        typesRem.add(type)
        heappush(rem, -taste)

ret = totalTaste + len(types) ** 2
curTotal = totalTaste
add = 1
while same and rem:
    worst = heappop(same)
    best = heappop(rem)
    curTotal = curTotal - worst - best
    ret = max(ret, curTotal + (len(types) + add) ** 2)
    add += 1
print(ret)

# Optimized solution
n, nTake = list(map(int, input().split()))
a = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[1])

totalTaste = 0
same = []
types = set()
for i in range(nTake):
    type, taste = a[i]
    totalTaste += taste
    if type not in types:
        types.add(type)
    else:
        same.append(taste)

rem = []
typesRem = set()
for i in range(nTake, n):
    type, taste = a[i]
    if type not in types and type not in typesRem:
        typesRem.add(type)
        rem.append(taste)

same.sort()
rem.sort(key=lambda x: -x)
ret = totalTaste + len(types) ** 2
curTotal = totalTaste
for i in range(min(len(same), len(rem))):
    curTotal = curTotal - same[i] + rem[i]
    ret = max(ret, curTotal + (len(types) + i + 1) ** 2)
print(ret)
# Original solution
N, K = list(map(int, input().split()))

list0 = []
list1 = []
set1 = set()

td = []
for i in range(N):
    t, d = list(map(int, input().split()))
    td.append((t, d))

td.sort(key=lambda x: (x[0], -x[1]))

for t, d in td:
    if t in set1:
        list0.append(d)
    else:
        set1.add(t)
        list1.append(d)

list0.sort(reverse=True)
list1.sort(reverse=True)

various = min(K, len(list1))
selected0 = []
selected1 = []
for i in range(various):
    selected1.append(list1.pop(0))
if K > various:
    for i in range(K - various):
        selected0.append(list0.pop(0))


ans = sum(selected0) + sum(selected1) + various ** 2

mn = selected1[-1]
while list0 and list0[0] > mn:
    mn = selected1.pop(-1)
    selected0.append(list0.pop(0))
    various -= 1
    tmp = sum(selected0) + sum(selected1) + various ** 2
    if tmp <= ans:
        break
    ans = tmp

print(ans)


# Optimized solution
N, K = list(map(int, input().split()))

list0 = []
list1 = []
set1 = set()

td = []
for i in range(N):
    t, d = list(map(int, input().split()))
    td.append((t, d))

td.sort(key=lambda x: (x[0], -x[1]))

for t, d in td:
    if t in set1:
        list0.append(d)
    else:
        set1.add(t)
        list1.append(d)

list0.sort(reverse=True)
list1.sort(reverse=True)

various = min(K, len(list1))
selected0 = []
selected1 = []
for i in range(various):
    selected1.append(list1.pop(0))
if K > various:
    for i in range(K - various):
        selected0.append(list0.pop(0))


ans = sum(selected0) + sum(selected1) + various ** 2

mn = selected1[-1]
sum0 = sum(selected0)
sum1 = sum(selected1)
while list0 and list0[0] > mn:
    sum0 += list0.pop(0)
    sum1 -= selected1.pop(-1)
    various -= 1
    tmp = sum0 + sum1 + various ** 2
    if tmp <= ans:
        break
    ans = tmp

print(ans)
# Original solution
from collections import deque
n,k=list(map(int,input().split()))
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kinds=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kinds:
        kinds[td[i][0]].append(td[i][1])
    else:
        kinds[td[i][0]]=deque()
        kinds[td[i][0]].append(td[i][1])
l=len(kinds)
ans+=(l**2)

ans_=ans
for i in range(k,n):
    if td[i][0] not in kinds:
        mi=[1000000000,1000000000]
        for j in kinds:
            if len(kinds[j])>1:
                if mi[1]>kinds[j][-1]:
                    mi=[j,kinds[j][-1]]
        if mi==[1000000000,1000000000]:
            break
        else:
            ans=ans-l**2+(l+1)**2-mi[1]+td[i][1]
            kinds[mi[0]].pop()
            kinds[td[i][0]]=deque()
            kinds[td[i][0]].append(td[i][1])
            ans_=max(ans,ans_)
            l+=1

print(ans_)


# Optimized solution
n,k=list(map(int,input().split()))
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[mi[0]]-=1
                now-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)