Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n, k = map(int, input().split())
nums = list(map(int, input().split()))
def judge(n, k, nums):
  original = nums
  types = set(nums)
  diff = len(types) - k
  count = []
  ans = 0

  if len(types) <= k:
    return 0

  for i in types:
    count.append(original.count(i))
  count.sort()

  for i in range(diff):
    ans += count[i]
  
  return ans

print(judge(n, k, nums))

### FIXED CODE ###

n, k = map(int, input().split())
nums = list(map(int, input().split()))
def judge(n, k, nums):
  original = nums
  types = set(nums)
  diff = len(types) - k
  count = []
  temp_count = 0
  temp_char = nums[0]
  ans = 0
  nums.sort()

  if len(types) <= k:
    return 0

  for i in range(n):
    if nums[i] == temp_char:
      temp_count += 1
    else:
      temp_char = nums[i]
      if not temp_count == 0:
        count.append(temp_count)
      temp_count = 1

    if i == n-1:
      if not temp_count == 0:
        count.append(temp_count)
        
  count.sort()
  
  return sum(count[:diff])

print(judge(n, k, nums))
### BUGGY CODE ###

import fractions

n, ma, mb = map(int,input().split())
a = [0] * (n + 1)
b = [0] * (n + 1)
c = [0] * (n + 1)
for i in range(1, n + 1):
    a[i], b[i], c[i] = map(int,input().split())

#iまでの薬品で、aがj(g),bがk(g)となるときの最小コスト
dp = [[[float('inf') for i in range(n + 1)] for j in range(401)] \
    for k in range(401)]

dp[0][0][0] = 0
sa = [0] * (n + 1)
sb = [0] * (n + 1)

for i in range(1, n + 1):
    sa[i] = sa[i - 1] + a[i]
    sb[i] = sb[i - 1] + b[i]

for i in range(1, n + 1):
    for j in range(sa[i] + 1):
        for k in range(sb[i] + 1):
            if j < a[i] or k < b[i]:
                dp[k][j][i] = dp[k][j][i - 1]
            else:
                dp[k][j][i] = min(dp[k][j][i - 1], \
                    dp[k - b[i]][j - a[i]][i - 1] + c[i])

i = 1
ans = float('inf')
while True:
    if i * ma > 400 or i * mb > 400:
        break
    ans = min(ans, dp[i * mb][i * ma][n])
    i += 1

if ans == float('inf'):
    ans = -1

print(ans)

### FIXED CODE ###

import fractions

n, ma, mb = map(int,input().split())
a = [0] * (n + 1)
b = [0] * (n + 1)
c = [0] * (n + 1)
for i in range(1, n + 1):
    a[i], b[i], c[i] = map(int,input().split())

#iまでの薬品で、aがj(g),bがk(g)となるときの最小コスト
dp = [[[10**15 for i in range(n + 1)] for j in range(401)] \
    for k in range(401)]

dp[0][0][0] = 0
sa = [0] * (n + 1)
sb = [0] * (n + 1)

for i in range(1, n + 1):
    sa[i] = sa[i - 1] + a[i]
    sb[i] = sb[i - 1] + b[i]

for i in range(1, n + 1):
    for j in range(401):
        if j > sa[i]:
            break
        for k in range(401):
            if k > sb[i]:
                break
            # i番目を買うか、買わないか
            if j < a[i] or k < b[i]:
                dp[k][j][i] = dp[k][j][i - 1]
            else:
                dp[k][j][i] = min(dp[k][j][i - 1], \
                    dp[k - b[i]][j - a[i]][i - 1] + c[i])

i = 1
ans = 10 ** 15
while True:
    if i * ma > 400 or i * mb > 400:
        break
    ans = min(ans, dp[i * mb][i * ma][n])
    i += 1

if ans == 10 ** 15:
    ans = -1

print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Regular Contest 095 c問題
Author     : Kitaura Hiromi
LastUpdate : 20180414
Since      : 20180414
"""
import random
import copy
def quickselect(items, item_index):

    def select(lst, l, r, index):

        # base case
        if r == l:
            return lst[l]

        # choose random pivot
        pivot_index = random.randint(l, r)

        # move pivot to beginning of list
        lst[l], lst[pivot_index] = lst[pivot_index], lst[l]

        # partition
        i = l
        for j in range(l+1, r+1):
            if lst[j] < lst[l]:
                i += 1
                lst[i], lst[j] = lst[j], lst[i]

        # move pivot to correct location
        lst[i], lst[l] = lst[l], lst[i]

        # recursively partition one side only
        if index == i:
            return lst[i]
        elif index < i:
            return select(lst, l, i-1, index)
        else:
            return select(lst, i+1, r, index)

    if items is None or len(items) < 1:
        return None

    if item_index < 0 or item_index > len(items) - 1:
        raise IndexError()

    return select(items, 0, len(items) - 1, item_index)

N = int(input())
X = list(map(int, input().split(" ")))
med1 = quickselect(copy.deepcopy(X), N//2-1)
med2 = quickselect(copy.deepcopy(X), N//2)
for i in range(N):
    if X[i] <= med1:
        print(med2)
    else:
        print(med1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Regular Contest 095 c問題
Author     : Kitaura Hiromi
LastUpdate : 20180414
Since      : 20180414
"""
import random
import copy

