Harryxun/stf_run huggingface dataset:
import sys
#import numpy as np
#from collections import defaultdict
import math
#from collections import deque

input = sys.stdin.readline
import numpy as np



def main():

    N,W = map(int,input().split())

    dp = [0] * (W+2)

    for _ in range(N):
        w,v = map(int,input().split())

        for j in range(W+1,w-1,-1):
            dp[j] =max(dp[j-w] +v ,dp[j])

    print(dp[W])
#    print(dp)




if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
#import numpy as np
#from collections import defaultdict
import math
#from collections import deque

input = sys.stdin.readline
#import numpy as np



def main():

    N,W = map(int,input().split())

    dp = [0] * (W+2)

    for _ in range(N):
        w,v = map(int,input().split())

        for j in range(W+1,w-1,-1):
            dp[j] =max(dp[j-w] +v ,dp[j])

    print(dp[W])
#    print(dp)




if __name__ == "__main__":
    main()
import sys
from collections import defaultdict


def dfs(tree, p, cnt, visited):
    visited[p] = True
    cnt_here = cnt[p]
    for c in tree[p]:
        if visited[c]:
            continue
        cnt[c] += cnt_here
        dfs(tree, c, cnt, visited)


def main():
    input = sys.stdin.buffer.readline
    n, q = map(int, input().split())
    tree = defaultdict(list)
    for _ in range(n - 1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)

    cnt = [0] * (n + 1)

    for _ in range(q):
        p, x = map(int, input().split())
        cnt[p] += x
    visited = [False] * (n + 1)
    dfs(tree, 1, cnt, visited)
    print(*cnt[1:])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import defaultdict


def dfs(tree, p, cnt, visited):
    visited[p] = True
    cnt_here = cnt[p]
    for c in tree.get(p):
        if visited[c]:
            continue
        cnt[c] += cnt_here
        dfs(tree, c, cnt, visited)


