Buggy python submission (verdict: Time Limit Exceeded):
def seek_dup(s):
    t_list = [t for (t, d) in s]
    #d_list = [d for (t, d) in s]
 
    for t, d in reversed(s):
        if t_list.count(t) > 1:
            return (t, d)
        else:
            continue
        
    return None
 
N, K = map(int, input().split())
menu_ = []
 
for i in range(N):
    t, d = map(int, input().split())
    menu_.append((t, d))
 
menu = sorted(menu_, key = lambda x:x[1], reverse=True)
p = sum([d for (t, d) in menu[:K]]) + len(set([t for (t, d) in menu[:K]]))**2
 
selected_menu = menu[:K]
t_list = [t for (t, d) in selected_menu]
d_list = [d for (t, d) in selected_menu]
ans = p
for m in menu[K:]:
    
    if m[0] not in t_list:
        d = seek_dup(selected_menu)
        if d == None:
            continue
        
        selected_menu.remove(d)
        selected_menu.append(m)
        t_list = [t for (t, d) in selected_menu]
        d_list = [d for (t, d) in selected_menu]        
        
    
        p += (m[1] - d[1]) + 2 * len(set(t_list)) - 1 
        #print(ans, p)
        ans = max(ans, p)
 
print(ans) 

Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Runtime Error):
def seek_dup(s):
    t_list = [t for (t, d) in s]
    #d_list = [d for (t, d) in s]
 
    for t, d in reversed(s):
        if t_list.count(t) > 1:
            return (t, d)
        else:
            continue
        
    return None
 
N, K = map(int, input().split())
menu_ = []
 
for i in range(N):
    t, d = map(int, input().split())
    menu_.append((t, d))
 
menu = sorted(menu_, key = lambda x:x[1], reverse=True)
p = sum([d for (t, d) in menu[:K]]) + len(set([t for (t, d) in menu[:K]]))**2
 
selected_menu = menu[:K]
#t_list = [t for (t, d) in selected_menu]
#d_list = [d for (t, d) in selected_menu]
ans = p
for m in menu[K:]:
    t_list = [t for (t, d) in selected_menu]
    d_list = [d for (t, d) in selected_menu]
    
    if m[0] not in t_list and len(set(t_list)) == len(t_list):
        d = seek_dup(selected_menu)
        if d == None:
            continue
        
        selected_menu.remove(d)
        selected_menu.append(m)
    
    p += (m[1] - d[1]) + 2 * len(set(t_list)) - 1 
    #print(ans, p)
    ans = max(ans, p)
 
print(ans) 

Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Runtime Error):
def seek_dup(s):
    t_list = [t for (t, d) in s]
    #d_list = [d for (t, d) in s]
 
    for t, d in reversed(s):
        if t_list.count(t) > 1:
            return (t, d)
        else:
            continue
        
    return None
 
N, K = map(int, input().split())
menu_ = []
 
for i in range(N):
    t, d = map(int, input().split())
    menu_.append((t, d))
 
menu = sorted(menu_, key = lambda x:x[1], reverse=True)
p = sum([d for (t, d) in menu[:K]]) + len(set([t for (t, d) in menu[:K]]))**2
 
selected_menu = menu[:K]
#t_list = [t for (t, d) in selected_menu]
#d_list = [d for (t, d) in selected_menu]
ans = p
for m in menu[K:]:
    t_list = [t for (t, d) in selected_menu]
    d_list = [d for (t, d) in selected_menu]
    
    if m[0] not in t_list:
        d = seek_dup(selected_menu)
        if d == None:
            continue
        
        selected_menu.remove(d)
        selected_menu.append(m)
    
    p += (m[1] - d[1]) + 2 * len(set(t_list)) - 1 
    #print(ans, p)
    ans = max(ans, p)
 
print(ans) 

Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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:
        neta.add(m[0])
        duplicate = duplicates.pop()
        
        p += (m[1] - duplicate) + 2 * len(neta) - 1 
        #print(ans, p)
        ans = max(ans, p)

print(ans) 

Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Runtime Error):

N, K = map(int, input().split())
menu = []

for i in range(N):
    t, d = 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:
        neta.add(m[0])
        duplicate = duplicates.pop()
        
        p += (m[1] - duplicate) + 2 * len(neta) + 1 
        #print(ans, p)
        ans = max(ans, p)

print(ans)  

Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
menu = []

for i in range(N):
    t, d = 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:
        neta.add(m[0])
        duplicate = duplicates.pop()
        
        p += (m[1] - duplicate) + 2 * len(neta) - 1 
        #print(ans, p)
        ans = max(ans, p)

print(ans)   

Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
menu = []

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

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:
        neta.add(m[0])
        duplicate = duplicates.pop()
        
        p += (m[1] - duplicate) + 2 * len(neta) - 1 
        #print(ans, p)
        ans = max(ans, p)

print(ans) 

Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
menu = []

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

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:
        neta.add(m[0])
        duplicate = duplicates.pop()
        
        p += (m[1] - duplicate) + 2 * len(neta) + 1 
        #print(ans, p)
        ans = max(ans, p)

