Harryxun/stf_run huggingface dataset:
# coding:utf-8

import sys
import heapq
from collections import defaultdict, deque

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, k = LI()
sushi = [(d, t) for t, d in (LI() for _ in range(n))]
sushi.sort()
sushi.reverse()

# sushiを美味しいものからk個とる
umami_max = []  # 寿司の種類数が減らないように最低一つは別で確保
umami_sub = []  # 種類数を増やす時に捨てる候補(priority_queueで管理)
used = set()
for i in range(k):
    d, t = sushi[i]
    if t not in used:
        umami_max.append(d)
        used.add(t)
    else:
        heapq.heappush(umami_sub, d)

umami_1 = sum(umami_max)
umami_2 = sum(umami_sub)
sushi_v = len(used)
ans = umami_1 + umami_2 + sushi_v ** 2

# 捨てる寿司の候補がない場合，満足度はこれ以上大きくならない
if len(umami_sub) == 0:
    print(ans)
    exit()

for i in range(k, n):
    d, t = sushi[i]
    if t in used:
        continue
    used.add(t)
    umami_1 += d
    umami_2 -= heapq.heappop(umami_sub)  # 一番美味しくない寿司を消す
    sushi_v += 1
    ans = max(ans, umami_1 + umami_2 + sushi_v ** 2)

print(ans)


### FIXED CODE ###

# coding:utf-8

import sys
import heapq
from collections import defaultdict, deque

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, k = LI()
sushi = [(d, t) for t, d in (LI() for _ in range(n))]
sushi.sort()
sushi.reverse()

# sushiを美味しいものからk個とる
umami_max = []  # 寿司の種類数が減らないように最低一つは別で確保
umami_sub = []  # 種類数を増やす時に捨てる候補(priority_queueで管理)
used = set()
for i in range(k):
    d, t = sushi[i]
    if t not in used:
        umami_max.append(d)
        used.add(t)
    else:
        heapq.heappush(umami_sub, d)

umami_1 = sum(umami_max)
umami_2 = sum(umami_sub)
sushi_v = len(used)
ans = umami_1 + umami_2 + sushi_v ** 2

for i in range(k, n):
    if len(umami_sub) == 0:  # 捨てる寿司の候補がない場合，満足度はこれ以上大きくならない
        break
    d, t = sushi[i]
    if t in used:
        continue
    used.add(t)
    umami_1 += d
    umami_2 -= heapq.heappop(umami_sub)  # 一番美味しくない寿司を消す
    sushi_v += 1
    ans = max(ans, umami_1 + umami_2 + sushi_v ** 2)