def main():
    input = sys.stdin.buffer.readline
    sys.setrecursionlimit(10 ** 9)
    n, q = map(int, input().split())
    tree = defaultdict(list)
    for _ in range(n - 1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    tree = dict(tree)
    cnt = [0] * (n + 1)

    for _ in range(q):
        p, x = map(int, input().split())
        cnt[p] += x
    visited = [False] * (n + 1)
    dfs(tree, 1, cnt, visited)
    print(*cnt[1:])


if __name__ == "__main__":
    main()
n = input()
while n<100 or n>999:
    n = input()
x = len(n)
for i in range(x):
    if n[i] is '7':
        print('Yes')
        break

### FIXED CODE ###

n = input()
x = len(n)
b = 'false'
for i in range(x):
    if n[i] is '7':
        b = 'true'
        print('Yes')
        break
if b is not 'true':
  print('No')
N, M=map(int,input().split())
if M==0:
	print("0 0")
else:
	ac=0
	pe=0
	ch=[]
	for i in range(M):
		a, b=input().split()
        a=int(a)
		if a in ch:
			continue
		elif b=="AC":
			ch.append(a)
			ac+=1
		else:
			pe+=1
	print(ac,pe)


### FIXED CODE ###

N, M=map(int,input().split())
if M==0:
	print("0 0")
else:
	ac=0
	pe=0
	ch=[0]*N
	Ch=[0]*N
	for i in range(M):
		a, b=input().split()
		a=int(a)-1
		if ch[a]==1:
			continue
		elif b=="WA":
			Ch[a]+=1
		else:
			ch[a]=1
			ac+=1
			pe+=Ch[a]
	print(ac,pe)
A,B,M = map(int,input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
s = [input().split() for i in range(M)]

mini = min(a) + min(b)

total = []
for i in s:
    total.append(a[int(i[0])-1]+b[int(i[1])]- int(i[-1]))
    
mini_2 = min(total)

if mini <= mini_2:
    print(mini)
else:
    print(mini_2)

### FIXED CODE ###

A,B,M = map(int,input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
s = [input().split() for i in range(M)]

mini = min(a) + min(b)

total = []
for i in s:
    total.append(a[int(i[0])-1]+b[int(i[1])-1]- int(i[-1]))
    
mini_2 = min(total)

if mini <= mini_2:
    print(mini)
else:
    print(mini_2)
N=int(input())
A=list(map(int,input().split()))
x=1
for i in A:
  x*=i
	if x>1000000000000000000:
  	print('-1')
    break
else:
  print(x)

### FIXED CODE ###

import sys
N=int(input())
A=list(map(int,input().split()))
if 0 in A:
  print('0')
  sys.exit()
x=1
for i in A:
  x*=i
  if x>1000000000000000000:
    print('-1')
    sys.exit()
print(x)
D,N = map(int,(input().split()))
l = [[] for _ in range(3)]
for i in range(1,1000001):
    c = 0
    j = i
    while j%100 == 0:
        c += 1
        j //= 100
    if c < 3:
        l[c].append(i)

print(l[D][N-1])

### FIXED CODE ###

D,N = map(int,(input().split()))
l = [[] for _ in range(3)]
for i in range(1,1010001):
    c = 0
    j = i
    while j%100 == 0:
        c += 1
        j //= 100
    if c < 3:
        l[c].append(i)

print(l[D][N-1])
# ceil関数(2引数)
def ceilT(a,b): #ceil(a/b)
    return (a+b-1)//b
H,A=map(int,input().split())
print(ceil(H,A))

### FIXED CODE ###

# 0405の分もやる

# ABC153-C
if False:
    N,K=map(int,input().split())
    H=[int(i) for i in input().split()]
    H.sort(reverse=True)
    print(sum(H[K:]))

# ABC153-D
if False:
    H=int(input())
    cnt=1
    ans=0
    while H>1:
        ans+=cnt
        H//=2
        cnt*=2
    print(ans+cnt)

# ABC153-A
if True:
    # ceil関数
    def ceil(a,b): #ceil(a/b)
        return (a+b-1)//b

    H,A=map(int,input().split())
    print(ceil(H,A))
S = input()
ans = 0
for i in range(1 << (len(S)-1)):
    eq = S
    for j in range(len(S)-1):
        if i & (1 << j):
            eq = eq[:j+1] + "," + eq[j+1:]
        else:
            pass
    eq = eq.split(",")
    eq = list(map(int,eq))
    ans += sum(eq)
print(ans)

### FIXED CODE ###

S = input()
ans = 0
for i in range(1 << (len(S)-1)):
    eq = S
    k = 0
    for j in range(len(S)-1):
        if i & (1 << j):
            eq = eq[:j+1+k] + "," + eq[j+1+k:]
            k +=1
        else:
            pass
    eq = eq.split(",")
    eq = list(map(int,eq))
    ans += sum(eq)
print(ans)
N, M = map(int, input().split())
list_a = [int(x) for x in input().split()]

import fractions

def insu2(a) :
    insu = 0
    while a%2 == 0 :
        insu += 1
        a /= 2
    return insu

check = True

for i in list_a :
    if insu2(i) != insu2(list_a[0]) :
        check = False

ans_0 = list_a[0]
for i in range(1,N) :
    ans_0 = ans_0 * list_a[i] // fractions.gcd(ans_0, list_a[i])

if ans_0 == 2 :
    ans = int(M+1/2)
else :
    ans = int((int(M/(ans_0/2))+1)/2)

if check == False :
    print(0)
else :
    print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
list_a = [int(x) for x in input().split()]

import fractions

def insu2(a) :
    insu = 0
    while a%2 == 0 :
        insu += 1
        a /= 2
    return insu

check = True

for i in list_a :
    if insu2(i) != insu2(list_a[0]) :
        print(0)
        exit()

ans_0 = list_a[0]
for i in range(1,N) :
    ans_0 = ans_0 * list_a[i] // fractions.gcd(ans_0, list_a[i])

ans_0 //= 2
ans = M//ans_0 - M//(ans_0*2)

print(ans)
import copy

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
  l=copy.copy(a)
  del l[i]
  r=[]
  for j in range(n-2):
    r.append(gcd(l[j],l[j+1]))
  g=max(r)
  if ans<g:
    ans=g
print(ans)


### FIXED CODE ###

import fractions
n=int(input())
a=list(map(int,input().split()))
l=[a[0]]
r=[a[-1]]
for i in range(n-1):
  l.append(fractions.gcd(l[i],a[i+1])) #l[i] は最初i個
for i in range(n-1):
  r.append(fractions.gcd(r[i],a[-2-i])) #r[i]は右i r[n-1]=全部 l[0]and r[n-3]
m=[l[n-2],r[n-2]]
for i in range(n-2):
  m.append(fractions.gcd(l[i],r[n-i-3]))
print(max(m))
N, M = map(int,input().split()))
l = list(map(int,input().split()))
su = l.sum()
if N < su:
    print(-1)
else:
    print(N - su)

### FIXED CODE ###

N, M = map(int,input().split())
l = list(map(int,input().split()))
su = sum(l)
if N < su:
    print('-1')
else:
    print(N - su)
##(N,K)=map(int,input().split())
##v=list(map(int, input().split()))
N=int(input())

v=[0]*N
for i in range(N):
    c=int(input())
    v[c-1]=i

for i in v:
    print(i+1)
    print(" ")

### FIXED CODE ###

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

N=int(input())
c=list(map(int, input().split()))
v=[0]*N
for i in range(N):
    v[c[i]-1]=i

for i in v:
    print(i+1)
    print(" ")
import sys
n = int（sys.stdin.readline())
t = 0
for i in range(N):
  if i%3 != 0 or i%5 != 0:
    t += i
print(t)

### FIXED CODE ###

import sys
n = int(sys.stdin.readline())
t = 0
for i in range(n+1):
  if i%3 != 0 and i%5 != 0:
    t += i
print(t)
import sys

def main():
    n = map(int, input().split())
    for i in range(1, 10, 1):
        if 1 <= n//i <= 9 and (n/i).is_integer():
            print('Yes')
            sys.exit()
        else:
            print('No')
main()

### FIXED CODE ###

import sys

def main():
    n = int(input())
    for i in range(1, 10, 1):
        if 1 <= n//i <= 9 and (n/i).is_integer():
            print('Yes')
            sys.exit()
    print('No')
    
main()
import math
x,y = map(int, input().split( ))
ans = int(math.log2(y/x))+1
print(ans)



### FIXED CODE ###

x,y = map(int, input().split( ))
ans = 1

while x*2<=y:
    x*=2
    ans+=1
print(ans)
#C

ans = []
x,n = map(int,input().split())
l = list(map(int,input().split()))

l.sort()

ans.append(x)

print(x,n)
print(l)

nl = [0] * 100


for i in l:
    nl[i] = i

if(not (n == 0)):
    #プラス方向
    mx = x+1
    if(mx < 100):
        for i in range(x+1,len(nl)+1):
            if( nl[i] ==  0):
                ans.append(mx)
                break
            mx = mx + 1
    
    
    mi = x - 1
    if(mi > 1):
        for i in range(x-1,1,-1):
            if( nl[i] ==  0):
                ans.append(mi)
                break
            mx = mx + 1        

print("ans=",ans)
print(min(ans))


### FIXED CODE ###

import sys

X, N = map(int,input().split())
p = list(map(int,input().split()))

for d in range(X + 1):
    for s in [-1, +1]:
        a = X + s * d
        if p.count(a) == 0:
            print(a)
            sys.exit(0)
n,k=map(int,input().split())
ans=0
while(n>0)
    n=n//k
    ans+=1
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
ans=0
while(n>0):
    n=n//k
    ans+=1
print(ans)
def popcount(x):
    xb = bin(x)
    return xb.count("1")
def solve(x, count_1):
    temp = x %count_1
    if(temp == 0):
        return 1
    else:
        return 1 + solve(temp, popcount(temp))
n = int(input())
x = input()
x_b = int(x, 2)
mod = x.count("1")
xm1 = x_b %(mod+1) 
xm2 = x_b %(mod-1)
for i in range(n):
    if(x[i] == "0"):
        mi = (((2**(n-1-i))%(mod+1) + xm1) % (mod+1))
        if(mi == 0):
            print(1)
        else:
            print(1 + solve(mi, popcount(mi)))
    else:
        mi = ((xm2-(2**(n-1-i))%(mod-1)) % (mod-1))
        if((x_b - xm2 == 0)):
            print(0)
        elif(mi == 0):
            print(1)
        else:
            print(1 + solve(mi, popcount(mi)))

### FIXED CODE ###

def popcount(x):
    xb = bin(x)
    return xb.count("1")
def solve(x, count_1):
    temp = x %count_1
    if(temp == 0):
        return 1
    else:
        return 1 + solve(temp, popcount(temp))
n = int(input())
x = input()
x_b = int(x, 2)
mod = x.count("1")
xm1 = x_b %(mod+1)
if(mod != 1):
    xm2 = x_b %(mod-1)
for i in range(n):
    if(x[i] == "0"):
        mi = (((pow(2, n-1-i, mod+1) + xm1) % (mod+1)))
        if(mi == 0):
            print(1)
        else:
            print(1 + solve(mi, popcount(mi)))
    else:
        if(mod == 1):
            print(0)
        else:
            mi = ((xm2-pow(2, n-1-i, mod-1)) % (mod-1))
            if((x_b - xm2 == 0)):
                print(0)
            elif(mi == 0):
                print(1)
            else:
                print(1 + solve(mi, popcount(mi)))
s = raw_input()
n = 0

def mul(s):
    if len(s) < 3:
        return 0
    n = 0
    flag = True
    while flag:
        res = 0
        s1 = s
        _res = 0
        for i in xrange(len(s) - 2):
        	j = j + _res
            str = s[j:(j+3)]
            if str == "ABC":
                n = n + 1
                res = res + 1
                _res = _res + 2
                s1 = s1[:j] + "BCA"+ s1[j+3:]
        if res == 0:
            flag =False
        s = s1
    return n
print mul(s)

### FIXED CODE ###

s=input()
n=0
c=0
i=0
while i<len(s):
  if s[i]=="A":
    c+=1
  elif s[i:i+2]=="BC":
    n+=c
    i+=1
  else:
    c=0
  i+=1
print(n)
s=input()
input()
i=0
while s[i]=="1":
    i+=1
    if i==len(s)-1:
        break
print(s[i])

### FIXED CODE ###

s=input()
k=int(input())-1
if s.count("1")==len(s):
    t=k
    print(1)
else:
    i=0
    while s[i]=="1":
        i+=1
    if k<i:
        print(1)
    else:
        print(s[i])
# Rows and columns(行と列)
rac_count = 3
rac_all = [input().split() for a in range(rac_count)]

rac_0 = rac_all[0]
rac_1 = rac_all[1]
rac_2 = rac_all[2]

rac_0.extend(rac_1)
rac_0.extend(rac_2)

print(str(rac_0[0] + rac_0[4] + rac_0[8]))

### FIXED CODE ###

# Rows and columns(行と列)
rac_count = 3
rac_all = [input() for a in range(rac_count)]

rac_0 = rac_all[0]
rac_1 = rac_all[1]
rac_2 = rac_all[2]

rac_0_0 = list(rac_0)
rac_1_1 = list(rac_1)
rac_2_2 = list(rac_2)

rac_0_0.extend(rac_1_1)
rac_0_0.extend(rac_2_2)

print(str(rac_0_0[0] + rac_0_0[4] + rac_0_0[8]))
import math
r = int(input())
print(r**2*math.pi,r*2*math.pi)

### FIXED CODE ###

import math
r = float(input())
print(r**2*math.pi,r*2*math.pi)
a = input()
if a = "ABC":
    print("ARC")
else:
    print("ABC")

### FIXED CODE ###

a = input()
if a == "ABC":
    print("ARC")
else:
    print("ABC")
X = input("X:")
K = input("K:")
D = input("D:")
x = int(X)
k = int(K)
d = int(D)
p = k*d-x
q = p//(2*d)
r = p/(2*d)
if r <= 0:
    print(-p)
elif 0 < r < k:
    s = min(p-2*d*q,-p+2*d*(q+1))
    print(s)
else:
    print(x+k*d)



### FIXED CODE ###

x,k,d=map(int,input().split())
p=k*d-x
q=p//(2*d)
r=p/(2*d)
if r<=0:
  print(-p)
elif 0<r<k:
  s=min(p-2*d*q,-p+2*d*(q+1))
  print(s)
else:
  print(-x-k*d)
from scipy.misc import comb
r1, c1, r2, c2 = map(int, input().split())
mod = 1000000007
hole = (comb(r2 + c2 + 2, r2 + 1, exact=True) - 1) % mod
rect1 = (comb(r2 + c1 - 1 + 2, r2 + 1, exact=True) - 1) % mod
rect2 = (comb(r1 - 1 + c2 + 2, r1, exact=True) - 1) % mod
duplicate = (comb(r1 + c1, r1, exact=True) - 1) % mod
ans = (hole - rect1 - rect2 + duplicate) % mod
print(ans)

### FIXED CODE ###

r1, c1, r2, c2 = map(int, input().split())

p = 10 ** 9 + 7
size = 1010000 * 2
f_list = [1] * size
for i in range(1, size):
    f_list[i] = (f_list[i - 1] * i) % p

def cmb(n, r):
    return f_list[n + r] * pow(f_list[n], p-2, p) * pow(f_list[r], p-2, p) % p

hole = cmb(r2 + 1, c2 + 1) - 1
rect1 = cmb(r2 + 1, c1) - 1
rect2 = cmb(r1, c2 + 1) - 1
duplicate = cmb(r1, c1) - 1
ans = (hole - rect1 - rect2 + duplicate) % p
print(ans)
def partition(A, p, r):
    x = A[r][1]
    i = p-1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1


def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)


