Harryxun/stf_run huggingface dataset:
n, W = map(int, input().split())
MAX_V = 100000
dp = [0] + [10**(18)]*MAX_V
for _ in range(n):
    tmp_dp = [0]*(MAX_V+1)
    w, v = map(int, input().split())
    for sum_v in range(MAX_V+1):
        if sum_v >= v:
            tmp_dp[sum_v] = min(dp[sum_v], dp[sum_v - v] + w)
        else:
            tmp_dp[sum_v] = min(dp[sum_v], w)
    dp = tmp_dp

ans = 0
while dp[ans+1] <= W:
    ans +=1
print(ans)

### FIXED CODE ###

N, W = map(int, input().split())
MAX_V = 10**5+1
dp = [float('inf')] * MAX_V
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for sum_v in range(MAX_V)[::-1]:
        if sum_v >= v:
            dp[sum_v] = min(dp[sum_v - v] + w, dp[sum_v])
        else:
            dp[sum_v] = min(dp[sum_v], w)
ans = 0
for v in range(MAX_V)[:: -1]:
    if dp[v] <= W:
        ans = v
        break
print(ans)
while 1:
  a,op,b = map(raw_input().split())
  if op == "+":
    print "%d" %(a + b)
  elif op == "-":
    print "%d" %(a - b)
  elif op == "*":
    print "%d" %(a * b)
  elif op == "/":
    print "%d" %(a / b)
  else:
    break
  

### FIXED CODE ###

while 1:
  s = raw_input().split()
  a, b =int(s[0]), int(s[2])
  op = s[1] 

  if op == "+":
    print "%d" %(a + b)
  elif op == "-":
    print "%d" %(a - b)
  elif op == "*":
    print "%d" %(a * b)
  elif op == "/":
    print "%d" %(a / b)
  else:
    break
l=len(s)
a=[]
z=[]
ans=0
for i in range(l):
    if s[i]=="A":
        a.append(i)
    elif s[i]=="Z":
        z.append(i)

for i in range(len(a)):
    for j in range(len(z)):
        if abs(z[j]-a[i]+1)>=ans:
            ans=abs(z[j]-a[i]+1)

### FIXED CODE ###

s=input()
l=len(s)
a=[]
z=[]
ans=0
for i in range(l):
    if s[i]=="A":
        a.append(i)
    elif s[i]=="Z":
        z.append(i)

ans=(max(z)-min(a)+1)

print(ans)
from collections import defaultdict, deque

n, m = [int(i) for i in raw_input().split()]

# children = defaultdict(list)
parents = defaultdict(list)

for _ in range(m):
    u, v = [int(i) for i in raw_input().split()]
    # children[u-1].append(v-1)
    parents[v-1].append(u-1)

def longest_path(children, parents, n):
    f = [None] * n
    targets = [x for y in children.values() for x in y]
    starts = [v for v in range(n) if v not in targets]

    # print f
    for i in range(n):
        get_f(children, parents, f, i)

    # print f
    return max(f)

def get_f(children, parents, f, i):
    if f[i] != None:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], get_f(children, parents, f, v) + 1)

    return f[i]

# def longest_path(children, parents, n):
#     targets = [x for y in children.values() for x in y]
#     starts = [v for v in range(n) if v not in targets]
#     f = [None] * n
    
#     Q = deque([])
#     for v in starts:
#         f[v] = 0
#         Q.append((v, 0))

#     output = 0
#     while len(Q) > 0:
#         node, length = Q.pop()
#         output = max(output, length)
#         for v in children[node]:
#             Q.append((v, length+1))

#     return output

print(longest_path(children, parents, n))


### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

n, m = [int(i) for i in raw_input().split()]
parents = defaultdict(list)

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):
    if i < 0 or i >= len(f):
        return 0

    if f[i] != -1:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], calc_f(parents, f, v)+1)

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

if len(f) == 0:
    print 0
else:
    print max(f)
n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
    a[i].reverse()

ans = n
used = set()
for i in range(m):
    count = [0]*(m+1)
    for j in range(n):
        count[a[j][-1]] += 1

    ans = min(max(count), ans)
    num = count.index(max(count))
    used.add(num)
    for j in range(n):
        while True:
            if a[j][-1] in used:
                a[j].pop()
            else:
                break

print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
    a[i].reverse()

ans = n
used = set()
for i in range(m):
    count = [0]*(m+1)
    for j in range(n):
        count[a[j][-1]] += 1

    ans = min(max(count), ans)
    num = count.index(max(count))
    used.add(num)
    for j in range(n):
        while len(a[j]) > 0:
            if a[j][-1] in used:
                a[j].pop()
            else:
                break