N = int(input())
X = list(map(int, input().split(" ")))
sorted_X = sorted(X)
med1 = sorted_X[N//2-1]
med2 = sorted_X[N//2]
for i in range(N):
    if X[i] <= med1:
        print(med2)
    else:
        print(med1)
### BUGGY CODE ###

n,a,b=map(int,input().split())
h=[]
for i in range(n):
    q=int(input())
    h.append(q)
left=0
right=max(h)+1
def en(t):
    cnt=0
    for i in range(n):
        if h[i]-b*t>0 and (h[i]-b*t)%(a-b)!=0:
            cnt+=((h[i]-b*t)//((a-b))+1)
        if h[i]-b*t>0 and (h[i]-b*t)%(a-b)==0:
            cnt+=((h[i]-b*t)//(a-b))
    if cnt<=t:
        return  True
    return  False
while left+1<right:
    tmp=(left+right)//2
    if en(tmp):
        right=tmp
    else:
        left=tmp
print(right)

### FIXED CODE ###

n,a,b=map(int,input().split())
h=[]
for i in range(n):
    q=int(input())
    h.append(q)
left=0
right=max(h)+1
def en(t):
    cnt=0
    for i in range(n):
        if h[i]-b*t>0 and (h[i]-b*t)%(a-b)!=0:
            cnt+=((h[i]-b*t)//((a-b))+1)
        if h[i]-b*t>0 and (h[i]-b*t)%(a-b)==0:
            cnt+=((h[i]-b*t)//(a-b))
    if cnt<=t:
        return  True
    return  False
while left+1<right:
    tmp=(left+right)//2
    if en(tmp):
        right=tmp
    else:
        left=tmp
print(right)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
if n%2:
    flag = True
else:
    flag = False
for i in range(n):
    if (i+1)%2:
        b.append(a[i])
    else:
        b.insert(0,a[i])
if flag:
    print(*b[::-1])
else:
    print(*b)


### FIXED CODE ###

from collections import deque
n = int(input())
a = list(map(str, input().split()))
b = deque()
if n%2:
    flag = False
else:
    flag = True
for i in range(n):
    if flag:
        if (i+1)%2:
            b.append(a[i])
        else:
            b.appendleft(a[i])
    else:
        if (i+1)%2:
            b.appendleft(a[i])
        else:
            b.append(a[i])
res = list(b)
print(' '.join(res))
### BUGGY CODE ###

import math
import calendar
import fractions
import itertools

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in list(itertools.permutations(a)):
    flag = 1
    for j in range(len(i) - 1):
        if i[j] * i[j + 1] % 4 != 0:
            flag = 0
            break
    if flag == 1:
       ans = 1
       break
if ans == 1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import math
import calendar
import fractions
import itertools

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

n = int(input())
a = map(int, input().split())
b = []
ans = 0
for i in a:
    c = i
    cnt = 0
    while c % 2 == 0 and cnt < 2:
        c /= 2
        cnt += 1
    b.append(cnt)
if my_index(b, 1) == False:
    if b.count(2) + 1 >= b.count(0):
        ans = 1
    else:
        ans = 0
else:
    if b.count(2) >= b.count(0):
        ans = 1
    else:
        ans = 0
if ans == 1:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

x,y = map(int,input().split())
maxx = y//x + 1
count = 0
for i in range(maxx):
  if x*(2**i) <= y:
    count += 1
print(count)

### FIXED CODE ###

x,y = map(int,input().split())
maxx = y//x + 1
count = 0
for i in range(maxx):
  if x*(2**i) <= y:
    count += 1
  else:
    break
print(count)
### BUGGY CODE ###

limit, sum_xyz = map(int, input().split())

pair = list()
for i in range(limit, -1, -1):
    x = i
    for j in range(limit, -1, -1):
        y = j
        if y < sum_xyz - limit - x or sum_xyz - x - y < 0:
            continue
        z = sum_xyz - x - y
        pair.append([x, y, z])

print(len(pair))

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
def main():
    K,S = [int(x) for x in input().split()]
 
    count = 0
 
    for x in range(K+1):
        for y in range(K+1):
            z = S - (x + y)
            if z >= 0 and z <= K:
                count += 1
 
    print(count)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np


def count_multi(s, d):
  a = np.array([int(c) for c in s])  # .astype(np.int)
  m = a  # % d
  keta = 1
  count = np.count_nonzero(m == 0)
  while len(m) > 1:
    m = (10*m[:-1] + a[keta:]) % d
    keta += 1
    count += np.count_nonzero(m == 0)
  return count
        
print(count_multi(input(), 2019))


### FIXED CODE ###

def main():
    mod = 2019
    count = [0] * 2019
    count[0] = 1
    s = input().strip()
    digit = 1
    current = 0
    for c in s[::-1]:
        current = (current + int(c) * digit) % mod
        count[current] += 1
        digit = digit * 10 % mod
    return sum([n * (n - 1) // 2 for n in count if n > 1])


print(main())
### BUGGY CODE ###

N = int(input())
S = input()
tei = 10000000000000000000000000000
for i in range(1,N-1):
  a = S[:(i-1)]
  b = S[(i+1):]
  kae = a.count("W") + b.count("E")
  tei = min(tei,kae)
a = S[1:]
b = S[:(N-1)]
sai = a.count("E")
go = b.count("W")
print(min(tei,sai,go))

### FIXED CODE ###

N = int(input())
S = input()
a = S[1:]
hazime = a.count("E")
tei = a.count("E")
for i in range(N-1):
  a = S[i]
  b = S[i+1]
  if a == "E" and b == "E":
    hazime += -1
    tei = min(tei,hazime)
  elif a == "E" and b == "W":
        continue
        tei = min(tei,hazime)
  elif a == "W" and b == "E":
     continue
     tei = min(tei,hazime)
  elif a == "W" and b == "W":
       hazime += 1
       tei = min(tei,hazime)
b = S[:N-1]
go = b.count("W")
tei = min(tei,go)
print(tei)
### BUGGY CODE ###

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

N,M=map(int,input().split())
key=[]
for i in range(0,M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    s=sum(2**(c[j]-1) for j in range(0,b))
    key.append([s,a])


node=2**N
djk=Dijkstra(node)
for i in range(0,M):
    for j in range(0,node):
        djk.add(j,key[i][0]|j,key[i][1])

d=djk.shortest_path(0)
if d[node-1]==float('inf'):
    print(-1)
else:
    print(d[node-1])

### FIXED CODE ###

N,M=map(int,input().split())
key=[]
cost=[]
for i in range(0,M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    s=sum(2**(c[j]-1) for j in range(0,b))
    key.append(s)
    cost.append(a)

node=2**N

dp=[[10**10 for i in range(0,node)] for j in range(0,M)]

for i in range(0,M):
    dp[i][node-1]=0
#i:何番までか j:手に入れた鍵
for i in range(0,M):
    for j in range(1,node):
        k=node-1-j
        if i==0:
            if k|key[0]==node-1:
                dp[0][k]=cost[0]
        else:
            dp[i][k]=min(dp[i-1][k],dp[i-1][k|key[i]]+cost[i])

if dp[M-1][0]>=10**10:
    print(-1)
else:
    print(dp[M-1][0])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = 0
for i in range(n-1):
    for j in range(i+1, n):
        s += a[i]*a[j]
        if s >= (10**9 +7):
            s %= (10**9 + 7)

s %= (10**9 + 7)
print(str(s))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = 0
mod = 10**9+7
asum = 0
for i in a:
    asum += i % mod
for i in range(n-1):
    s += ((a[i]%mod)*(asum-(a[i]%mod)))%mod
    asum = asum-(a[i]%mod)
s %= mod
print(str(s))
### BUGGY CODE ###

N = int(input())
S = input()
key = {}
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            key[S[i] + S[j] + S[k]] = 1
print(len(key))

### FIXED CODE ###

n = int(input())
S = input()
count = 0
for i in range(10):
    a = S.find(str(i))
    if a == -1:
        continue
    for j in range(10):
        b = S.find(str(j),a + 1)
        if b == -1:
            continue
        for k in range(10):
            if str(k) in S[b+1::]:
                count += 1
print(count)
### BUGGY CODE ###

a = int(input())
l = []
for i in range(a):
    t = int(input())
    l.append((i,t-1))
dic=[0]
k=l[0][1]
ans=1
for i in range(a):
    if k == 1:
        print(ans)
        break
    elif k not in dic:
        dic.append(k)
        k=l[k][1]
        ans+=1
    else:
        print(-1)
        break

### FIXED CODE ###

a = int(input())
l = []
for i in range(a):
    t = int(input())
    l.append((i,t-1))
dic={0}
k=l[0][1]
ans=1
for i in range(a):
    if k == 1:
        print(ans)
        break
    elif k not in dic:
        dic.add(k)
        k=l[k][1]
        ans+=1
    else:
        print(-1)
        break
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    jj = 0
    while jj < 1000:
        jj += 1
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if t >= M and t - p <= M:
            break
        elif t > M:
            l = m + 1
        else:
            u = m - 1
        k = []
    r = 0   
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    for i in range(len(k)):
        r += (k[i]+1) * A[i] + B[k[i]]
    return r - (t - M) * m
    
print(main())
    


### FIXED CODE ###

import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())
### BUGGY CODE ###

A,B=map(int,input().split())
a=A
for i in range(1,B-A+1):
    b=a^(A+i)
    a=b
print(a)


### FIXED CODE ###

A,B=map(int,input().split())
k=A%4
AA=A+4-k
l=B%4
BB=B-l
AAA=[]
BBB=[]
for i in range(A,AA):
    AAA+=[i]
for i in range(BB,B+1):
    BBB+=[i]

def henkan(A):
    if len(A)==4 or len(A)==0:
        return 0
    elif len(A)==3:
        return A[0]^A[1]^A[2]
    elif len(A)==2:
        return A[0]^A[1]
    elif len(A)==1:
        return A[0]
print(henkan(AAA)^henkan(BBB))
### BUGGY CODE ###

from fractions import gcd

N, M = map(int, input().split())
S = input()
T = input()

dic = {}
L = int((N*M) / gcd(N,M))
ans = L

for i in range(N):
  dic[int(i*(L/N)+1)] = i

for i in range(M):
  if i*(L/M)+1 in dic.keys():
    if S[dic[int(i*(L/M)+1)]] == T[i]:continue
    else: 
      ans = -1
      break

  


print(ans)


### FIXED CODE ###

from fractions import gcd

N, M = map(int, input().split())
S = input()
T = input()

dic = {}
L = int((N*M) / gcd(N,M))
ans = L

for i in range(N):
  dic[int(i*(L/N)+1)] = i

key = set(dic.keys())
for i in range(M):
  if i*(L/M)+1 in key:
    if S[dic[int(i*(L/M)+1)]] == T[i]:continue
    else: 
      ans = -1
      break

  


print(ans)
### BUGGY CODE ###

# 164 B

a, b, c, d = map(int, input().split())

while a != 0 or c != 0:
    c = c - b
    if c == 0:
        print("Yes")
        break
    a = a - d
    if a == 0:
        print("No")
        break

### FIXED CODE ###

# 164 B

a, b, c, d = map(int, input().split())

while a != 0 or c != 0:
    c = c - b
    if c <= 0:
        print("Yes")
        break
    a = a - d
    if a <= 0:
        print("No")
        break
### BUGGY CODE ###

from itertools import product

H, W, K = map(int, input().split())
grid = ""

for _ in range(H):
  grid += input()

ans = 10000

for Hcut in product((0, 1), repeat = H-1):
  Gr_num = sum(Hcut) + 1
  old = [0]*Gr_num
  cnt = 0
  for i in range(W):
    #縦一列のchocoを見る
    choco = grid[i::W]
    new = [0]*Gr_num
    gr = 0
    for j in range(H):
      new[gr] += int(choco[j])
      if j < H-1:
        if Hcut[j] == 1:
          gr += 1
    #そもそも一列でオーバーしてたら詰み。
    if max(new) > K:
      cnt += 10000
      break
    #新しい一列を追加しても大丈夫か確認
    check = [old[gr] + new[gr] for gr in range(Gr_num)]
    if max(check) > K:
      old = new[:]
      cnt += 1
    else:
      old = check[:]
  ans = min(ans, cnt+sum(Hcut))

print(ans)

### FIXED CODE ###

from itertools import product

H, W, K = map(int, input().split())
grid = ""

for _ in range(H):
  grid += input()

ans = 10000

for Hcut in product((0, 1), repeat = H-1):
  Gr_num = sum(Hcut) + 1
  old = [0]*Gr_num
  cnt = 0
  for i in range(W):
    #縦一列のchocoを見る
    choco = grid[i::W]
    new = [0]*Gr_num
    gr = 0
    for j in range(H):
      new[gr] += int(choco[j])
      if j < H-1:
        if Hcut[j] == 1:
          gr += 1
    #そもそも一列でオーバーしてたら詰み。
    if max(new) > K:
      cnt += 10000
      break
    #新しい一列を追加しても大丈夫か確認
    check = [old[gr] + new[gr] for gr in range(Gr_num)]
    if max(check) > K:
      old = new[:]
      cnt += 1
    else:
      old = check[:]
  ans = min(ans, cnt+sum(Hcut))

print(ans)
### BUGGY CODE ###

from collections import Counter
n = int(input())
st = input()
l = []
stc = Counter(st)
if(stc["W"] == stc["E"] -1 or stc["W"] == stc["E"] +1 or stc["W"] == stc["E"]):
    for i in range(n):
        east = Counter(st[:i])["W"]
        west = Counter(st[i + 1:])["E"]
        l.append(east + west)
else:
    t = stc.most_common(1)[0][0]
    for i in range(n):
        if(st[i] == t):
            east = Counter(st[:i])["W"]
            west = Counter(st[i + 1:])["E"]
            l.append(east + west)
print(min(l))

### FIXED CODE ###

from collections import Counter
n = int(input())
st = input()
l = []
stc = Counter(st)
ma = [Counter(st[:0])["W"] + Counter(st[1:])["E"]]
previous = st[0]
for i in range(1,n):
    temp = ma[-1]
    if(previous == "W"):
        temp+=1
    previous = st[i]
    if(st[i] == "E"):
        temp-=1
    ma.append(temp)
print(sorted(ma)[0])
### BUGGY CODE ###

from operator import itemgetter

n, k = map(int, input().split())
td = [tuple(int(x) for x in input().split()) for _ in range(n)]

a = sorted(td, key=itemgetter(1), reverse=True)

ans = [0]
v = []
s = []
for i in range(k):
    ans[0] += a[i][1]
    if a[i][0] not in s:
        s.append(a[i][0])
        v.append([a[i][1]])
    else:
        v[s.index(a[i][0])].append(a[i][1])
ans[0] += (len(s)) ** 2

t = []
d = []
for x, y in a[k:]:
    if x in s:
        continue
    elif x not in t:
        t.append(x)
        d.append([y])
    else:
        d[t.index(x)].append(y)

td = []
for i in range(len(t)):
    td.append((t[i], max(d[i])))

td = sorted(td, key=itemgetter(1), reverse=True)

ms = len(s)
p = 0
g = ms

for i in range(ms):
    v[i] = sorted(v[i])

#print(v)

for x, y in td:
    min_s = -1
    min_v = a[0][1]
    for i in range(ms):
        if len(v[i]) > 1:
            if min_v > v[i][0]:
                min_s = i
                min_v = v[i][0]
    if min_s == -1:
        break
    ans.append(ans[p] - min_v + y - g * g + (g + 1) * (g + 1))
    v[min_s].remove(v[min_s][0])
    g += 1
    p += 1

print(max(ans))



### FIXED CODE ###

from operator import itemgetter

n, k = map(int, input().split())
td = [tuple(int(x) for x in input().split()) for _ in range(n)]

a = sorted(td, key=itemgetter(1), reverse=True)

ans = [0]
s = set()
t = []
for i in range(k):
    ans[0] += a[i][1]
    if a[i][0] not in s:
        s.add(a[i][0])
    else:
        t.append(a[i][1])

p = len(s)
q = len(t) - 1

if q < 0:
    print(ans[0] + k * k)
    exit()

v = []
for i in range(k, n):
    if a[i][0] not in s:
        s.add(a[i][0])
        v.append(a[i][1])

ans[0] += p * p
d = 0

for x in v:
    ans.append(ans[d] + x - t[q] + (p + 1) * (p + 1) - p * p)
    p += 1
    d += 1
    q -= 1
    if q < 0:
        break

print(max(ans))
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

h, n = map(int, input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
l = h + max(a for a, _ in ab)

#DP[i] = i までの魔法でモンスターの体力を減らすため消耗する魔力の最小値
dp = [10**8+1] * l
dp[0] = 0

for i in range(l):  #最大L回繰り返せばよい
    for a, b in ab:
        dp[i] = min(dp[i-a] + b, dp[i])
print(min(dp[h:]))


### FIXED CODE ###

import numpy as np
H,N=map(int, input().split())
A = [None]*N
B = [None]*N
for i in range(N):
  A[i],B[i]=map(int,input().split())
dp=[10**8]*(H+1)
A = np.array(A)
B = np.array(B)
dp = np.array(dp)
dp[0]=0
for i in range(1,H+1):
  x=np.amin((dp[np.maximum(0,i-A)]+B))
  dp[i]=min(x,dp[i])
print(dp[-1])