def suitlist(cards):
    suits = [[]]*len(cards)
    for card in cards:
        suits[int(card[1])].append(card[0])
    return suits


def is_stable(before, after):
    suits_b = suitlist(before)
    suits_a = suitlist(after)
    for a, b in zip(suits_b, suits_a):
        if a != b:
            return False
    return True


n = int(input())
cards = []
origin = cards.copy()
for _ in range(n):
    cards.append(input().split())
origin = cards.copy()
quicksort(cards, 0, n - 1)
print("Stable" if is_stable(origin, cards) else "Not stable")
for card in cards:
    print(*card)

### FIXED CODE ###

def partition(A, p, r):
    x = int(A[r][1])
    i = p-1
    for j in range(p, r):
        if int(A[j][1]) <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1


def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)


def is_stable(cards):
    for i in range(1, len(cards)):
        if cards[i-1][1] == cards[i][1]:
            if cards[i-1][2] > cards[i][2]:
                return False
    return True


n = int(input())
cards = []
for i in range(n):
    cards.append(input().split() + [i])
quicksort(cards, 0, n - 1)
print("Stable" if is_stable(cards) else "Not stable")
for card in cards:
    print(card[0], card[1])
n, k = map(int, input().split())
H = list(map(int, input().split()))
cnt = 0
for i in n:
    if H[i] >= k:
        cnt += 1
