Harryxun/stf_run huggingface dataset:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

n,k,l=map(int,input().split())
uf1=UnionFind(n)
uf2=UnionFind(n)
for _ in range(k):
  u,v=map(int,input().split())
  uf1.unite(u-1,v-1)
for _ in range(k):
  u,v=map(int,input().split())
  uf2.unite(u-1,v-1)
ans=[]
for i in range(n):
  x=set(uf1.members(i))&set(uf2.members(i))
  ans.append(len(x))
print(*ans)


### FIXED CODE ###

from collections import defaultdict
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

n,k,l=map(int,input().split())
uf1=UnionFind(n)
uf2=UnionFind(n)
for _ in range(k):
  u,v=map(int,input().split())
  uf1.unite(u-1,v-1)
for _ in range(l):
  u,v=map(int,input().split())
  uf2.unite(u-1,v-1)
d=defaultdict(int)
for i in range(n):
  d[(uf1.find(i),uf2.find(i))]+=1
ans=[d[(uf1.find(i),uf2.find(i))] for i in range(n)]
print(*ans)
b = input()
let = 'ATGC'
prev = b[0]
if prev in let:
    leng = 1
lens = []
for i in range(1,len(b)):
    if leng == 0 and b[i] in let:
        leng = 1
    if b[i] in let and prev in let:
        print(b[i])
        leng += 1
    else:
        lens.append(leng)
        leng = 0
    prev = b[i]

print(max(lens))

### FIXED CODE ###

b = input()
let = 'ATGC'
prev = b[0]
high = 0
leng = 0
stop = False

if prev in let:
    leng = 1
    high = 1
    
for i in range(1,len(b)):
    if leng == 0 and b[i] in let:
        leng = 1
    if b[i] in let and prev in let:
        leng += 1
        stop = False
    else:
        stop = True
        if leng > high:
            high = leng
            leng = 0
    prev = b[i]
    
if not stop:
    if leng > high:
        high = leng
    
print(high)
number = int(input().split())
if (number[1] * 10 + number [2]) % 4 == 0:
    print(YES)
else:
    print(NO)


### FIXED CODE ###

number = input().split()
number = [int(i) for i in number]
if (number[1] * 10 + number [2]) % 4 == 0:
    print("YES")
else:
    print("NO")
#dpg
#根になってるものからsearch
#1.行き先にいくための現時点での最長経路と根から来た場合の経路を比較
#2.その枝はもう見なくて良いので削除(行き先に入る枝のカウントを1減らす)
#入る枝がなくなったら根として考えてそっからまたsearch
#計算量はsearchの回数分(m+n)
n, m = map(int, input().split())
dest = [[] for _ in range(n)]
comein = [0 for _ in range(n)]
ro = [True for _ in range(n)]
dp = [0 for _ in range(n)]
for _ in range(m):
	x, y = map(int, input().split())
	dest[x-1].append(y-1)
	comein[y-1] += 1
	ro[y-1] = False

def search(leaf):
	global dp
	for i in dest[leaf]:
		comein[i] -= 1
		dp[i] = max(dp[i], dp[leaf] + 1)
		if comein[i] == 0:
			search(i)
	return

for j in range(n):
	if ro[j] == True:
		search(j)

print(max(dp))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
dest = [[] for _ in range(n)]
comein = [0 for _ in range(n)]
ro = [True for _ in range(n)]
dp = [0 for _ in range(n)]
for _ in range(m):
	x, y = map(int, input().split())
	dest[x-1].append(y-1)
	comein[y-1] += 1
	ro[y-1] = False

def search(leaf):
	global dp
	for i in dest[leaf]:
		comein[i] -= 1
		dp[i] = max(dp[i], dp[leaf] + 1)
		if comein[i] == 0:
			search(i)
	return

for j in range(n):
	if ro[j] == True:
		search(j)

print(max(dp))
a, b, c = list(map(int, input().split(' ')))
a_m = a%10**9
b_m = b%10**9
c_m = c%10**9
sub = (c_m - a_m - b_m)&mod10**9