print(ans)
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N = int(input())
S = input()
T = input()
ans = 2*N
for i in range(N,-1,-1):
    # ST = S[:i] + T
    print(ST,ST[:i],ST[i:])
    if ST[:N]==S and ST[-N:]==T:
        ans = min(len(ST),ans)

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


### FIXED CODE ###

# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N = int(input())
S = input()
T = input()
ans = 2*N
for i in range(N,-1,-1):
    ST = S[:i] + T
    # print(ST,ST[:i],ST[i:])
    if ST[:N]==S and ST[-N:]==T:
        ans = min(len(ST),ans)

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))
n = int(input())
a = []
nowmin = a[0]
for i in range(n):
  a.append(int(input()))
ans = a[1]-a[0]
for i in range(n-1):
 if a[i] < nowmin:
  k = max(a[i+1:]) - a[i]
  if k > ans:
    ans =  k
    
print(ans)



### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
nowmin = a[0]
nowmax = max(a[1:])
ans = nowmax - nowmin
for i in range(n-1):
  if a[i] == nowmax:
    nowmax = max(a[i+1:])
  if a[i] < nowmin:
    k = nowmax - a[i]
    if k > ans:
      ans =  k
      nowmin = a[i]


print(ans)
N,M = map(int,input().split())

if n == m:
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

N,M = map(int,input().split())
 
if N == M:
  print("Yes")
else:
  print("No")
a,b=map(int,input().split())
s=0
s += b
s += b*(10**len(a))
for i in range(320):
    if s==i*i:
        print(i)
        exit()


### FIXED CODE ###

a,b=input().split()
s=0
s += int(b)
s += int(a)*(10**len(b))
for i in range(320):
    if s==i*i:
        print('Yes')
        exit()
print('No')
n = int(input())
num = list(map(int, input().split()))