print(cnt)


### FIXED CODE ###

n, k = map(int, input().split())
H = list(map(int, input().split()))
cnt = 0
for i in range(n):
    if H[i] >= k:
        cnt += 1
print(cnt)
N, Q = map(int, input().split())
s = '#' + input() + '#'
T = []
D = []
for t, d in [input().split() for _ in range(Q)]:
  T.append(T)
  D.append(-1 if d=='L' else 1)

#そのゴーレムがどちらかの端にたどりつけるかの関数
def canReachEnd(iL, dir):
  nowL = iL
  nowt = s[iL]
  for t, d in zip(T, D):
    if t == nowt:
      nowL += d
      nowt = s[nowL]
  if dir == 1 and nowL == N+1:
    return True
  elif dir == -1 and nowL == 0:
    return True
  else:
    return False

#1. iは左にたどりつくがi+1は辿りつかないようなiを探す
left = 0
right = N+1
while right > left+1:
  check = (left+right)//2
  if canReachEnd(check, -1):
    left = check
  else:
    right = check
leftborder = leftborder

#2. jは右にたどり着くがj-1は辿りつかないようなjを探す
left = leftborder
right = N+1
while right > left+1:
  check = (left+right)//2
  if canReachEnd(check, 1):
    right = check
  else:
    left = check