if 4*a_m*b_m < sub*sub:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

a, b, c = list(map(int, input().split(' ')))
sub = c-a-b
if sub > 0 and 4*a*b < sub*sub:#計算が成立するためには、c-a-b > 0が必要
        print('Yes')
else:
    print('No')
h,a=map(int, input().solit())
if h%a==0:
  print(h/a)
else:
  print(h//a+1)

### FIXED CODE ###

h,a=map(int,input().split())
if h%a==0:
  print(int(h/a))
else:
  print(int(h//a)+1)
import sys
sys.setrecursionlimit(10**7)

n = int(input())
info = []
for _ in range(n-1):
    c, s, f = map(int, input().split())
    info.append([c, s, f])
# print(info)

def func(i, low):
    if i == low:
        return info[i][1] + info[i][0]

    return func2(func(i-1, low), info[i][2], info[i][1]) + info[i][0]

def func2(n, f, s):
    if n <= s:
        return s
    if n % f == 0:
        return n
    else:
        return n//f * f + f

# print(func(n-2, 0))
for i in range(n):
    if i == n-1:
        print(0)
    print(func(n-2, i))

### FIXED CODE ###

n = int(input())
C = []
S = []
F = []
for _ in range(n-1):
    c, s, f = map(int, input().split())
    C.append(c)
    S.append(s)
    F.append(f)

def f(n, s, f):
    if n <= s:
        return s
    if n % f == 0:
        return n
    else:
        return n // f * f + f

for i in range(n-1):
    now = S[i] + C[i]
    for j in range(i+1, n-1):
        now = f(now, S[j], F[j]) + C[j]
    print(now)
print(0)
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_sum = [0]
for i in range(N):
    A_sum.append(A_sum[i] + A[i])
B_sum = [0]
for i in range(N):
    B_sum.append(B_sum[i] + B[i])
B_sum.append(10**10)

res = 0
for i in range(len(A_sum)):
    low = 0
    high = len(B_sum)
    while high - low > 1:
        mid = (low + high) // 2
        if A_sum[i] + B_sum[mid] <= K:
            low = mid
        else:
            high = mid
    if A_sum[i] + B_sum[low] <= K:
        res = max(res, i + low)

print(res)


### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_sum = [0]
for i in range(N):
    A_sum.append(A_sum[i] + A[i])
B_sum = [0]
for i in range(M):
    B_sum.append(B_sum[i] + B[i])
B_sum.append(10**10)

res = 0
for i in range(len(A_sum)):
    low = 0
    high = len(B_sum)
    while high - low > 1:
        mid = (low + high) // 2
        if A_sum[i] + B_sum[mid] <= K:
            low = mid
        else:
            high = mid
    if A_sum[i] + B_sum[low] <= K:
        res = max(res, i + low)

print(res)
s = input()

print(chr(ord(s) + 1)


### FIXED CODE ###

s = input()

print(chr(ord(s) + 1))
s = input()
s = list(s)
i = 0
j = 0
flg =0

if len(s) >1:
    while(1):
        for i in range(len(s)+1):
            if s[i] != s[i+1]:
                s.pop(i+1)
                s.pop(i)
                j+=2
                break
            elif len(s) == 2:
                flg = 1
                break
        
        if len(s) ==0 or flg==1:
            break
        
print(j)

### FIXED CODE ###

s = input()
a = s.count('1')
b = s.count('0')
print(min(a,b)*2)
n, k, c = map(int, input().split())
s = input()


if s[i] == "o":
    if i+c+1 <= n-1:
        if s[i+c+1] == "x" and s[i+1] == "x":
            print(i+1)


### FIXED CODE ###

import sys
n, k, c = map(int, input().split())
s = input()


count = 0
i = 0
ansleft = set()
while i < n:
    if s[i] == "o":
        ansleft.add(i+1)
        i += c+1
        count += 1
    else:
        i += 1

if count >= k+1:
    sys.exit()


ansright = set()
s = s[::-1]
i = 0
while i < n:
    if s[i] == "o":
        ansright.add(n-i)
        i += c+1
    else:
        i += 1

ans = ansright&ansleft
ans = list(ans)
ans.sort()
for i in ans:
    print(i)
def month(num):
    if 0 < num <= 12:
        return True
    else:
        return False


S = input()
first = int(S[:2])
second = int(S[2:])

if month(first)
    if month(second):
        print('AMBIGUOUS')
    else:
        print('MMYY')

elif not month(first) and month(second):
    print('YYMM')

else:
    print('NA')





### FIXED CODE ###

def month(num):
    if 0 < num <= 12:
        return 1
    else:
        return 0


S = input()
first = int(S[:2])
second = int(S[2:])

if month(first) == 1 and month(second) == 1:
    print('AMBIGUOUS')

elif month(first) == 1 and month(second) == 0:
    print('MMYY')

elif month(first) == 0 and month(second) == 1:
    print('YYMM')

else:
    print('NA')
[print('{}x{}={}').format(i, j, i * j) for j in range(1, 10) for i in range(1, 10)]

### FIXED CODE ###

a = range(1, 10)
[print('{}x{}={}'.format(i, j, i * j)) for i in a for j in a]
H,W,M = map(int,input().split())
P = [0]*(H+1)
Q = [0]*(W+1)
#A = [[0 for j in range(W+1)] for i in range(H+1)]
for k in range(M):
  a,b = map(int,input().split())
  P[a] += 1
  Q[b] += 1
  #A[a][b] = 1
#print(P,Q,A,Pmax,Qmax,ans)
Pindex = [i for i, v in enumerate(P) if v == max(P)]
Qindex = [i for i, v in enumerate(Q) if v == max(Q)]
Pmax = P[Pindex[0]]
Qmax = Q[Qindex[0]]
ans = Pmax+Qmax-1
key = 0
for x in Pindex:
  for y in Qindex:
    if A[x][y] == 0:
      ans += 1
      key = 1
      break
  if key == 1:
    break
print(ans)


### FIXED CODE ###

H,W,M = map(int,input().split())
P = [0]*(H+1)
Q = [0]*(W+1)
A = set()
for k in range(M):
    a,b = map(int,input().split())
    P[a] += 1
    Q[b] += 1
    A.add((a,b))
Pmax = max(P)
Qmax = max(Q)
Pindex = []
Qindex = []
for i in range(H+1):
    if P[i] == Pmax:
        Pindex.append(i)
for i in range(W+1):
    if Q[i] == Qmax:
        Qindex.append(i)
ans = Pmax+Qmax-1
key = 0
for x in Pindex:
  for y in Qindex:
    if (x,y) not in A:
      ans += 1
      key = 1
      break
  if key == 1:
    break
print(ans)
import sys
from functools import lru_cache

N, M = map(int, input().split())
sys.setrecursionlimit(10**5)
E = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    E[x-1].append(y-1)

dp = [-1]*N


@lru_cache(maxsize=None)
def rec(v):
    if len(E[v]) == 0:
        dp[v] = 0
        return dp[v]

    for to in E[v]:
        dp[v] = max(dp[v], rec(to)+1)
    return dp[v]


for i in range(N):
    dp[i] = rec(i)
print(max(dp))

### FIXED CODE ###

import sys
N, M = map(int, input().split())
sys.setrecursionlimit(10**5)
E = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    E[x-1].append(y-1)

dp = [-1]*N


def rec(v):
    if dp[v] != -1:
        return dp[v]
    if len(E[v]) == 0:
        dp[v] = 0
        return dp[v]

    for to in E[v]:
        dp[v] = max(dp[v], rec(to)+1)
    return dp[v]


for i in range(N):
    dp[i] = rec(i)
print(max(dp))
n = int(input())
a = list(map(int, input().split()))

b = 0
by = 0
flg = 0
for i,j in enumerate(a):
	if abs(i) > abs(b):
		b = j
		by = i+1
		if j > 0:
			flg = 1
		else:
			flg = 0
ans = []
if flg == 1:
	x = min(a)
	if x < 0:
		for i in range(n):
			if a[i] != b:
				a[i] += b
				ans.append([by,i+1])
	for i in range(1,n):
		a[i] += a[i-1]
		ans.append([i,i+1])
else:
	x = max(a)
	if x > 0:
		for i in range(n,-1,-1):
			if a[i] != b:
				a[i] += b
				ans.append([by,i+1])
	for i in range(n-2,-1,-1):
		a[i] += a[i+1]
		ans.append([i+2,i+1])
print (len(ans))
for i in ans:
	print (*i)


### FIXED CODE ###

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

b = 0
by = 0
flg = 0
for i,j in enumerate(a):
	if abs(j) > abs(b):
		b = j
		by = i+1
		if j > 0:
			flg = 1
		else:
			flg = 0
ans = []
if flg == 1:
	x = min(a)
	if x < 0:
		for i in range(n):
			if a[i] != b:
				a[i] += b
				ans.append([by,i+1])
	for i in range(1,n):
		a[i] += a[i-1]
		ans.append([i,i+1])
else:
	x = max(a)
	if x > 0:
		for i in range(n-1,-1,-1):
			if a[i] != b:
				a[i] += b
				ans.append([by,i+1])
	for i in range(n-2,-1,-1):
		a[i] += a[i+1]
		ans.append([i+2,i+1])
print (len(ans))
for i in ans:
	print (*i)
N, X = map(int, input().split())
L = list(map(int, input().split()))
cnt = 1
Len = 0
for i in range(X):
	Len += L[i]
	if Len > X:
		break
	cnt += 1

print(cnt)

### FIXED CODE ###

N, X = map(int, input().split())
L = list(map(int, input().split()))
cnt = 1
Len = 0
for i in range(len(L)):
	Len += L[i]
	if Len > X:
		break
	cnt += 1

print(cnt)
n=int(input())
d=list(map(int,input().split()))
sam=0

for i in range(n):
  for j in range(n-i):
    sam=sam+(d[i]*d[j+1])

print(sam)

### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
sam=0

for i in range(n):
  for j in range(i+1,n): 
    sam=sam+(d[i]*d[j]) 
    

print(sam)
n = 10**6
mod = 10 ** 9 + 7
fact = [1]*(n+1)
rfact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod-2, mod)
for i in range(n, 0, -1):
  rfact[i-1] = r = r * i % mod

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % mod

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod

k = int(input())
s = input()

len_s = len(s)
ans = 0
for i in range(len_s,k+len_s+1):
    ans += (comb(i-1,len_s-1) * pow(25,i-len_s,mod) * pow(26,k+len_s-i,mod)) % mod
    ans %= mod
print(ans)

### FIXED CODE ###

n = 2 * (10**6) + 10
mod = 10 ** 9 + 7
fact = [1]*(n+1)
rfact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod-2, mod)
for i in range(n, 0, -1):
  rfact[i-1] = r = r * i % mod

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % mod

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod

k = int(input())
s = input()

len_s = len(s)
ans = 0
for i in range(len_s,k+len_s+1):
    ans += (comb(i-1,len_s-1) * pow(25,i-len_s,mod) * pow(26,k+len_s-i,mod)) % mod
    ans %= mod
print(ans)
w=[input() for _ in range(n)]
    chk=[]
    chk.append(w[0])
    ans='Yes'
    for i in range(1,n):
        if w[i-1][-1]!=w[i][0] or (w[i] in chk):
            ans='No'
            break
        chk.append(w[i])
    print(ans)

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

def resolve():
    n=int(input())
    w=[input() for _ in range(n)]
    chk=[]
    chk.append(w[0])
    ans='Yes'
    for i in range(1,n):
        if w[i-1][-1]!=w[i][0] or (w[i] in chk):
            ans='No'
            break
        chk.append(w[i])
    print(ans)

if __name__ == '__main__':
    resolve()
N,K = map(int, input().split())

ans = int(N/K) ** 3
if K%2 == 0:
    ans += int(N/int(K/2) - int(N/K)) ** 3
    
print(ans)


### FIXED CODE ###

N = int(input())

if (N % 2) == 0:
    ans = (N/2) ** 2
else:
    ans = int(N/2) * int(N/2 + 1)

print(int(ans))
from collections import Counter
n=int(input())
xy = [list(map(int,input().split())) for i in range(n)]
a = Counter([xy[i+1][0]-xy[i][0] for i in range(0,len(xy)-1)]).most_common()[0][0]
b = Counter([xy[i+1][1]-xy[i][1] for i in range(0,len(xy)-1)]).most_common()[0][0]

ans=0
tmp0,tmp1 = xy[0]
for i in range(1,len(xy)):
	ans += 0 if tmp0 == xy[i][0]-a  and tmp1 == xy[i][1]-b else 1
	tmp0=xy[i][0]
	tmp1=xy[i][1]
tmp = ans
ans=0
for i in range(len(xy)-1,-1,-1):
	ans += 0 if tmp0 == xy[i][0]-a and tmp1 == xy[i][1]-b else 1
	tmp0=xy[i][0]
	tmp1=xy[i][1]

print(min(ans,tmp)+1)

### FIXED CODE ###

n=int(input())
if n==1:
	print(1)
	exit()
xy = sorted([list(map(int,input().split())) for i in range(n)])
p=q=0
ans=0
dic={}
for i in range(n-1):
	for j in range(i+1,n):
		p = xy[j][0]-xy[i][0]
		q = xy[j][1]-xy[i][1]
		if (p,q) in dic:
			dic[(p,q)]+=1
		else:
			dic[(p,q)]=1
print(n-max(dic.values()))
_, *a = map(int, open(0).read.split())
ret = 1
for x in a:
  ret *= x
  if ret > 10**18:
    ret = -1
    break
print(ret)


### FIXED CODE ###

_, *a = map(int, open(0).read().split())
ret = 1
for x in sorted(a):
  ret *= x
  if ret > 10 ** 18:
    ret = -1; break
    
print(ret)
s = input()
if len(s)==len(set(s)):
  print('yes')
else:
  print('no)

### FIXED CODE ###

s = input()
if len(s)==len(set(s)):
  print('yes')
else:
  print('no')
#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int, L: "List[int]"):
    L = np.array(sorted(L))
    ct = 0
    for a in range(len(L)-2):
        for b in range(a, len(L)-1):
            ct+=((L[b] < L) & (L < L[a+b])).sum() 
    print(ct)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# import numpy as np
import bisect

def solve(N: int, L: "List[int]"):
    L = sorted(L)
    ct = 0
    for a in range(len(L)-2):
        a_ = L[a]
        for b in range(a+1, len(L)-1):
            b_in = bisect.bisect_left(L,a_+L[b]) - b -1
            if b_in > 0:
                ct+=b_in

            # print("L :{} a+Lb :{}  b_in:{}".format(L[b+1:],a_+L[b],ct))
        # ct += sum([bisect.bisect_left(L[b+1:],a_+L[b]) for b in range(a+1, len(L)-1)])
    print(ct)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()
n, m = list(map(int, input().split()))
root_list = []
for _ in range(m):
    root_list.append(list(map(int, input().split())))

answer_list = [0] * (n-1)
done_list = [1]
already_list = [1]
before_list = [1]
while len(root_list) > 0 and 0 in answer_list:
    if len(done_list) == 0:
        break
    tmp_list = []
    copy_root_list = root_list.copy()
    for num in done_list:
        for l in root_list:
            if l[1] == num:
                if answer_list[int(l[0]-2)] == 0:
                    answer_list[int(l[0]-2)] = num
                    tmp_list.append(l[0])
                    already_list.append(l[1])
                    copy_root_list.remove(l)
                else:
                    copy_root_list.remove(l)
            elif  l[0] == num:
                if answer_list[int(l[1]-2)] == 0:
                    answer_list[int(l[1]-2)] = num
                    tmp_list.append(l[1])
                    already_list.append(l[1])
                    if l in copy_root_list:
                        copy_root_list.remove(l)
                else:
                    if l in copy_root_list:
                        copy_root_list.remove(l)
    copy_root_list = [i for i in copy_root_list if (i[0] not in already_list or i[1] not in already_list)]
    root_list = copy_root_list
    done_list = tmp_list

if 0 not in answer_list:
    print("Yes")
    for i in answer_list:
        print(int(i))
else:
    print("No")
    

### FIXED CODE ###

from collections import deque

n, m = list(map(int, input().split()))
root_dict = {}

for _ in range(m):
    a, b = list(map(int, input().split()))
    if a not in root_dict:
        root_dict[a] = deque([b])
    else:
        root_dict[a].append(b)
    if b not in root_dict:
        root_dict[b] = deque([a])
    else:
        root_dict[b].append(a)

visited = [1] + [-1] * (n-1)

done = deque([1])

while done:
    x = done.popleft()
    while root_dict[x]:
        i = root_dict[x].popleft()
        if visited[i-1] < 0:
            visited[i-1] = x
            done.append(i)

if -1 in visited:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(visited[i])
n, k = map(int, input().split())
l = list(map(int, input().split()))
l = sorted(l, reverse=True)
sum = 0
for i in range(k):
        sum += l[i]
print(sum)
~

### FIXED CODE ###

n, k = map(int, input().split())
l = list(map(int, input().split()))
l = sorted(l, reverse=True)
sum = 0
for i in range(k):
        sum += l[i]
print(sum)
H, W = map(int, input().split())
items = []
black = []
for i in range(H):
    tmp = input()
    for j in range(W):
        if tmp[j] == "#":
            black.append((i, j))
    items.append(list(tmp))

que = []

for b in black:
    que.append(b)

ans = 0
d4 = [(1, 0), (0, -1), (-1, 0), (0, 1)]
next_que = que.copy()
while len(que) != H * W:
    tmp = next_que.copy()
    next_que = []
    for b in list(tmp):
        x, y = b[0], b[1]
        for d in d4:
            dx = d[0]
            dy = d[1]
            if 0 <= x + dx <= H - 1 and 0 <= y + dy <= W - 1:
                tar = items[x + dx][y + dy]
                if tar == ".":
                    next_que.append((x + dx, y + dy))
                    que.append((x + dx, y + dy))
                    items[x + dx][y + dy] = "#"
    ans += 1
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
items = []
black = []
for i in range(H):
    tmp = list(input())
    for j in range(W):
        if tmp[j] == "#":
            black.append((i, j))
    items.append(tmp)

que = []
for b in black:
    que.append(b)

ans = 0
d4 = [(1, 0), (0, -1), (-1, 0), (0, 1)]
next_que = que
while len(que) != H * W:
    tmp = next_que
    next_que = []
    for b in list(tmp):
        x, y = b[0], b[1]
        for d in d4:
            dx = d[0]
            dy = d[1]
            if 0 <= x + dx <= H - 1 and 0 <= y + dy <= W - 1:
                tar = items[x + dx][y + dy]
                if tar == ".":
                    next_que.append((x + dx, y + dy))
                    que.append((x + dx, y + dy))
                    items[x + dx][y + dy] = "#"
    ans += 1
print(ans)
S = input()
K = int(input())
l = 0
for i in S:
  if i == '1':
    l+=1
  	if l >= K:
      print(1)
      break
  else:
    print(int(i))
    break
    

### FIXED CODE ###

S = input()
K = int(input())
l = 0
for i in S:
  if i == '1':
    l+=1
    if l >= K:
      break
  else:
    break
print(i)
K = int(input())
list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
kou = list[K+1])
print(K+1,"番目の項は", kou, "です。")

### FIXED CODE ###

list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())
if K < 32:
    print(list[K-1])
else:
    print(list[31])
n = int(input())
k = int(input())
x = int(input())
y = int(input())

if n - k >= 0:
  print(k * x + (n-k) * y)
else
  print(k * x)

### FIXED CODE ###

n = int(input())
k = int(input())
x = int(input())
y = int(input())

if n - k >= 0:
  print(k * x + (n-k) * y)
else:
  print(n * x)