cnt = 0
for i in range( n // 2 + 1):
    print((2*i + 1))
    if num[2*i] % 2 == 1:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 0
for i in range((n + 1)// 2):
    if num[2*i] % 2 == 1:
        cnt += 1
print(cnt)
import sys

N = sys.argv[1]
if N == 0:
  print(0)
else:
  print(((N - 1) / 1000) + 1) * 1000 - N)

### FIXED CODE ###

N = 0
try:
  N = int(input())
except:
  pass
if N == 0:
  print(0)
else:
  print((((N - 1) // 1000) + 1) * 1000 - N)
from math import gcd
mod = 10**9 +7
n = int(input())
a = list(map(int, input().split()))
r = a[0]
for i in range(1, n):
    r = r*a[i]//gcd(r, a[i])
result = 0
for i in a:
    result = (result+r//i)%mod
print(result)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

mod = 10**9 + 7
memo = defaultdict(int)
base = 0
for i in a:
    base = (base+pow(i, mod-2, mod))%mod
    num = i
    for j in range(2, int(i**.5)+1):
        if num%j==0:
            c = 0
            while num%j==0:
                num //= j
                c += 1
            memo[j] = max(memo[j], c)
    if num != 1:
        memo[num] = max(memo[num], 1)
k = 1
for s, t in memo.items():
    k = (k*pow(s, t, mod))%mod

print((k*base)%mod)
N=int(input())
josi = list(map(int,input().split()))
n=1
m=0
count=0
while n<=N:
  m=n
  while m<N:
    if josi[m]=n:
      count = count+1
    m=m+1
  print(count)
  m=0
  count=0

      

### FIXED CODE ###

N=int(input())
josi = list(map(int,input().split()))
count=[0]*N
n=0
while n<N-1:
  count[josi[n]-1] =count[josi[n]-1]+1
  n=n+1
n=0
while n<N:
  print(count[n])
  n=n+1
from math import factorial

n, m = [int(i) for i in input().split()]
mod = 10e9 + 7

ans = 0
diff = abs(n - m)
if diff == 0:
    ans = (factorial(n) ** 2) * 2 % mod
elif diff == 1:
    ans = factorial(n) * factorial(m) % mod
print(ans)


### FIXED CODE ###

from math import factorial

n, m = [int(i) for i in input().split()]
mod = 10 ** 9 + 7

ans = 0
diff = abs(n - m)
if diff == 0:
    ans = (factorial(n) ** 2) * 2 % mod
elif diff == 1:
    ans = factorial(n) * factorial(m) % mod
print(ans)
import collections
def solve(n, a_list):

    count = collections.Counter()
    for i in a_list:
        count[i // 400] += 1

    min_value = len([i for i in count.keys() if i != 8])
    max_value = min_value + count[8]
    return "{0} {1}".format(min_value, max_value)

if __name__ == "__main__":
    n = int(input())
    a_list = [int(input()) for i in range(n)]
    print(solve(n, a_list))


### FIXED CODE ###

import collections
def solve(n, a_list):

    count = collections.Counter()
    for i in a_list:
        no = 8 if i // 400 >= 8 else i // 400
        count[no] += 1

    tmp = len([i for i in count.keys() if i != 8])
    max_value = tmp + count[8]
    min_value = 1 if tmp == 0 else tmp

    return "{0} {1}".format(min_value, max_value)

if __name__ == "__main__":
    n = int(input())
    a_list = [int(i) for i in input().split()]
    print(solve(n, a_list))
def gen_switch(i, n):
    ret = []
    str_bin = format(i, '011b')
    for k in range(n):
        ret.append(int(str_bin[-k-1]))
    ret.reverse()
    return ret


input_line = raw_input()
splitted_line = input_line.split(" ")
n = int(splitted_line[0])
m = int(splitted_line[1])


my_mtx = []

for i in range(m):
    my_list = [0] * n
    splitted_line = raw_input().split(" ")

    for j in range(len(splitted_line)):
        if j != 0:
            my_list[int(splitted_line[j])-1] = 1

    my_mtx.append(my_list)

splitted_line = raw_input().split(" ")
my_list = []

for item in splitted_line:
    my_list.append(int(item))


count = 0

# print(my_list)

for i in range(2 ** n):
    my_switch = gen_switch(i, n)
    for j in range(m):
        my_sum = 0
        for k in range(len(my_switch)):
            my_sum = my_sum + (my_switch[k] * my_mtx[j][k])
        if my_sum % 2 != my_list[j]:
            break
        if j == m - 1:
            count = count + 1

print(count)


### FIXED CODE ###

def gen_switch(i, n):
    ret = []
    str_bin = format(i, '011b')
    for k in range(n):
        ret.append(int(str_bin[-k-1]))
    ret.reverse()
    return ret


input_line = input()
splitted_line = input_line.split(" ")
n = int(splitted_line[0])
m = int(splitted_line[1])


my_mtx = []

for i in range(m):
    my_list = [0] * n
    splitted_line = input().split(" ")

    for j in range(len(splitted_line)):
        if j != 0:
            my_list[int(splitted_line[j])-1] = 1

    my_mtx.append(my_list)

splitted_line = input().split(" ")
my_list = []

for item in splitted_line:
    my_list.append(int(item))


count = 0

# print(my_list)                                                                                                                                                                                                              

for i in range(2 ** n):
    my_switch = gen_switch(i, n)
    for j in range(m):
        my_sum = 0
        for k in range(len(my_switch)):
            my_sum = my_sum + (my_switch[k] * my_mtx[j][k])
        if my_sum % 2 != my_list[j]:
            break
        if j == m - 1:
            count = count + 1

print(count)
n=int(input())
if x>=400 and x<=599:
    print(8)
    exit()
if x>=600 and x<=799:
    print(7)
    exit()
if x>=800 and x<=999:
    print(6)
    exit()
if x>=1000 and x<=1199:
    print(5)
    exit()
if x>=1200 and x<=1399:
    print(4)
    exit()
if x>=1400 and x<=1599:
    print(3)
    exit()
if x>=1600 and x<=1799:
    print(2)
    exit()
if x>=1800 and x<=1999:
	print(1)
  	exit()

### FIXED CODE ###

x=int(input())
if x>=400 and x<=599:
    print(8)
    exit()
if x>=600 and x<=799:
    print(7)
    exit()
if x>=800 and x<=999:
    print(6)
    exit()
if x>=1000 and x<=1199:
    print(5)
    exit()
if x>=1200 and x<=1399:
    print(4)
    exit()
if x>=1400 and x<=1599:
    print(3)
    exit()
if x>=1600 and x<=1799:
    print(2)
    exit()
if x>=1800 and x<=1999:
    print(1)
    exit()
def main(): 
    
    N = int(input())
    h = list(map(int, input().split()))

    dp = [10000 for _ in range(n)]

    dp[0] = 0

    for i in range(1, N):
        dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i -1]))
        if i > 1:
            dp[i] = min(dp[i], dp[i -2] + abs(h[i] - h[i-2]))

    print(dp[N-1])





if __name__ == "__main__":
    main() 

### FIXED CODE ###

def main(): 
    
    N = int(input())
    h = list(map(int, input().split()))

    dp = [0 for _ in range(N)]

    for i in range(1,N):
        if i == 1:
            dp[i] = abs(h[i] - h[i-1])
        else:
            dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]))

    print(dp[N-1])

    
