Harryxun/stf_run huggingface dataset:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

inv_t = [0, 1] + [0] * (N - 2)
for i in range(2, N):
    inv_t[i] = inv_t[MOD % i] * (MOD - MOD // i) % MOD

A.sort()
ans = 0
C = 1
for i in range(K, N + 1):
    ans += (A[i - 1] - A[N - i]) * C
    ans %= MOD
    C = C * i * inv_t[i - K + 1]
    C %= MOD
print(ans)


### FIXED CODE ###

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


def pow(x, t):
    if t == 0:
        return 1
    a = pow(x, t >> 1)
    return a * a * (x ** (t & 1)) % MOD


fact = [0] * N
fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD
ifact = [0] * N
ifact[N - 1] = pow(fact[N - 1], MOD - 2)
for i in range(N - 1, 0, -1):
    ifact[i - 1] = ifact[i] * i
    ifact[i - 1] %= MOD


def nCr(n, r):
    if r < 0 or r > n:
        return 0
    return fact[n] * ifact[r] * ifact[n - r] % MOD


A.sort()
ans = 0
for i in range(K, N + 1):
    C = nCr(i - 1, K - 1)
    ans += A[i - 1] * C
    ans -= A[N - i] * C
    ans %= MOD
print(ans)
import sys
b=0
a=[{},{}]
for e in sys.stdin:
 if'\n'==e:b=1
 else:c=int(e.split(',')[0]);a[b][c]=1+[0,a[b][c]][c in a[b]]
for k in sorted({*a[0]}&{*a[1]}):print(k,a[0][k]+a[1][k])


### FIXED CODE ###

import sys
b=0
a=[{},{}]
for e in sys.stdin:
 if'\n'==e:b=1
 else:c,_=e.split(',');c=int(c);a[b].setdefault(c,0);a[b][c]+=1
for k in sorted({*a[0]}&{*a[1]}):print(k,a[0][k]+a[1][k])
N,X,T = map(int,input().split())
count=0
if N <=X:
  print(T)
  break
elif N > X:
  while N > X:
    N = N - X
    count+=1
  print(T*count)

### FIXED CODE ###

N,X,T = map(int,input().split())
count = 1
while N > X:
  N = N - X
  count += 1
print(T*count)
n = int(input())
li = [list(map(int, input().split())) for _ in range(n)]
ans = []

for cx in range(101):
    for cy in range(101):
        for i in li:
            if i[2] != 0:
                ans.append([cx, cy, i[2] + abs(i[0]-cx) + abs(i[1] -cy)])
                break

for i in li:
    if len(ans) ==1:
        break
    for j in reversed (range(len(ans[:]))):
        if ans[j][2] - abs(i[0]-ans[j][0]) - abs(i[1]-ans[j][1]) != i[2]:
            ans.pop(j)


print(" ".join(map(str, ans[0])))

### FIXED CODE ###


n = int(input())
li = [list(map(int, input().split())) for _ in range(n)]
ans = []

for cx in range(101):
    for cy in range(101):
        for i in li:
            if i[2] != 0:
                ans.append([cx, cy, i[2] + abs(i[0]-cx) + abs(i[1] -cy)])
                break

for i in li:
    if len(ans) ==1:
        break
    if i[2] != 0:
        for j in reversed (range(len(ans[:]))):
            if ans[j][2] - abs(i[0]-ans[j][0]) - abs(i[1]-ans[j][1]) != i[2]:
                ans.pop(j)
    if i[2] == 0:
        for j in reversed (range(len(ans[:]))):
            if ans[j][2] - abs(i[0]-ans[j][0]) - abs(i[1]-ans[j][1]) > i[2]:
                ans.pop(j)

print(" ".join(map(str, ans[0])))
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
happiness = 0

for i in range(0, N, 1):
  if i > 0:
    if A[i-1] == (A[i]-1):
      happiness += (B[A[i]]+C[i-1])
  else:
    happiness += B[A[i]-1]
print(happiness)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
happiness = 0

for i in range(0, N, 1):
  if i > 0:
    if A[i-1] == (A[i]-1):
      happiness += (B[A[i]-1]+C[A[i]-2])
    else:
      happiness += B[A[i]-1]
  else:
    happiness += B[A[i]-1]
print(happiness)
import math
 
def hoge(x, p):
  return int((math.floor(x**(1/p)))**p)
 
x = int(input())
 
max_bp = 0
for b in range(2, x):
  for p in range(2, x):
    bp = b ** p
    if bp > x:
      break
    max_bp = max(max_bp, bp)

print(max_bp)

### FIXED CODE ###

a,b,c,d = map(int, input().split())
if abs(a-c)<=d or (abs(a-b)<=d and abs(b-c)<=d):
  print("Yes")
else:
  print("No")
import fractions
a,b,c,d = list(map(int, input().split()))
a -= 1
l = c/fractions.gcd(c,d)*d
b = b - b //c - b // d + b //l
a = a - a //c - a // d + a //l
print("{:.0f}".format(b-a))

### FIXED CODE ###

import sys
s = input()
for i in range(3):
    if s[i] == s[i+1]:
        print("Bad")
        sys.exit()
print("Good")
i = 1

while True:
  x = input()
  if x = 0:
    break
  else:
    print 'case ' + i + ': ' + x
    i += 1

### FIXED CODE ###

i = 1

while 1:
  x = input()
  if x == 0:
    break
  else:
    print 'Case %d: %d' % (i, x)
    i += 1
N=input()
slen=len(N)-1
ans=0
for i in range(2<<(slen-1)):
    k=N
    ins=0
    for j in range(slen): 
        if((i>>j)&1):
            k=k[:j+1+ins]+"+"+k[j+1+ins:]
            ins+=1
    ans+=eval(k)
print(ans)

   

### FIXED CODE ###

N=input()
slen=len(N)-1
if(slen==0):
    print(N)
    exit()
ans=0
for i in range(2<<(slen-1)):
    k=N
    ins=0
    for j in range(slen): 
        if((i>>j)&1):
            k=k[:j+1+ins]+"+"+k[j+1+ins:]
            ins+=1
    ans+=eval(k)
print(ans)
import fractions

from functools import reduce
K=int(input())

def gcd_list(a,b,c):
  return gcd(gcd(a,b),gcd(b,c))


count=0
for i in range(1,K+1):
  for j in range(i,K+1):
    for k in range(j,K+1):
      
      if i==j and j==k and k==i:
        n=1
      elif i==j or j==k or k==i:
        n=3
      else:
        n=6
      count+=n*gcd_list(i,j,k)

print(count)

### FIXED CODE ###

import math

from functools import reduce
K=int(input())

def gcd_list(numbers):
  return reduce(math.gcd, numbers)


count=0
for i in range(1,K+1):
  for j in range(i,K+1):
    for k in range(j,K+1):
      if i==j and j==k and k==i:
        n=1
      elif i==j or j==k or k==i:
        n=3
      else:
        n=6
      count+=n*gcd_list([i,j,k])

print(count)
import numpy as np
N, K = map(int,input().split())
h = list(map(int, input().split()))

dp = np.full(N, np.inf)
dp[0] = 0
for i in range(1,N):
  for j in range(1,K+1):
    if i >= j: dp[i] = np.min(dp[i],dp[i-j]+np.abs(h[i] - h[i-j]))
print(int(dp[-1]))


### FIXED CODE ###

N, K = map(int,input().split())
h = list(map(int, input().split()))

dp = [1e+09]*N
dp[0] = 0
for i in range(1,N):
  for j in range(1,K+1):
    if i >= j: dp[i] = min(dp[i],dp[i-j]+abs(h[i] - h[i-j]))
print(int(dp[-1]))
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

for i in range(1, n):
    candy = []
    candy.append(sum(a[:i]) + sum(b[i-1:]))

print(max(candy))

### FIXED CODE ###

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

ans = a[0] + sum(b)
c = ans

for i in range(n-1) :
    c = c - b[i] + a[i+1]
    ans = max(ans, c)

print(ans)
import sys

N, M = map(int, input().split())
SC = list()
for i in range(M):
    s, c = map(int, input().split())
    SC.append([s, c])

SSC = sorted(SC, key=lambda x: x[0])

ansL = [list(filter(lambda x:x[0]==1, SSC)), list(filter(lambda x:x[0]==12, SSC)), list(filter(lambda x:x[0]==3, SSC)),]

for L in ansL:
    if L == []:
        continue
    else:
        for l in L:
            if L[0][1] != l[1]:
                print("-1")
                sys.eixt()

ans = ""
for l in ansL:
    if l == []:
        ans += str(0)
    else:
        ans += str(min([x[1] for x in l]))

if ans[0] == "0":
    print(-1)
    sys.exit()
print(ans)




### FIXED CODE ###

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

condition = set()
for i in range(M):
    s, c = map(int, input().split())
    condition.add((s, c))

ans = float("inf")
if N == 1:
    for i in range(10):
        num = str(i)
        for s, c in condition:
            if num[s-1] != str(c):
                break
        else:
            print(i)
            exit()       

for i in range(10**(N-1), 10**N):
    num = str(i)
    for s, c in condition:
        if num[s-1] != str(c):
            break
    else:
        print(i)
        exit()
print(-1)
N=int(input().split())
V=list(map(int,input().split()))
C=list(map(int,input().split()))
def rescale(V,C):
  price=0
  for v,c in zip(V,C):
    if v>c:
      price=price+v-c
  return price 
print("{}".format(rescale(V,C)))


### FIXED CODE ###

N=int(input())
V=list(map(int,input().split()))
C=list(map(int,input().split()))
def rescale(V,C):
  price=0
  for v,c in zip(V,C):
    if v>c:
      price=price+v-c
  return price 
print("{}".format(rescale(V,C)))
# coding: utf-8

str = input()

if str =='A' :
    str = 'T'
    break
elif str == 'T' :
    str = 'A'
    break
elif str == 'C':
    str = 'G'
elif str == 'G':
    str = 'C'

print(str)

### FIXED CODE ###

# coding: utf-8

str = input()

if str =='A' :
    str = 'T'
elif str == 'T' :
    str = 'A'
elif str == 'C':
    str = 'G'
elif str == 'G':
    str = 'C'

print(str)
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for i in range(M):
  tmp = list(map(int, input().split()))
  BC.append(tmp)

A.sort()
BC.sort(key=lambda x: x[1], reverse=True)

j = 0
for i in range(M):
  count = 0
  while A[j] < BC[i][1]:
    A[j] = BC[i][1]			# 値を置き換える
    j += 1
    count += 1
    if count == BC[i][0]:
      break
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for i in range(M):
  tmp = list(map(int, input().split()))
  BC.append(tmp)

A.sort()
BC.sort(key=lambda x: x[1], reverse=True)

j = 0
for i in range(M):
  count = 0
  while A[j] < BC[i][1]:
    A[j] = BC[i][1]			# 値を置き換える
    j += 1
    count += 1
    if count == BC[i][0] or j == N:
      break
  if j == N:
    break
print(sum(A))
N=int(input())
A=list(map(int, input().split()))
L=[0]*(100001)
#何回その数字が出てきたかのリスト
ans=0
for a in A:
  L[a]+=1
  #aが出てきた数（2回出てきたら2になる）
  ans=sum(A)
Q=int(input())
for i in range(Q):
  B,C=map(int, input().split())
  #Bの数だけ（C-B)足す、BはCに置き換わるのでLB＝０になおす。
  key=L[B]
  L[C]+=key
  ans+=key*(C-B)
  L[B]=0
  print(ans)

### FIXED CODE ###

S=input()
if S.isupper()==True:
  print('A')
else:
  print('a')
def func(data):
  if data[2] == data[3] and data[4] == data[5]:
    print('Yes')
  else:
    print('No')

func(s)

### FIXED CODE ###

s= input()
if s[2] == s[3] and s[4] == s[5]:
  print('Yes')
else:
  print('No')
import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  dp=[[inf]*(50*50+1)for _ in range(n)]
  kakutei=[[0]*(50*50+1)for _ in range(n)]
  dp[0][min(s,50*50)]=0
  todo=[[0,0,min(s,50*50)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(100*51-1,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=50*50
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()
n = int(input())
polys = []
for i in range(n):
        polys.append(int(input()))

if sum(polys) - max(polys) > max(polys):
        print('Yes')
else:
        print('No')

### FIXED CODE ###

n = int(input())
polys = list(map(int, input().split(' ')))

if sum(polys) - max(polys) > max(polys):
        print('Yes')
else:
        print('No')
from scipy.misc import comb
n, m, r = map(int, input().split())
a = r - n * m
if a < 0:
    print(0)
else:
    print(int(comb(a + n - 1, n - 1)))


### FIXED CODE ###

import math
n, m, r = map(int, input().split())
a = r - n * m
def combination(p, q):
    if q < 0 or p < q:
        return 0
    return math.factorial(p) // math.factorial(q) // math.factorial(p - q)
if a < 0:
    print(0)
else:
    print(int(combination(a + n - 1, a)))
def search(start: int, visited: list, power: list, min_power: int, min_powers: int) -> int:
    minimum = 10**4
    if min_powers[start] != -1:
        return min_powers[start] + min_power
    if visited[1] == True:
        #print(f'{min_power=}')
        return min_power
    for i, v in enumerate(visited):
        if not v:
            visited[i] = True
            min_power += power[start][i]

            #min_powers[i] = search(i,visited,power,min_power,min_powers)
            minimum = min(minimum, search(i,visited,power,min_power,min_powers))

            visited[i] = False
            min_power -= power[start][i]
            #print(f'{minimum=}')
    return minimum


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

power = [[] for _ in range(10)]

for i in range(10):
    power[i] = list(map(int, input().split()))

world = [[] for _ in range(H)]

for i in range(H):
    world[i] = list(map(int, input().split()))

min_powers = [-1] * 10
visited = [False] * 10

#print(f'{power[8][4]=}')
for i in range(10):
    min_power = 0
    visited[i] = True
    min_powers[i] = search(i,visited,power,min_power,min_powers)
    visited[i] = False
    #visited = [False] * 10
for i in range(10):
    #pass
    print(f'{i=}, {min_powers[i]=}')
ans = 0
for wor in world:
    for w in wor:
        if w != -1:
            ans += min_powers[w]

print(ans)


### FIXED CODE ###


def search(start: int, visited: list, power: list, min_power: int, min_powers: int) -> int:
    minimum = 10**4
    if min_powers[start] != -1:
        return min_powers[start] + min_power
    if visited[1] == True:
        #print(f'{min_power=}')
        return min_power
    for i, v in enumerate(visited):
        if not v:
            visited[i] = True
            min_power += power[start][i]

            #min_powers[i] = search(i,visited,power,min_power,min_powers)
            minimum = min(minimum, search(i,visited,power,min_power,min_powers))

            visited[i] = False
            min_power -= power[start][i]
            #print(f'{minimum=}')
    return minimum


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

power = [[] for _ in range(10)]

for i in range(10):
    power[i] = list(map(int, input().split()))

world = [[] for _ in range(H)]

for i in range(H):
    world[i] = list(map(int, input().split()))

min_powers = [-1] * 10
visited = [False] * 10

#print(f'{power[8][4]=}')
for i in range(10):
    min_power = 0
    visited[i] = True
    min_powers[i] = search(i,visited,power,min_power,min_powers)
    visited[i] = False
    #visited = [False] * 10
for i in range(10):
    pass
    #print(f'{i=}, {min_powers[i]=}')
ans = 0
for wor in world:
    for w in wor:
        if w != -1:
            ans += min_powers[w]

print(ans)
N, M = map(int, input().split())
L1, R1 = map(int, input().split())
flag = 0
def find_key(L1,R1,L2,R2):
  if R1 < L2 or R2 < L1:
    return(False)
  else:
    a = [R1,L1,R2,L2]
    a.sort()
    return(a[1],a[2])

for i in range(M - 1):
  L,R = map(int, input().split())
  if find_key(L1,R1,L,R) != False:
    L1,R1 = find_key(L1,R1,L,R)
  else:
    flag = 1
    print(0)
    break
if flag = 0:
  print(R1-L1+1)

### FIXED CODE ###

N, M = map(int, input().split())
L1, R1 = map(int, input().split())
flag = 0
def find_key(L1,R1,L2,R2):
    if R1 < L2 or R2 < L1:
        return(False)
    else:
        a = [R1,L1,R2,L2]
        a.sort()
        return(a[1],a[2])

for i in range(M - 1):
    L,R = map(int, input().split())
    if find_key(L1,R1,L,R) != False:
        L1,R1 = find_key(L1,R1,L,R)
    else:
        flag = 1
        print(0)
        break
if flag == 0:
    print(R1-L1+1)
n,Q=map(int,input().split())
s=input()

a=['']*(n+1)
for i in range(n):
    a[i+1]=a[i]+s[i]    

for i in range(Q):
    l,r=map(int,input().split())
    q=a[r][l-1:]
    print(q.count('AC'))

### FIXED CODE ###

n,Q=map(int,input().split())
s=input()

a=[0]*(n+1)
for i in range(2,n+1):
    if s[i-2]=='A' and s[i-1]=='C':
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]

for i in range(Q):
    l,r=map(int,input().split())
    print(a[r]-a[l])
import sys
sys.setrecursionlimit(1e6)

N, M = map(int, input().split())
if M % 2 == 1:
  print(-1)
  exit()
  
E = []
A = [[] for _ in range(N)]
for _ in range(M):
  i, j = map(int, input().split())
  E.append([i-1, j-1])
  A[i-1].append(j-1)
  A[j-1].append(i-1)

tree = [[] for _ in range(N)]
visited = [False] * N
queue = [0]
visited[0] = True
while queue:
  i = queue.pop()
  for j in A[i]:
    if not visited[j]:
      tree[i].append(j)
      tree[j].append(i)
      visited[j] = True
      queue.append(j)

D = [0] * N
for i, j in E:
  if i not in tree[j]:
    print(i+1, j+1)
    D[i] += 1

def f(parent, i):
  for j in tree[i]:
    if j == parent:
      continue
    f(i, j)
    if D[j] % 2 == 0:
      print(i+1, j+1)
      D[i] += 1
    else:
      print(j+1, i+1)
      D[j] += 1
  return

f(0, 0)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
if M % 2 == 1:
  print(-1)
  exit()
  
E = []
A = [[] for _ in range(N)]
for _ in range(M):
  i, j = map(int, input().split())
  E.append([i-1, j-1])
  A[i-1].append(j-1)
  A[j-1].append(i-1)

tree = [[] for _ in range(N)]
visited = [False] * N
queue = [0]
visited[0] = True
while queue:
  i = queue.pop()
  for j in A[i]:
    if not visited[j]:
      tree[i].append(j)
      tree[j].append(i)
      visited[j] = True
      queue.append(j)

D = [0] * N
for i, j in E:
  if i not in tree[j]:
    print(i+1, j+1)
    D[i] += 1

def f(parent, i):
  for j in tree[i]:
    if j == parent:
      continue
    f(i, j)
    if D[j] % 2 == 0:
      print(i+1, j+1)
      D[i] += 1
    else:
      print(j+1, i+1)
      D[j] += 1
  return

f(0, 0)
N,M = map(int, input().split())
A = [int(input()) for a in range(M)]
A = set(A)
	
DP = [0] * (N + 1)	
DP[0] = 1

mod = (10 ** 9) + 7

for i in range(1,N+1):
	if i in A:
		DP[i] = 0
	else:
		DP[i] = DP[i-1] + DP[i-2]

print(DP[n] % (mod))

### FIXED CODE ###

N,M = map(int, input().split())
A = [int(input()) for a in range(M)]
A = set(A)
	
DP = [0] * (N + 1)	
DP[0] = 1

mod = (10 ** 9) + 7

for i in range(1,N+1):
	if i in A:
		DP[i] = 0
	else:
		DP[i] = DP[i-1] + DP[i-2]

print(DP[N] % (mod))
h, n = map(int, input().split())
a = []
b = []
for _ in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)

dp = [float("inf")] * (3 * h)
dp[0] = 0
for i in range(h):
    for j in range(n):
        dp[i + a[j]] = min(dp[i + a[j]], dp[i] + b[j])

ans = float('inf')
for j in range(h, 2 * h + 1):
    ans = min(ans, dp[j])
print(ans)

### FIXED CODE ###

h, n = map(int, input().split())
a = []
b = []
for _ in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)

dp = [float("inf")] * (2 * 10000 + 1)
dp[0] = 0
for i in range(h):
    for j in range(n):
        if (i + a[j]) > 2 * 10000:
            dp[2 * 10000] = min(dp[2 * 10000], dp[i] + b[j])
            continue
        dp[i + a[j]] = min(dp[i + a[j]], dp[i] + b[j])

ans = float('inf')
for j in range(h, 2 * 10000 + 1):
    ans = min(ans, dp[j])
print(ans)
n = input()
for i in range(0,len(n)-1,1):
  if (n[i] ==-n[i+1]):
    print("Bad")
    else:
print("Good")

### FIXED CODE ###

n = input()
for i in range(len(n) -1):
  if (n[i] == n[i+1]):
      print("Bad")
      break
else: 
    print("Good")
import numpy as np
N, K = map(int, input().split(' '))
h = np.array([-1] + list(map(int, input().split(' '))), dtype=np.int64)

dp = np.array([-1 for _ in range(N+1)], dtype=np.int64)
# dp[0], dp[1], ..., dp[N] が用意される

dp[1] = 0
for k in range(2, N+1): # k = 2, ..., N
  """
  candidate = []
  for i in range(1, K+1): # i = 1, 2, ..., K
    if k - i <= 0:
      break
    candidate.append(dp[k-i] + abs(h[k] - h[k-i]))
  """
  start_index = max(1, k - K + 1)
  # candidate = [
  #     dp[start_index] + abs(h[k] - h[start_index]),
  #     dp[start_index+1] + abs(h[k] - h[start_index+1]),
  #     ...,
  #     dp[k-1] + abs(h[k] - h[k-1]),
  # ]
  candidate = dp[start_index:k] + np.abs(h[k] - h[start_index:k])
  dp[k] = np.min(candidate)

print(dp[N])


### FIXED CODE ###

N, K = map(int, input().split(' '))
h = [None] + list(map(int, input().split(' ')))

dp = [None for _ in range(N+1)]
# dp[0], dp[1], ..., dp[N] が用意される

dp[1] = 0
for k in range(2, N+1): # k = 2, ..., N
  candidate = []
  for i in range(1, K+1): # i = 1, 2, ..., K
    if k - i <= 0:
      break
    candidate.append(dp[k-i] + abs(h[k] - h[k-i]))
  dp[k] = min(candidate)

print(dp[N])
a = input()
color = input()

if a < 3200:
  print("red")
  else
  print(color)

### FIXED CODE ###

a = int(input())
color = input()
 
if a < 3200:
  print("red")
else:
  print(color)
import sys
sys.setrecursionlimit(30000)
n, q = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

cost = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    cost[p-1] += x

ans = [0] * n
def dfs(cur, c, parent):
    c += cost[cur]
    ans[cur] = c
    for next in edge[cur]:
        if next != parent:
            dfs(next, c, cur)

dfs(0, 0, -1)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

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

connect = [set() for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

counter = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    counter[p-1] += x

ans = [0] * n
def dfs(me, parent, cum):
    cum += counter[me]
    ans[me] = cum
    for child in connect[me]:
        if child != parent:
            dfs(child, me, cum)

dfs(0, -1, 0)

print(*ans)
N = int(input())
S = list(input())
 
r, g, b = 0, 0, 0
for i in range(N):
    if S[i] == 'R':
        r += 1
    elif S[i] == 'G':
        g += 1
    else:
        b += 1
 
a = r*g*b
 
for i in range(N):
    for j in range(i+1, N):
        if 2*j-i < N:
            if (S[i] != S[j]) and (S[j] != S[2*j-i]) and (S[i] != S[2*j-i]):
                a -= 1
 
print(a)

### FIXED CODE ###

from sys import stdin

N = int(stdin.readline().rstrip())


a=N%10
b=((N-a)/10)%10
c=(N-10*b-a)/100
n=[a,b,c]
if 7 in n:
    print('Yes')

else:
    print('No')
N = int(input())
cnt = 0 
for a in range(1,N//2+1):
    for b in range(a,N):
        if N - a * b > 0:
            if a == b:
                cnt += 1
            else:
                cnt += 2
print(cnt)

### FIXED CODE ###

s = input()

if s[-1] == 's':
    print(s+'es')
else:
    print(s+'s')
import numpy as np
import math
n = int(input())
a = np.array([int(n) for n in input().split()])
divisors = []
for i in range(2, math.ceil(math.sqrt(a.max()))+1):
    while True:
        cond = (a%i==0)
        if cond.sum() > 1:
            a[cond] //= i
            divisors.append(i)
        else:
            break
print(int(np.concatenate((a,divisors)).cumprod()[-1]))

### FIXED CODE ###

n = int(input())
a = map(int, input().split())
result = a.__next__()

for nb in a:
    na = result
    result *= nb
    while nb > 0:
        na, nb = nb, na%nb
    result //= na

print(result)