print(ans)
n, q = map(int, input().split())
to = [[] for i in range(n)]
ans = [0 for i in range(n)]
def dfs(v, p = -1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    #to[b].append(a)
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
dfs(0)
print(" ".join(map(str, ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(200005) 
input = sys.stdin.readline
n, q = map(int, input().split())
to = [[] for i in range(n)]
ans = [0 for i in range(n)]
def dfs(v, p = -1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)
for i in range(n - 1):
    a, b = map(int, input().split())
    to[a - 1].append(b - 1)
    to[b - 1].append(a - 1)
for i in range(q):
    p, x = map(int, input().split())
    ans[p - 1] += x
dfs(0)
print(*ans)
import sys

N = int(sys.stdin.readline())
D = list(map(int, sys.stdin.readline().split()))

times = [0] * 24
for d in D:
    times[d] += 1

if max(times) > 2 or times[0] == 2 or times[12] == 2:
    print(0)
else:
    ans = 0
    # 1 - 11時間の時差の場合、Diと24 - Diの両方を試す
    for i in range(2**11):
        positions = []
        if times[0] == 1:
            positions.append(0)
        for j in range(11):
            if times[j+1] == 2:
                positions.append(j+1)
                positions.append(24 - j-1)
            elif times[j+1] == 1:
                if (i >> j) & 1:
                    positions.append(24 - j-1)
                else:
                    positions.append(j+1)
        if times[12] == 1:
            positions.append(12)
        positions.sort()
        # print(positions)
        lp = len(positions)
        d = float("inf")
        for p in range(lp):
            # 0をまたぐ場合がある
            if p == lp -1:
                diff = 24 - positions[p] + positions[0]
            else:
                diff = positions[p+1] - positions[p]
            d = min(d, diff if diff != 24 else 0)
        ans = max(ans, d)

print(ans)

### FIXED CODE ###

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

B = [-1 for _ in range(N)]
ans = []

for i in range(N, 0, -1):
    tmp_sum = 0
    tmp_i = 2 * i
    while N >= tmp_i :
        tmp_sum += B[tmp_i - 1]
        tmp_i += i

    # print(i, tmp_sum)
    if A[i-1] == tmp_sum % 2:
        B[i-1] = 0
    else:
        ans.append(i)
        B[i-1] = 1

print(len(ans))
if len(ans):
    print(" ".join(map(str, ans[::-1])))
N, X = map(int, input().split())

m = [input() for i in range(N)]

ans1 = X

MING = min(m)

for i in range(N):
    ans1 = ans1 - (m[i])

REST = (ans1)//(MING)

print((REST) + (N))

### FIXED CODE ###

N, X = map(int, input().split())
m = []
for _ in range(N):
    m.append(int(input()))

SUM = sum(m)
MIN = min(m)


if SUM < X:
    REST = X - (SUM)
    ans = REST//MIN
    print(ans + N)
    
else:
    print(N)
def conv(c): return '+' if c==1 else '-'
def main():
	num = [int(c) for c in input()]
	choices = [-1,1]
    for a in choices:
		for b in choices:
			for c in choices:
				if num[0]+num[1]*a+num[2]*b+num[3]*c==7:
					print("{}{}{}{}{}{}{}=7".format(num[0],conv(a),num[1],conv(b),num[2],conv(c),num[3]))
                    return
main()


### FIXED CODE ###

def conv(c): return '+' if c==1 else '-'
def main():
	num = [int(c) for c in input()]
	choices = [-1,1]
	for a in choices:
		for b in choices:
			for c in choices:
				if num[0]+num[1]*a+num[2]*b+num[3]*c==7:
					print("{}{}{}{}{}{}{}=7".format(num[0],conv(a),num[1],conv(b),num[2],conv(c),num[3]))
					return
main()
# -*- coding: utf-8 -*-

# Input
s = [input() for i in range(3)]
ST = list(s[0].split())
S = str(ST[0])
T = str(ST[1])

AB = list(s[1].split())
A = int(AB[0])
B = int(AB[1])

U = str(s[3])


# Proccess
If U == S:
	A -= 1
else:
	B -= 1

# Output							
print(str(A)+" "+str(B))

### FIXED CODE ###

# -*- coding: utf-8 -*-

# Input
s = [input() for i in range(3)]
ST = list(s[0].split())
S = str(ST[0])
T = str(ST[1])

AB = list(s[1].split())
A = int(AB[0])
B = int(AB[1])

U = str(s[2])


# Proccess
if U == S:
	A -= 1
else:
	B -= 1

# Output							
print(str(A)+" "+str(B))
#import random

n = input()
n = int(n)

# if n == 1:
# 	_ = input()
# 	print(0)

# else:
# 	h = []

for i in range(n):
	input()

	# rnd = random.randint(0, n)
	# count = 0

	# for i in range(rnd, n-1):
	# 	if h[i+1] <= h[i]:
	# 		count += 1

print(0)

### FIXED CODE ###

n = int(input())
x = input().split()
y = [0]
c = 0
for i in range(n-1):
  if int(x[i]) >= int(x[i+1]):
    c = c + 1
  else:
    y.append(c)
    c = 0
y.append(c)
print(max(y))
# coding:utf-8
import sys
import datetime

H1 = sys.stdin.readline()
M1 = sys.stdin.readline()
H2 = sys.stdin.readline()
M2 = sys.stdin.readline()
K = sys.stdin.readline()


while not 0 <= H1 < 23 and 0 <= M1 < 59 and 0 <= H2 < 23 and 0 <= M2 < 59:
    H1 = sys.stdin.readline()
    M1 = sys.stdin.readline()
    H2 = sys.stdin.readline()
    M2 = sys.stdin.readline()
    K = sys.stdin.readline()

if M2 > M1:
    a = (H2 - H1) * 60 + M2 - M1
    print(a - K)
if M2 < M1:
    b = (H2 - H1) * 60 + M1 - M2
    print(b - K)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline

h1, m1, h2, m2, k = map(int, readline().split())
print(60 * (h2 - h1) + m2 - m1 - k)
import math
H,N=map(int,input().split())
A=[]
B=[]
for i in range(N):
    n,a=input().split()
    A.append(int(n))
    B.append(int(a))
C=[]
for i in range(N):
    C.append(A[i]/B[i])
sub=0
for i in range(N):
    if C[i]>=C[sub]:
        sub=i
sub2=math.ceil(H/A[sub])
sub3=sub2*B[sub]
def f(x):
    if x<=0:
        return 0
    else:
        mini=f(x-A[0])+B[0]
        for i in range (1,N):
            sub=f(x-A[i])+B[i]
            if sub<mini:
                mini=sub
        return mini
for ia in range(H,sub2*A[sub]):
    if f(ia)<sub3:
        sub3=f(ia)
print(sub3)

### FIXED CODE ###

H,N=map(int,input().split())
A=[]
B=[]
for i in range(N):
    n,a=input().split()
    A.append(int(n))
    B.append(int(a))
def f(x):
    if x<=0:
        return 0
    else:
        mini=g(x-A[0])+B[0]
        for i in range (1,N):
            sub=g(x-A[i])+B[i]
            if sub<mini:
                mini=sub
        return mini
def g(x):
    if x<0:
        return 0
    else:
        return g_list[x]
g_list=[]
g_list.append(0)
for i in range(1,H+1):
    g_list.append(f(i))
print(g_list[-1])
from math import gcd

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

l = [0]*(n+1)
r = [0]*(n+1)

for i in range(n):
    l[i+1] = gcd(l[i], a[i])
    r[n-i-1] = gcd(r[n-i], a[n-i-1])

m = [0]*n

for i in range(n):
    m[i] = gcd(l[i], r[i+1])

print(max(m))

### FIXED CODE ###

from fractions import gcd

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

l = [0]*(n+1)
r = [0]*(n+1)

for i in range(n):
    l[i+1] = gcd(l[i], a[i])
    r[n-i-1] = gcd(r[n-i], a[n-i-1])

m = [0]*n

for i in range(n):
    m[i] = gcd(l[i], r[i+1])

print(max(m))
import math

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
u = set(a)
if len(u) == 1:
    print(n)
    exit()
else:
    g = 1
    for x in u:
        g = g * x // math.gcd(g, x)
    b = 0
    for i in range(n):
        b = b + (g // a[i])
print(b%MOD)

### FIXED CODE ###

import fractions

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
u = sorted(set(a))
if len(u) == 1:
    print(n)
    exit()
else:
    g = 1
    for x in u:
        g = (g * x) // fractions.gcd(g, x)
    b = 0
    for i in range(n):
        b = b + (g // a[i])
print(b%MOD)
N=int(input())
a=list(map(int,input().split()))
S=sum(a)
SS=0
mi=abs(S-SS)
for i in range(N):
  S=S-a[i]
  SS=SS+a[i]
  if mi>=abs(S-SS):
    mi=abs(S-SS)
print(mi)

### FIXED CODE ###

a,b=map(int,input().split())
if a*b*(a+b)%3==0:
  print("Possible")
else:
  print("Impossible")
import numpy as np

i = list(map(int, input().split()))
N = i[0]
R = i[1]

if N>=10:
    print(R)
else:
    print(R-(100*(10-N))

### FIXED CODE ###

import numpy as np

i = list(map(int, input().split()))
N = i[0]
R = i[1]

if N>=10:
    print(R)
else:
    print(R+(100*(10-N)))
N = int(input())
A = list(map(int, input().split()))
X = [A[0]]
for i in range(1, N):
  if A[i] != A[i-1]:
    X.append(A[i])
B, C = [], []
n = len(X)
status = 0
result = 1000
now_m = 1000
k = 0
if X[0]>X[1]:
  B.append(0)
else:
  C.append(0)
for i in range(1, n-1):
  if X[i-1]<X[i] and X[i]>X[i+1]:
    B.append(i)
for i in range(1, n-1):
  if X[i-1]>X[i] and X[i]<X[i+1]:
    C.append(i)
if X[n-2]<X[n-1]:
  B.append(n-1)
else:
  C.append(n-1)
S = set(B+C)
for s in S:
    if status==0:
        k = now_m//X[s]
        now_m -= k*X[s]
        status = 1
    else:
        now_m += k*X[s]
        result = max(result, now_m)
        k = 0
        status = 0
print(result)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
X = [A[0]]
for i in range(1, N):
  if A[i] != A[i-1]:
    X.append(A[i])
S = []
n = len(X)
if n==1:
  print(1000)
else:
  status = 0
  result = 1000
  now_m = 1000
  k = 0
  if X[0]<X[1]:
    S.append(0)
  for i in range(1, n-1):
    if (X[i-1]<X[i] and X[i]>X[i+1]) or (X[i-1]>X[i] and X[i]<X[i+1]):
      S.append(i)
  if X[n-2]<X[n-1]:
    S.append(n-1)
  for s in S:
    if status==0:
        k = now_m//X[s]
        result = max(result, now_m)
        now_m -= k*X[s]
        status = 1
    else:
        now_m += k*X[s]
        result = max(result, now_m)
        k = 0
        status = 0
  print(result)
K, X = map(int, input().split())
if K*500 <X:
    print('NO')
  else:
    print('Yes')

### FIXED CODE ###

k,x= map(int, input().split())

if 500*k>=x:
    print('Yes')
else:
    print('No')
a, b, x = map(int, input().split())
import math
if x  <= 0.5 * b * a **2:
  print(90 - math.degrees(math.atan(2*x / (a * b ** 2))))
else:
  print(90 - math.degrees(math.atan(a/  (2*(b-x/(a**2)))  )))

### FIXED CODE ###

a, b, x = map(int, input().split())
import math
if x == b * a** 2:
  print(0)
elif x  <= 0.5 * b * a **2:
  print(round(90 - math.degrees(math.atan(2*x / (a * b ** 2))),10))
else:
  print(round(90 - math.degrees(math.atan(a/  (2*(b-x/(a**2)))  )),10))
import numpy
n, k= map(int,input().split())
ps = list(map(int, input().split()))
pon=ps
i=1
for a in range(k-1):
    ps1 = numpy.roll(pon, -i)  # = np.ndarray([ x[1], x[2], ..., x[n-1], x[0] ])
    ps = ps + ps1
    i+=1

    
if not k==1:num=ps.tolist().index(ps[:-(k-1)].max())
ans=0
for a in range(k):
    ans+=sum(range(1,pon[num+a]+1))/pon[num+a]
    
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
 
p = list(map(int,input().split()))
 
s = [0]*(n+1)
 
for i in range(n):
    s[i+1] = s[i] + (p[i] + 1)/2
 
res = 0
 
for i in range(n-k+1):
    res = max(res, s[i+k] - s[i])
    
print("{:.10f}".format(res))
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(map(str, input().split()))
def pl(a): print(" ".join(list(map(str, a))))
def ma():return map(int,input().split())
from collections import accumulate as acc
import operator as op
import copy as cp
import math 

n=ri()
s=input()
cnt=n
if n==1:
  print(1)
  
else:
  for i in range(n-1):
    if s[i]==s[i+1]:
      cnt-=1
  print(cnt)


### FIXED CODE ###

def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(map(str, input().split()))
def pl(a): print(" ".join(list(map(str, a))))
def ma():return map(int,input().split())
from itertools import accumulate as acc
import operator as op
import copy as cp
import math 

n=ri()
s=input()
cnt=n
if n==1:
  print(1)
  
else:
  for i in range(n-1):
    if s[i]==s[i+1]:
      cnt-=1
  print(cnt)
import math
n=int(input())
a=[int(x) for x in input().split()]
a_log=[]
for i in a:
  if i == 0:
    i+=10**(-1000000)
  i_log=math.log10(i)
  a_log.append(i_log)
  
if sum(a_log)>18:
  print("-1")
else:
  for i in range(n-1):
  	a[i+1]*=a[i]
  if a[n-1]>10**18:
    print("-1")
  else:
    print(a[n-1])

### FIXED CODE ###

import math
n=int(input())
a=[int(x) for x in input().split()]
a_log=[]
if 0 not in a:
  for i in a:
    i_log=math.log10(i)
    a_log.append(i_log)
  
  if sum(a_log)>18:
    print("-1")
  else:
    for i in range(n-1):
  	  a[i+1]*=a[i]
    if a[n-1]>10**18:
      print("-1")
    else:
      print(a[n-1])
else:
  print("0")
import numpy as np

N = int(input())

"""
for i in range(1,int(N)+1):
    count = 0
    if i > 3:
        maxa = int(np.sqrt(i-2))
        for x in range(1,maxa):
            for y in range(1,maxa):
                for z in range(1,maxa):
                    if x*x+y*y+z*z+x*y+y*z+z*x > i:
                        break
                    if x*x+y*y+z*z+x*y+y*z+z*x == i:
                        count +=1

    print(count)

"""
ans = np.zeros(int(N))

maxa = int(np.sqrt(N-2))
for x in range(1,maxa):
    for y in range(1,x):
        for z in range(1,y):
            p = x*x+y*y+z*z+x*y+y*z+z*x
            if p<N+1:
                ans[p-1] += 6


for x in range(1,maxa):
    for y in range(1,x):
        p = x*x*3+y*y+x*y*2
        if p<N+1:
            ans[p-1] += 3
        p = y*y*3+x*x+x*y*2
        if p<N+1:
            ans[p-1] += 3

for x in range(1,maxa):
    p = x*x*6
    if p<N+1:
        ans[p-1] += 1

for x in range(0,N):
    print(int(ans[x]))

### FIXED CODE ###

import numpy as np

N = int(input())

ans = np.zeros(int(N))

if N<10001 and N>3:
    maxa = int(np.sqrt(N-2))
    for x in range(1,maxa):
        for y in range(1,x):
            for z in range(1,y):
                p = x*x+y*y+z*z+x*y+y*z+z*x
                if p<N+1:
                    ans[p-1] += 6


    for x in range(1,maxa):
        for y in range(1,x):
            p = x*x*3+y*y+x*y*2
            if p<N+1:
                ans[p-1] += 3
            p = y*y*3+x*x+x*y*2
            if p<N+1:
                ans[p-1] += 3

    for x in range(1,maxa):
        p = x*x*6
        if p<N+1:
            ans[p-1] += 1

for x in range(0,N):
    print(int(ans[x]))
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
x,y = Ch,Cw
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Cw-1][Ch-1] = 0
 
while (que or que_warp):
    while (que):
        for i in range(4):
            nx = int(que[0][1]+dx[i])
            ny = int(que[0][0]+dy[i])
            if (1<=nx<=W) and (1<=ny<=H):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((ny,nx))
                    que_warp.append((ny,nx))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][1] + ddx[i])
            ny = int(que_warp[0][0] + ddy[i])
            if (1 <= nx <= W) and (1 <= ny <= H):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((ny, nx))
        que_warp.pop(0)
 
print (res_S[Dw-1][Dh-1])


### FIXED CODE ###

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0
 
while (que or que_warp):
    l = len(que)
    while (que):
        if l > 0:
            que_warp.append(que[0])
            l -= 1
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)
 
print (res_S[Dh-1][Dw-1])
k=100
for i in range(10000):
    if k >= x:
        print(i)
        break
    k= k*1.01 // 1

### FIXED CODE ###

x=int(input())

k=100
for i in range(10000):
    if k >= x:
        print(i)
        break
    k= k*1.01 // 1
a=input()
t=-1
flag="False"
for i in range(n-1):
  if a[i]==a[i+1]:
    flag="True1"
    t=i
    break
  if i!=n-2 and a[i]==a[i+2]:
    flag="True2"
    t=i
    break
if flag=="False":
  print("{} {}".format(-1,-1))
elif flag=="True1":
  print("{} {}".format(t+1,t+2))
else flag=="True2":
  print("{} {}".format(t+1,t+2))

### FIXED CODE ###

a=input()
t=-1
flag="False"
for i in range(len(a)-1):
  if a[i]==a[i+1]:
    flag="True1"
    t=i
    break
  if i!=len(a)-2:
    if a[i]==a[i+2]:
      flag="True2"
      t=i
      break
if flag=="False":
  print("{} {}".format(-1,-1))
elif flag=="True1":
  print("{} {}".format(t+1,t+2))
else:
  print("{} {}".format(t+1,t+3))
s=input()
k=int(input())
ss=[]
for i in range(len(s)):
	ss.append(ord(s[i])-ord("a"))
i=0
while k>0:
	if i==len(s)-1:
		ss[i]=(k+ss[i])%26
		break
	elif k>=26-ss[i]:
		k-=(26-ss[i])
		ss[i]=0
	i+=1
ans=""
for i in range(len(s)):
	ans+=chr(ord("a")+ss[i])
print(ans)


if len(ans)==1:
	print(2/0)
elif len(ans)<=3:
	for i in range(10**12):
		ans+="a"

### FIXED CODE ###

s=input()
k=int(input())
ss=[]
for i in range(len(s)):
	ss.append(ord(s[i])-ord("a"))
i=0
while k>0:
	if i==len(s)-1:
		ss[i]=(k+ss[i])%26
		break
	elif k>=26-ss[i] and ss[i]!=0:
		k-=(26-ss[i])
		ss[i]=0
	i+=1
ans=""
for i in range(len(s)):
	ans+=chr(ord("a")+ss[i])
print(ans)
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def df(c, d):
        res = c // d
        if res * d > c: res -= 1
        return res

    q = int(input())
    L = [list(map(int, input().split())) for _ in range(q)]
    for a, b in L:
        if (a, b) == (1, 1):
            print(0)
            continue
        c = a * b - 1
        rc = int(c ** 0.5)
        rc -= 1
        while (rc + 1) ** 2 < c:
            rc += 1
        ans = rc * 2
        if rc * (rc + 1) > c:
            ans -= 1
        ab = set([a, b])
        for k in ab:
            ans -= 1
            if k > rc:
                y = df(c, k)
                if y == 0:
                    ans += 1
                else:
                    x = df(c, y)
                    if x != k or (df(c, k) == df(c, k - 1)):
                        ans += 1
        print(ans)

main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def df(c, d):
        res = c // d
        if res * d > c: res -= 1
        return res

    q = int(input())
    L = [list(map(int, input().split())) for _ in range(q)]
    for a, b in L:
        if (a, b) == (1, 1):
            print(0)
            continue
        c = a * b - 1
        rc = int(c ** 0.5)
        rc -= 1
        while (rc + 1) ** 2 <= c:
            rc += 1
        ans = rc * 2
        if rc * (rc + 1) > c:
            ans -= 1
        ab = [a, b]
        for k in ab:
            ans -= 1
            if k > rc:
                y = df(c, k)
                if y == 0:
                    ans += 1
                else:
                    x = df(c, y)
                    if x != k or (df(c, k) == df(c, k - 1)):
                        ans += 1
        print(ans)

main()
n = int(input())
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
# n == 1のとき、[1, 1]を返す
def factorization(n):
    
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
num = factorization(n)
kazu = []
for num_i in num:
    cnt = 1 #num_i[0]
    hoge = num_i[0]
    for i in range(num_i[1]):
        cnt *= hoge
        kazu.append(cnt)
kazu.sort()
cnt = 0
ans = 1
while ans <= n:
    ans *= kazu[cnt]
    cnt += 1
print(cnt)


### FIXED CODE ###

a, b = map(int, input().split())
print(a * b)
n=input()
a=list(input())
result = 0
for num in a:
    result += 1/int(num)
    
print(1/result)




### FIXED CODE ###

n=input()
a=str(input())
li = list(a.split(" "))
result = 0
for num in li:
    result += 1/int(num)
    
print(1/result)
a,b,c,d=map(int(),input().split())
maxa=max(a*c,a*d,b*c,b*d)
print(maxa)

### FIXED CODE ###

a,b,c,d=map(int,input().split())
maxa=max(a*c,a*d,b*c,b*d)
print(maxa)
from bisect import bisect_left as bl
from collections import deque as dq
X, Y, Z, K = map(int, input().split())
ABC = [sorted(list(map(int, input().split()))) for _ in range(3)]
AB = []
for i in range(X):
  for j in range(Y):
    AB.append(ABC[0][i] + ABC[1][j])
AB.sort(reverse = True)
res = []
for i in range(K):
  for j in range(Z):
    res.append(AB[i] + ABC[2][j])
res.sort(reverse = True)
for i in range(K):
  print(res[i])

### FIXED CODE ###

from bisect import bisect_left as bl
from collections import deque as dq
X, Y, Z, K = map(int, input().split())
ABC = [sorted(list(map(int, input().split()))) for _ in range(3)]
AB = []
for i in range(X):
  for j in range(Y):
    AB.append(ABC[0][i] + ABC[1][j])
AB.sort(reverse = True)
res = []
for i in range(min(K, X * Y)):
  for j in range(Z):
    res.append(AB[i] + ABC[2][j])
res.sort(reverse = True)
for i in range(K):
  print(res[i])