if __name__ == "__main__":
    main()
N = int(input())
res = 0
for i in range(N):
  x, y = input().split()
  if y == 'JPY':
    res += int(x)
  else:
    res += int(x) * 380000
    
print(res)

### FIXED CODE ###

N = int(input())
res = 0
for i in range(N):
  x, y = input().split()
  if y == 'JPY':
    res += int(x)
  else:
    res += float(x) * 380000
    
print(res)
li = input().split()
ans = [li[0]+li[1],li[0]-li[1],li[1]-li[0],li[0]*li[1]].sort()
print(ans[3])

### FIXED CODE ###

li = list(map(int,input().split()))
ans = [li[0]+li[1],li[0]-li[1],li[0]*li[1]]
ans.sort()
print(ans[2])
A = list(map(int,input().split( )))
a=A[0]
b=A[1]
k=A[2]
x=0
for h in range(1,51):
	i=50-h
	if a%i + b%i:
		continue
	x=x+1
	print(i)
	if x == k:
		break
print(i)

### FIXED CODE ###

A = list(map(int,input().split( )))
a=A[0]
b=A[1]
k=A[2]
x=0
for h in range(100):
	i= (b if a>b else a)-h
	if a%i + b%i:
		continue
	x=x+1
	if x == k:
		break
print(i)
import sys
N,K=map(int,input().split())
alist=list(map(int,input().split()))
#print(alist)