rightborder = right

dropcnt = 0
dropcnt += leftborder
dropcnt += (N-(rightborder-1))
print(N-dropcnt)


### FIXED CODE ###

N, Q = map(int, input().split())
s = '#' + input() + '#'
#room[0], [1~N], [N+1]と考える
#文字を取り出すとき:[1~N]
T = [] #Title[0～Q-1]
D = [] #Direction[0～Q-1] R:1, L:-1で表現
for t, d in [input().split() for _ in range(Q)]:
  T.append(t)
  D.append(-1 if d=='L' else 1)

#そのゴーレムがどちらかの端にたどり着けるかの関数
#True, Falseを返す
def canReachEnd(iL, dir):
  #iLは初期マス(1~N), dirは方向(L:-1, R:1)
  
  #nowL:今いるマスの位置
  nowL = iL
  #nowt:今いるマスに書いてある文字
  nowt = s[iL]
  for t, d in zip(T, D):
    if t == nowt:
      #左に動いても右に動いてもdを足せばok
      #端に落ちたら文字が'#'なので気にしない
      nowL += d
      nowt = s[nowL]
      
  if dir == 1 and nowL == N+1:
    return True
  elif dir == -1 and nowL == 0:
    return True
  else: return False
#たどり着けるかの関数終わり

#ここから二分探索で2つの「境目」を探す