print(ans) 

Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
menu = []

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

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:
        neta.add(m[0])
        duplicate = duplicates.pop()
        
        p += (m[1] - duplicate) + 2 * len(neta) - 1 
        #print(ans, p)
        ans = max(ans, p)

print(ans)  

Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Runtime Error):
def seek_dup(s):
    t_list = [t for (t, d) in s]
    #d_list = [d for (t, d) in s]

    for t, d in reversed(s):
        if t_list.count(t) > 1:
            return (t, d)
        else:
            continue
        
    return None

N, K = map(int, input().split())
menu = []

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

sorted(menu, key = lambda x:x[1], reverse=True)
ans = sum([d for (t, d) in menu[:K]]) + len(set([t for (t, d) in menu[:K]]))**2

selected_menu = menu[:K]
#t_list = [t for (t, d) in selected_menu]
#d_list = [d for (t, d) in selected_menu]
p = ans
for m in menu[K:]:
    t_list = [t for (t, d) in selected_menu]
    d_list = [d for (t, d) in selected_menu]
    
    if m[0] not in t_list:
        d = seek_dup(selected_menu)
        if d == None:
            continue
        
        selected_menu.remove(d)
        selected_menu.append(m)
    
    p += (m[1] - d[1]) + 2 * len(set(t_list)) - 1 
    #print(ans, p)
    ans = max(ans, p)

print(ans) 

Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Runtime Error):

def seek_dup(s):
    t_list = [t for (t, d) in s]
    #d_list = [d for (t, d) in s]

    for t, d in reversed(s):
        if t_list.count(t) > 1:
            return (t, d)
        else:
            continue
        
    return None

N, K = map(int, input().split())
menu = []

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

sorted(menu, key = lambda x:x[1], reverse=True)
ans = sum([d for (t, d) in menu[:K]]) + len(set([t for (t, d) in menu[:K]]))**2

selected_menu = menu[:K]
#t_list = [t for (t, d) in selected_menu]
#d_list = [d for (t, d) in selected_menu]
p = ans
for m in menu[K:]:
    t_list = [t for (t, d) in selected_menu]
    d_list = [d for (t, d) in selected_menu]
    
    if m[0] not in t_list:
        d = seek_dup(selected_menu)
        if d == None:
            continue
        
        #selected_menu.remove(d)
        #selected_menu.append(m)
    
    p += (m[1] - d[1]) + 2 * len(set(t_list)) + 1 
    #print(ans, p)
    ans = max(ans, p)

print(ans)    
    

Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Runtime Error):
def manzoku(s):
    return sum([d for (t, d) in s]) + len(set([t for (t, d) in s]))**2

N, K = map(int, input().split())
menu = []

for i in range(N):
    t, d = map(int, input().split())
    menu.append((t, d))
#print(menu)
    
#Sort with value d
sorted(menu, key = lambda x:x[1], reverse=True)
#print(menu)

menu_ = menu[:K]
#print(menu_)
#x = len(set([t for (t, d) in menu_]))
_menu = menu[K:]
#print(_menu)

#print(menu_)
ans = manzoku(menu_)
flg = True
for idx in range(K, N):
    for j in range(K):
        if [i for (i, v) in menu_].count(menu_[j][0]) > 1:
            del menu_[j]
            #print(menu_)
            for k in range(N-K):
                if _menu[k][0] not in [i for (i, v) in menu_]:
                    menu_.append(_menu[k])
                    #print(menu_)
                    del _menu[k]
                    #print(_menu)
                    flg = False
                    break
        if flg == False:
            break

    p = manzoku(menu_)
    #print(ans, p)
    ans = max(ans, p)

print(ans)    

Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Runtime Error):
def manzoku(s):
    return sum([d for (t, d) in s]) + len(set([t for (t, d) in s]))**2

N, K = map(int, input().split())
menu = []

for i in range(N):
    t, d = map(int, input().split())
    menu.append((t, d))
    
#Sort with value d
sorted(menu, key = lambda x:x[1], reverse=True)
#print(menu)

menu_ = menu[:K]
#x = len(set([t for (t, d) in menu_]))
_menu = menu[K:]

def sushi():
    for (t, d) in reversed(menu_):
        if [i for (i, v) in menu_].count(t) != 1:
            menu_.remove((t, d))
            #print(menu_)
            for (ii, vv) in _menu:
                if ii != t:
                    menu_.append((ii, vv))
                    #print(menu_)
                    _menu.remove((ii, vv))
                    #print(_menu)
                    return False
    return True        

#print(menu_)
g = []
for idx in range(K, N):
    g.append(manzoku(menu_))

    if sushi():
        break

print(max(g))    
    

Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools

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

for i in range(N):
    t, d = 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]))


Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Runtime Error):
import itertools

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

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

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

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


Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools

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

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

def manzoku(s):
    #Oishisa basic point
    Oishisa = sum([menu[i][1] for i in s])
   
    #Syurui bonus point
    Syurui = len(set([menu[i][0] for i in s]))**2
    
    #Manzoku point
    return Oishisa + Syurui

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

Fixed submission:
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = 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)