memo={}
def num_cut(x):
  if x in memo:
    return memo[x]
  
  ret=0
  for a in alist:
    ret+=-(-(a-x)//x)
    
  memo[x]=ret
  return ret

#for i in range(1,max(alist)):
#  print(i,num_cut(i))

l=1
r=max(alist)+1
while l<=r:
  mid=(l+r)//2
  #print(l,mid,r)
  
  if num_cut(mid-1)>K and num_cut(mid)<=K:
    print(mid)
    break
  elif num_cut(mid)<=K:
    r=mid
  else:
    l=mid

### FIXED CODE ###

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

def num_cut(x):
  if x==0:
    return float("inf")
  
  ret=0
  for a in alist:
    ret+=-(-(a-x)//x)
  return ret

#for i in range(1,max(alist)):
#  print(i,num_cut(i))

l=1
r=max(alist)+1
while l<=r:
  mid=(l+r)//2
  #print(l,mid,r)
  
  if num_cut(mid-1)>K and num_cut(mid)<=K:
    print(mid)
    break
  elif num_cut(mid)<=K:
    r=mid
  else:
    l=mid
a, b, c = map(int, input().split())
 if a < b < c:
   print("Yes")
 else:
   print("No")

### FIXED CODE ###

a, b, c = map(int, input().split())
if a < b < c:
  print("Yes")
else:
  print("No")
# -*- coding:utf-8 -*-

def calc(S, T):
    # 差を計算する
    ans = 0
    for i in range(len(S)):
        if S[i] != T[i]:
            ans += 1
    return ans


def solve():
    s = input()
    S = [moji for moji in s]
    T = input()

    # 文字の置き換えをして、差が減ってなかったら無理？
    pre_diff = calc(S, T)
    while True:
        for i in range(len(S)):
            if S[i] != T[i]:
                c1 = S[i]
                c2 = T[i]
                break
        
        for i in range(len(S)):
            if S[i] == c1:
                S[i] = c2
            elif S[i] == c2:
                S[i] = c1
        
        # 差を計算する
        diff = calc(S, T)
        if diff == 0:
            break
        elif diff < pre_diff:
            pre_diff = diff
            continue
        else:
            print("No")
            return
    print("Yes")





if __name__ == "__main__":
    solve()

### FIXED CODE ###

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

def calc(S, T):
    # 差を計算する
    ans = 0
    for i in range(len(S)):
        if S[i] != T[i]:
            ans += 1
    return ans


def solve():
    s = input()
    S = [moji for moji in s]
    T = input()

    # 文字の置き換えをして、差が減ってなかったら無理？
    
    diff = calc(S, T)
    if diff == 0:
        print("Yes")
        return
    pre_diff = diff

    while True:
        # c1, c2を決める
        for i in range(len(S)):
            if S[i] != T[i]:
                c1 = S[i]
                c2 = T[i]
                break
        
        # 文字を置き換える
        for i in range(len(S)):
            if S[i] == c1:
                S[i] = c2
            elif S[i] == c2:
                S[i] = c1
        
        # 差を計算する
        diff = calc(S, T)
        if diff == 0:
            break
        elif diff < pre_diff:
            pre_diff = diff
            continue
        else:
            print("No")
            return
    print("Yes")





if __name__ == "__main__":
    solve()
#D
import math ,sys
x = int(input())
for a in range(math.ceil(math.log10(x))):
    for b in range(-10 ** 9//2, 10 ** 9//2):
        if s ** 5 - b ** 5 == x:
            print(a, b)
            sys.exit()

### FIXED CODE ###

#D
import sys
x = int(input())

#-118<a<119 -119<b<118で全捜索
for a in range(-118, 120):
    for b in range(-119, 119):
        if a ** 5 - b ** 5 == x:
            print(a, b)
            sys.exit()
a,b,c=[str(i) for i in input().split()]
if a[-1]==b[1] and b[-1]==c[1]:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

a,b,c=[str(i) for i in input().split()]
if a[-1]==b[0] and b[-1]==c[0]:
  print('YES')
else:
  print('NO')
# coding: utf-8
# Your code here!

n,m = map(int, input.split())

if n == m:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

# coding: utf-8
# Your code here!

n,m = map(int, input().split())

if n == m:
    print('Yes')
else:
    print('No')
n=int(input())
l=sorted(list(map(int,input().split())))
for i,x in enumerate(l):
  l[i]=format(x,'63b')
memo=[0]*63
for i in range(63):
  for j in range(n):
    if l[j][i]=='1':
      memo[-i-1]+=1
now=1
ans=0
mod=10**9+7
for x in memo:
  ans+=(now*x*(n-x))%mod
  now*=2
print(ans%mod)


### FIXED CODE ###

print('win' if sum(list(map(int,input().split())))<22 else 'bust')
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7

if all(a<0 for a in A):
    A.sort(reverse=K%2==0)
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
ans = 1
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

for v in ng:
    ans *= v
    ans %= MOD
for v in pz:
    ans *= v
    ans %= MOD
if len(ng)%2 == 0:
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is not None and b is not None) or (c is not None and d is not None):
    print(ans)
    exit()

if a is None or b is None:
    ans *= d * pow(c,-1,MOD)
elif c is None or d is None:
    ans *= a * pow(b,-1,MOD)
else:
    if a*c > b*d:
        ans *= a * pow(b,-1,MOD)
    else:
        ans *= d * pow(c,-1,MOD)
ans %= MOD
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7

if all(a>=0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if all(a<0 for a in A):
    A.sort(reverse=K%2==0)
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if N==K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

if len(ng)%2 == 0:
    ans = 1
    for v in ng:
        ans *= v
        ans %= MOD
    for v in pz:
        ans *= v
        ans %= MOD
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is None or b is None) and (c is None or d is None):
    assert False

ans = 1
if a is None or b is None:
    ans = d
    for v in ng[:-1]:
        ans *= v
        ans %= MOD
    for v in pz:
        ans *= v
        ans %= MOD
elif c is None or d is None:
    ans = a
    for v in ng:
        ans *= v
        ans %= MOD
    for v in pz[:-1]:
        ans *= v
        ans %= MOD
else:
    if a*c > b*d:
        ans = a
        for v in ng:
            ans *= v
            ans %= MOD
        for v in pz[:-1]:
            ans *= v
            ans %= MOD
    else:
        ans = d
        for v in ng[:-1]:
            ans *= v
            ans %= MOD
        for v in pz:
            ans *= v
            ans %= MOD
ans %= MOD
print(ans)
# -*- coding: utf-8 -*-

def get_digits_sum(val_str):
    digits_sum = 0
    for i in range(len(val_str)):
        digits_sum += int(val_str[i])

    return digits_sum

N = int(input())


for i in range(2, N, 1):
    A = i
    B = N - i
    a_sum = get_digits_sum(str(A))
    b_sum = get_digits_sum(str(B))
    if i==2:
        sum_min = a_sum + b_sum
    elif sum_min > a_sum + b_sum:
        sum_min = a_sum + b_sum
        
print(sum_min)

### FIXED CODE ###

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

def get_digits_sum(val_str):
    digits_sum = 0
    for i in range(len(val_str)):
        digits_sum += int(val_str[i])

    return digits_sum

N = int(input())

if N==2:
    sum_min = 2

for i in range(2, N, 1):
    A = i
    B = N - i
    a_sum = get_digits_sum(str(A))
    b_sum = get_digits_sum(str(B))
    if i==2:
        sum_min = a_sum + b_sum
    elif sum_min > a_sum + b_sum:
        sum_min = a_sum + b_sum
        
print(sum_min)