#(1)「iは左に辿り着くがi+1は辿り着かない」iを探す
#何も辿り着かない場合はi=0とする？
#全部辿り着く場合はi=Nとする？
#leftとrightが隣接したときのleftを答えとする？
##すると、ありえるleftの範囲は0~N
left = 0
right = N+1
while right > left+1:
  check = (left+right)//2
  
  if canReachEnd(check, -1):left = check
  else: right = check
#答えを代入
leftborder = left


#(2)「jは右に辿り着くがj-1は辿り着かない」jを探す
#何も辿り着かない場合はj=N+1とする？
#全部辿り着く場合はj=1とする？
#leftとrightが隣接したときのrightを答えとする？
##すると、ありえるrightの範囲はleftborder+1~N+1
left = leftborder #(1)で左に辿り着くと分かった部分は省く
right = N+1
while right > left+1:
  check = (left+right)//2
  
  if canReachEnd(check, 1):right = check
  else: left = check
#答えを代入
rightborder = right

#二分探索終わり

#lbには左に辿り着く限界,rbには右に辿り着く限界が格納
#1~lbまでは全部左端に落ちる lb==0なら0
#rb~Nまでは全部右端に落ちる rb==N+1なら0

dropcnt = 0
dropcnt += leftborder
dropcnt += (N-(rightborder-1))
print(N-dropcnt)
from collections import defaultdict

n, k = map(int, input().split())
ans = 0
top = [0] * 10 ** 5
sub = []

for i in range(n):
    t, d = map(int, input().split())
    if top[t] == 0:
        top[t] = d
    else:
        if d > top[t]:
            sub.append(top[t])
            top[t] = d
        else:
            sub.append(d)

top.sort(reverse=True)
top_sum = [0]
sub.sort(reverse=True)
sub_sum = [0]

for p in top:
    if p == 0:
        top_sum.append(-1)
    else:
        top_sum.append(top_sum[-1] + p)

for p in sub:
    sub_sum.append(sub_sum[-1] + p)

ans = 0

for i in range(1, k + 1):
    if (len(sub_sum) - 1) >= (k - i) and top_sum[i] != -1:
        ans = max(ans, top_sum[i] + sub_sum[k - i] + i ** 2)
        
print(ans)


### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
top = [0] * n
sub = []

for i in range(n):
    t, d = map(int, input().split())
    t -= 1
    if top[t] == 0:
        top[t] = d
    else:
        if d > top[t]:
            sub.append(top[t])
            top[t] = d
        else:
            sub.append(d)

top.sort(reverse=True)
top_sum = [0]
sub.sort(reverse=True)
sub_sum = [0]

for p in top:
    if p == 0:
        top_sum.append(-1)
    else:
        top_sum.append(top_sum[-1] + p)

for p in sub:
    sub_sum.append(sub_sum[-1] + p)

ans = 0

for i in range(1, k + 1):
    if (len(sub_sum) - 1) >= (k - i) and top_sum[i] != -1:
        ans = max(ans, top_sum[i] + sub_sum[k - i] + i ** 2)

print(ans)
from math import ceil
A = int(input()); B = int(input())

print(ceil(B / A))

### FIXED CODE ###

import math
A,B=map(int, input().split())
print(math.ceil((B-1)/(A-1)))
import sys

z = 0
for line in sys.stdin:
  xs = map(int, line.split())
  if len(xs) == 1: continue
  z += 380000 * xs[0] if xs[1] == 'BTC' else xs[0]
print(z)

### FIXED CODE ###

import sys

z = 0
for line in sys.stdin:
  xs = line.split()
  if len(xs) < 2:
    continue
  if xs[1] == 'BTC':
    z += 380000 * float(xs[0])
  else: 
    z += float(xs[0])
print(z)
#n>=25なら鳩ノ巣で0
#2人以上居るdは一意
#あとはしらみつぶし
#周期性考慮せよ
n = int(input())
if n>=25:
    print(0)
    exit()

d = list(map(int, input().split( )))
if 0 in d:##
    print(0)
    exit()
d.append(0)
dic = {}

for di in d:
    if di in dic:
        dic[di] += 1
    else:
        dic[di]= 1
solo = []
times = []
for di in dic:
    if dic[di]==1:#di=0はここに入る
        solo.append(di)
    elif dic[di]==2:
        times.append(di)
        times.append(24-di)
    else:
        print(0)
        exit()
        
ans = 0
m = len(solo)
bit = 1<<m

for i in range(bit):
    times2 = []
    for t in times:
        times2.append(t)
    for j in range(m):
        if i>>j&1:
            times2.append(solo[j])
        elif solo[j]:
            times2.append(24-solo[j])
    times2.sort()
    dif = 24
    if len(times2)==1:###
        print(0)
        exit()
    #print(times2)

    for k in range(len(times2)-1):
        dif = min(dif,times2[k+1]-times2[k])
    dif = min(dif, 24 + times [0] -times2[-1])
    ans = max(ans,dif)
print(ans)
    


### FIXED CODE ###

#n>=25なら鳩ノ巣で0
#2人以上居るdは一意
#あとはしらみつぶし

n = int(input())
if n>=25:
    print(0)
    exit()

d = list(map(int, input().split( )))
if 0 in d:##
    print(0)
    exit()
d.append(0)
dic = {}

for di in d:
    if di in dic:
        dic[di] += 1
    else:
        dic[di]= 1
solo = []
times = []
for di in dic:
    if dic[di]==1:#di=0はここに入る
        solo.append(di)
    elif dic[di]==2:
        times.append(di)
        if di!=12:
            times.append(24-di)
        else:
            print(0)
            exit()
    else:
        print(0)
        exit()
        
ans = 0
m = len(solo)
bit = 1<<m

for i in range(bit):
    times2 = []
    for t in times:
        times2.append(t)
    for j in range(m):
        if i>>j&1:
            times2.append(solo[j])
        else:####???
            times2.append(24-solo[j])
    times2.sort()
    dif = 24
    if len(times2)==1:###
        print(0)
        exit()
    #print(times2)

    for k in range(len(times2)-1):
        dif = min(dif,times2[k+1]-times2[k])
    dif = min(dif,times2[0] + 24 - times2[-1])
    ans = max(ans,dif)
print(ans)
,B,C,K=map(int,input().split())
ans=0
if A>=K:
  ans=K
elif A<K and K<=A+B:
  ans=A
else :
  ans=A-(K-A-B)
print(ans)

### FIXED CODE ###

A,B,C,K=map(int,input().split())
ans=0
if A>=K:
  ans=K
elif A<K and K<=A+B:
  ans=A
else :
  ans=A-(K-A-B)
print(ans)
60 88 34
92 41 43
65 73 48
10
60
43
88
11
48
73
65
41
92
34

### FIXED CODE ###

import sys

ar = []
x = sys.stdin.readline()
x = x.split(' ')
ar.extend([int(str) for str in x])
x = sys.stdin.readline()
x = x.split(' ')
ar.extend([int(str) for str in x])
x = sys.stdin.readline()
x = x.split(' ')
ar.extend([int(str) for str in x])

n = int(sys.stdin.readline())
ret = []
for i in range(n):
  b = int(sys.stdin.readline())
  if( b in ar):
    index = ar.index(b)
    ret.append(index)

result = "No"
for i in range(0,3):
  if( i*3+0 in ret and i*3+1 in ret and i*3+2 in ret ):
    result = "Yes"
  if( i+0*3 in ret and i+1*3 in ret and i+2*3 in ret ):
    result = "Yes"
if( 0 in ret and 4 in ret and 8 in ret ):
  result = "Yes"
if( 2 in ret and 4 in ret and 6 in ret ):
  result = "Yes"

print(result)



sys.stdout.flush()