Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import defaultdict
import math
def factorial_memo(n, p):
  F = [1] * (n + 1)
  for i in range(n):
    F[i + 1] = F[i] * (i + 1) % p
  return F

def inverse(F, p):
  Finv = [x for x in F]
  Finv[-1] = pow(Finv[-1], p - 2, p)
  for i in range(len(F) - 2, 0, -1):
    Finv[i] = Finv[i + 1] * (i + 1) % p
  return Finv

def comb(*A):
  f = F[sum(A)]
  for a in A:
    f *= Finv[a]
  return f % p

def is_prime(n):
  for prime in prime_table:
    if n % prime == 0:
      return False
  else:
    return True

N, M = map(int, input().split())
p = 10 ** 9 + 7
limit = math.sqrt(M)
prime_table = []
primes = defaultdict(int)
primes[1] = 0
n = 2
while n <= M:
  if n > limit or is_prime(n):
    prime_table.append(n)
    while M % n == 0:
      primes[n] += 1
      M //= n
    limit = math.sqrt(M)
  n += 1
F = factorial_memo(max(primes.values()) + N, p)
Finv = inverse(F, p)
cnt = 1
for c in primes.values():
  cnt *= comb(c, N - 1)
print(cnt % p)

### FIXED CODE ###

from collections import defaultdict
import math
def factorial_memo(n, p):
  F = [1] * (n + 1)
  for i in range(n):
    F[i + 1] = F[i] * (i + 1) % p
  return F

def inverse(F, p):
  Finv = [x for x in F]
  Finv[-1] = pow(Finv[-1], p - 2, p)
  for i in range(len(F) - 2, 0, -1):
    Finv[i] = Finv[i + 1] * (i + 1) % p
  return Finv

def comb(*A):
  f = F[sum(A)]
  for a in A:
    f *= Finv[a]
  return f % p

def eratosthenes(limit):
  E = [1] * (limit + 1)
  E[0], E[1] = 0, 0
  prime_table = []
  for i, e in enumerate(E):
    if e:
      prime_table.append(i)
      for j in range(i, limit + 1, i):
        E[j] = 0
  return prime_table

N, M = map(int, input().split())
p = 10 ** 9 + 7
limit = int(math.sqrt(M)) + 1
prime_table = eratosthenes(limit)
primes = defaultdict(int)
primes[1] = 0
for prime in prime_table:
  if prime > M:
    break
  while M % prime == 0:
    primes[prime] += 1
    M //= prime
if M > 1:
  primes[M] += 1
F = factorial_memo(max(primes.values()) + N, p)
Finv = inverse(F, p)
cnt = 1
for c in primes.values():
  cnt *= comb(c, N - 1)
print(cnt % p)
### BUGGY CODE ###

X, Y ,Z ,K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

C.sort(reverse=True)

ab_scores = sorted([a + b for a in A for b in B], reverse=True)[:K]
scores = sorted([ab + c for ab in ab_scores for c in C], reverse=True)

for i in range(K):
    print(scores[i])


### FIXED CODE ###

X, Y ,Z ,K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)


scores = []
for a in range(len(A)):
    for b in range(len(B)):
        if (a + 1) * (b + 1) > K:
            break
        for c in range(len(C)):
            if (a + 1) * (b + 1) * (c + 1) > K:
                break
            score = A[a] + B[b] + C[c]
            scores.append(score)

scores.sort(reverse=True)

for i in range(K):
    print(scores[i])
### BUGGY CODE ###

# 入力文字列
get_str = input()

# 操作回数
N = int(input())

# リバースフラグ
r_flag = 0

# 操作
for i in range(N):
    # 取得操作
    inp_cmd = list(input().split())
    # inp_cmd[0] = 1 ならリバースフラグ更新
    if(inp_cmd[0] == '1'):
        r_flag = (r_flag+1) % 2
    else:
        # inp_cmd[1]=1、かつリバースフラグなし
        # inp_cmd[1]=2、かつリバースフラグあり
        # 先頭に文字追加
        if((inp_cmd[1] == '1' and r_flag == 0) or (inp_cmd[1] == '2' and r_flag == 1)):
            get_str = inp_cmd[2] + get_str
        # 上記以外は後ろに追加
        else:
            get_str = get_str + inp_cmd[2]
# リバースフラグあり
if(r_flag == 1):
    get_str = get_str[::-1]

print(get_str)

### FIXED CODE ###

# 入力文字列
get_str = list(input())

# 操作回数
N = int(input())

# リバースフラグ
r_flag = 0

left_str = []
right_str = []
# 操作
for i in range(N):
    # 取得操作
    inp_cmd = list(input().split())
    # inp_cmd[0] = 1 ならリバースフラグ更新
    if(inp_cmd[0] == '1'):
        r_flag = (r_flag+1) % 2
    else:
        # inp_cmd[1]=1、かつリバースフラグなし
        # inp_cmd[1]=2、かつリバースフラグあり
        # 先頭に文字追加
        if((inp_cmd[1] == '1' and r_flag == 0) or (inp_cmd[1] == '2' and r_flag == 1)):
            left_str.append(inp_cmd[2])
        # 上記以外は後ろに追加
        else:
            right_str.append(inp_cmd[2])

# 左文字列リストを反転
left_str = left_str[::-1]

# 文字列結合
list_str = []
list_str = left_str + get_str + right_str

# リバースフラグあり
if(r_flag == 1):
    list_str = list_str[::-1]

out_str = ''.join(list_str)
print(out_str)
### BUGGY CODE ###

from collections import Counter
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
c = Counter(a)
x = 0
for i in range(min(k,len(c))):
  x+=c.most_common()[i][1]
print(n-x)

### FIXED CODE ###

from collections import Counter
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
print(sum(sorted(Counter(a).values())[:-k]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
H = list(map(int,input().split()))
A = list(map(int,input().split()))

N += 1

# N: 処理する区間の長さ
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [-INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

update(0,0)

for h,a in zip(H,A):
    update(h,query(0,h) + a)

ans = query(0,N+1)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
H = list(map(int,input().split()))
A = list(map(int,input().split()))

N += 1

# N: 処理する区間の長さ
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [-INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

update(0,0)

for h,a in zip(H,A):
    update(h,query(0,h) + a)

ans = query(0,N+1)
print(ans)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
lxs=list(xs)
#xj=xs.count("1")
xj=sum([1 for l in lxs if l=="1"])

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
    if xs[n-1-i]=="0":
        pxi=xj+1
        xi=(xip+i1%pxi)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        xi=(xim-i1%pxi)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
#        xi=xi%(bin(xi).count("1"))
        xi=xi%popcount(xi)
    print(icnt)



### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)
### BUGGY CODE ###

n,*a=map(int,open(0).read().split())
f=lambda i:a[i]
c=0
h=[]
while True:
  if f(c)==2:break
  if c in h:
    print(-1)
    exit()
  h.append(c)
  c=f(c)-1
print(len(h)+1)

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
f=lambda x,y:x[y]
i=1
c=0
for _ in range(n):
  i=f(a,i-1)
  c+=1
  if i==2:
    print(c)
    exit()
print(-1)
### BUGGY CODE ###

n = int(input())
dic = {}
for i in range(n):
        s = input()
        if s in dic     :
                dic[s]+=1
        else:
                dic[s]=1
ls = [i for i in dic if dic[i] == max(dic.values())]
for key in sorted(ls):
        print(key)

### FIXED CODE ###

n = int(input())
dic = {}
for i in range(n):
    s = input()
    if not s in dic.keys():
        dic[s]=1
    else:
        dic[s]+=1
maxv = max(dic.values())
ls = [i for i in dic if dic[i] == maxv]
for key in sorted(ls):
    print(key)
### BUGGY CODE ###

#5
#24 11 8 3 16

N = int(input())
num = list(map(int, input().split()))
divz = [0]*N

num.sort()

count = 0
for i, n in enumerate(num):
    for k in range(i):
            if num[i] % num[k] == 0:
                divz[i] = 1
                break
    if divz[i] == 0 and (((i < N-1) and num[i] != num[i+1]) or (i == N-1)):
        count += 1

print(count)


### FIXED CODE ###

import numpy as np

N = int(input())
MAXX = 10**6 + 5
num = np.array(input().split(), np.int32)[:]
mark = np.zeros(MAXX, np.int32)

num = np.sort(num)
for n in num:
    if mark[n] < 2:
        mark[n::n] += 1

count = 0
for n in num:
    if mark[n] == 1:
        count += 1

print(count)
### BUGGY CODE ###

n, a = map(int, raw_input().split())
if n>10**7 or a >= 10**7:
    exit(1)
dp = range(n+1)
ans = n+1
for x in xrange(2, n):
    for i in xrange(x+x, n+1, x):
        dp[i] = min(dp[i], dp[x]+a+i/x)
    ans = min(ans, dp[x]+a+(n+x-1)/x)
print min(ans, dp[-1])


### FIXED CODE ###

# seishin.py
N, A = map(int, input().split())

ans = N
if N > 1:
    for k in range(1, 41):
        left = 0; right = N+1
        while left+1 < right:
            mid = (left + right) // 2
            if mid**(k+1) < N:
                left = mid
            else:
                right = mid
        m = right
        v = (m-1)**(k+1)
        for i in range(k+1):
            v //= m-1
            v *= m
            if N <= v:
                ans = min(ans, A*k + (m-1)*(k+1) + (i+1))
                break
print(ans)
### BUGGY CODE ###

def dfs(x):
  m=x//2
  if m not in dp or dp[m]>dp[x]+abs(2*m-x)*d+a:
    dp[m]=dp[x]+abs(2*m-x)*d+a
    dfs(m)
  m=0--x//2
  if m not in dp or dp[m]>dp[x]+abs(2*m-x)*d+a:
    dp[m]=dp[x]+abs(2*m-x)*d+a
    dfs(m)
  m=x//3
  if m not in dp or dp[m]>dp[x]+abs(3*m-x)*d+b:
    dp[m]=dp[x]+abs(3*m-x)*d+b
    dfs(m)
  m=0--x//3
  if m not in dp or dp[m]>dp[x]+abs(3*m-x)*d+b:
    dp[m]=dp[x]+abs(3*m-x)*d+b
    dfs(m)
  m=x//5
  if m not in dp or dp[m]>dp[x]+abs(5*m-x)*d+c:
    dp[m]=dp[x]+abs(5*m-x)*d+c
    dfs(m)
  m=0--x//5
  if m not in dp or dp[m]>dp[x]+abs(5*m-x)*d+c:
    dp[m]=dp[x]+abs(5*m-x)*d+c
    dfs(m)
def solve():
  dp[n]=0
  dfs(n)
  return min(dp[i]+abs(i)*d for i in dp)
for _ in range(int(input())):
  n,a,b,c,d=map(int,input().split())
  dp={}
  print(solve())

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
  def dfs(x):
    m=x//2
    if m not in dp or dp[m]>dp[x]+abs(2*m-x)*d+a:
      dp[m]=dp[x]+abs(2*m-x)*d+a
      dfs(m)
    m=0--x//2
    if m not in dp or dp[m]>dp[x]+abs(2*m-x)*d+a:
      dp[m]=dp[x]+abs(2*m-x)*d+a
      dfs(m)
    m=x//3
    if m not in dp or dp[m]>dp[x]+abs(3*m-x)*d+b:
      dp[m]=dp[x]+abs(3*m-x)*d+b
      dfs(m)
    m=0--x//3
    if m not in dp or dp[m]>dp[x]+abs(3*m-x)*d+b:
      dp[m]=dp[x]+abs(3*m-x)*d+b
      dfs(m)
    m=x//5
    if m not in dp or dp[m]>dp[x]+abs(5*m-x)*d+c:
      dp[m]=dp[x]+abs(5*m-x)*d+c
      dfs(m)
    m=0--x//5
    if m not in dp or dp[m]>dp[x]+abs(5*m-x)*d+c:
      dp[m]=dp[x]+abs(5*m-x)*d+c
      dfs(m)
  def solve():
    dp[n]=0
    dfs(n)
    return min(dp[i]+abs(i)*d for i in dp)
  for _ in range(int(input())):
    n,a,b,c,d=map(int,input().split())
    dp={}
    print(solve())
if __name__ == "__main__":
  main()
### BUGGY CODE ###

h,w,lim = map(int,input().split())
S = []
ans = 10**10
for i in range(h):
    S.append(input())
for i in range(2**(h-1)):
    bit = ''
    cur = 1
    for j in range(h-1):
        if i&cur != 0:
            bit = '1'+bit
        else:
            bit = '0'+bit
        cur *= 2
    group = []
    if i == 0:
        group = [[i for i in range(h)]]
    else:
        div = []
        for j in range(len(bit)):
            if bit[j] == '0':
                div.append(j)
            else:
                div.append(j)
                group.append(div)
                div = []
        div.append(j+1)
        if len(div) != 0:
            group.append(div)
    num = [0]*len(group)
    cur = len(group)-1
    flag1 = True
    for j in range(w):
        next = [0]*len(group)
        flag2 = True
        for k in range(len(group)):
            plus = 0
            for l in range(len(group[k])):
                if S[group[k][l]][j] == '1':
                    plus += 1
            if plus > lim:
                flag1 = False
                break
            elif plus+num[k] > lim:
                flag2 = False
                next[k] += plus
            else:
                next[k] += plus
        if flag1 == False:
            break
        else:
            if flag2 == False:
                cur += 1
                num = next
            else:
                for k in range(len(group)):
                    num[k] += next[k]
    if flag1:
        ans = min(ans, cur)
print(ans)


### FIXED CODE ###

h,w,lim = map(int,input().split())
S = []
ans = 10**10
for i in range(h):
    S.append(input())
for i in range(2**(h-1)):
    bit = ''
    cur = 1
    for j in range(h-1):
        if i&cur != 0:
            bit = '1'+bit
        else:
            bit = '0'+bit
        cur *= 2
    group = []
    if i == 0:
        group = [[i for i in range(h)]]
    else:
        div = []
        for j in range(len(bit)):
            if bit[j] == '0':
                div.append(j)
            else:
                div.append(j)
                group.append(div)
                div = []
        div.append(j+1)
        if len(div) != 0:
            group.append(div)
    num = [0]*len(group)
    cur = len(group)-1
    flag1 = True
    for j in range(w):
        next = [0]*len(group)
        flag2 = True
        for k in range(len(group)):
            plus = 0
            for l in range(len(group[k])):
                if S[group[k][l]][j] == '1':
                    plus += 1
            if plus > lim:
                flag1 = False
                break
            elif plus+num[k] > lim:
                flag2 = False
                next[k] += plus
            else:
                next[k] += plus
        if flag1 == False:
            break
        else:
            if flag2 == False:
                cur += 1
                num = next
            else:
                for k in range(len(group)):
                    num[k] += next[k]
    if flag1:
        ans = min(ans, cur)
print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    minus = 0
    plus = 0
    fact = [0] * (N+1)
    fact[0] = 1
    pow_fact = [0] * (N+1)
    pow_fact[0] = 1
    fa = 1
    for i in range(1, N+1):
        fa *= i
        fact[i] = fa
        pow_fact[i] = pow(fa, mod-2, mod)
    b = pow_fact[K-1]
    for i in range(N-K+1):
        a = fact[N-i-1]
        c = pow_fact[N-i-K]
        comb = (a*b*c) % mod
        minus += (A[i] * comb)
        plus += (A[-i-1] * comb)
    print((plus - minus) % mod)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
minus = 0
plus = 0
fact = [0] * (N+1)
fact[0] = 1
pow_fact = [0] * (N+1)
pow_fact[0] = 1
fa = 1
for i in range(1, N+1):
    fa *= i
    fa %= mod
    fact[i] = fa
    pow_fact[i] = pow(fa, mod-2, mod)
b = pow_fact[K-1]
for i in range(N-K+1):
    a = fact[N-i-1]
    c = pow_fact[N-i-K]
    comb = (a*b*c) % mod
    minus += (A[i] * comb) % mod
    plus += (A[-i-1] * comb) % mod
print((plus - minus) % mod)
### BUGGY CODE ###

n = int(input())
n_list = [i for i in range(1,n)]
print(sum(n_list))

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

import sys
n,k = map(int,input().split( ))
if k>n:
    flag =1
else:
    flag =0
    
k = min(k,n)
h = list(map(int, input().split( )))
dp =[abs(h[i]-h[0]) for i in range(k)]
for i in range(2,k):
    tmp =[]
    for j in range(i+1):
        #tmp =[]
        #print(*dp)
        #print(dp[j])
        #print(*h)
        #print(h[i],h[j],i,j)
        tmp.append(dp[j]+abs(h[i]-h[j]))#こっちはdp[j],h[j]
    dp[i]= min(tmp)
if flag:
    print(dp[-1])
    sys.exit()
for i in range(k,n):
    tmp =[]
    for j in range(1,k+1):#+1
        tmp.append(dp[i-j]+abs(h[i]-h[i-j]))#こっちはdp[i-j],h[i-j]
    dp.append(min(tmp))
#print(*dp)
print(dp[n-1])


### FIXED CODE ###

import sys
n,k = map(int,input().split( ))
if k>n:
    flag =1
else:
    flag =0
    
k = min(k,n)
h = list(map(int, input().split( )))
dp =[abs(h[i]-h[0]) for i in range(k)]
for i in range(2,k):
    tmp =[]
    for j in range(i+1):
        #tmp =[]
        #print(*dp)
        #print(dp[j])
        #print(*h)
        #print(h[i],h[j],i,j)
        tmp.append(dp[j]+abs(h[i]-h[j]))#こっちはdp[j],h[j]
    dp[i]= min(tmp)
if flag:
    print(dp[-1])
    sys.exit()
for i in range(k,n):
    tmp =[]
    for j in range(1,k+1):#+1
        tmp.append(dp[i-j]+abs(h[i]-h[i-j]))#こっちはdp[i-j],h[i-j]
    dp.append(min(tmp))
#print(*dp)
print(dp[n-1])
### BUGGY CODE ###

from collections import deque
N=int(input())
uvw=list(list(map(int,input().split())) for _ in range(N-1))

graph=[[0]*N for _ in range(N)]
for u,v,w in uvw:
    graph[u - 1][v - 1] = w
    graph[v - 1][u - 1] = w

colors=[2]*N
nonvisited=[p for p in range(1,N)]
queue=deque([0])
colors[0]=0
while len(queue)>0:
    x=queue.popleft()
    if x!=0:
        nonvisited.pop(nonvisited.index(x))
    if len(nonvisited)==0:
        break
    for j in nonvisited:
        if graph[x][j]!=0:
            #nonvisited.pop(nonvisited.index(j))
            queue.append(j)
            colors[j]=(colors[x]+graph[x][j])%2
for p in colors:
    print(p)


### FIXED CODE ###

from collections import deque
N=int(input())
uvw=list(list(map(int,input().split())) for _ in range(N-1))

graph_list=[[] for _ in range(N)]
for u,v,w in uvw:
    graph_list[u - 1].append([v,w])
    graph_list[v - 1].append([u,w])

colors=[-1]*N
colors[0]=0
queue=deque([1])

while len(queue)>0:
    x=queue.popleft()
    if all(colors[i]!=-1 for i in range(N)):
        break
    for j in graph_list[x-1]:
        if colors[j[0]-1]==-1:
            queue.append(j[0])
            colors[j[0]-1]=(2+colors[x-1]+j[1])%2
for p in colors:
    print(p)
### BUGGY CODE ###

S = input()
T = input()

dp = [[ "" for _ in range(len(S) + 1 )] for _ in range(len(T) + 1)]

for i in range(1,len(dp)):
    for j in range(1,len(dp[0])):
        if T[i - 1] == S[j-1]:
            dp[i ][j ] = dp[i-1][j-1] + S[j-1]
        else:
            res1 = dp[i - 1][j]
            res2 = dp[i][j - 1]
            if max([len(res1),len(res2)]) == len(res1):
                dp[i ][j] = res1
            else:
                dp[i ][j] = res2
print(dp[-1][-1])

### FIXED CODE ###

S = input()
T = input()
dp = [[ 0] * (len(S) + 1 ) for _ in range(len(T) + 1)]
ma = 0
for i in range(len(dp)-1):
    for j in range(len(dp[0])-1):
        if T[i ] == S[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
             dp[i + 1][j + 1]  = max(dp[i][j + 1],dp[i +1][j])
i = len(T) - 1
j = len(S) - 1 
ans = ""
while i >=0 and j >= 0:
    if dp[i][j+1] == dp[i + 1][j + 1]:
        i-=1
    elif dp[i + 1][j] == dp[i + 1][j + 1]:
        j-=1
    else:
        #print(j,i)
        ans = S[j] + ans
        i-=1
        j-=1
print(ans)
### BUGGY CODE ###

N = int(input())
r = [int(input()) for x in range(N)]

max_diff = min(r) - max(r) - 1

for i in range(N) :
    for j in range(i + 1, N) :
        max_diff = max(max_diff, r[j] - r[i])
        
print(max_diff)


### FIXED CODE ###

n = int(input())

# initial observation
cur_min = int(input())
max_diff = -1 * (10**9) - 1

for i in range(n - 1) :
    num = int(input())
    
    max_diff = max(max_diff, num - cur_min)
    
    if num < cur_min :
        cur_min = num
    
print(max_diff)
### BUGGY CODE ###

import sys
from itertools import *
from math import *
input=sys.stdin.readline
D, G = map(int, input().split())
probs = [list(map(int, input().split())) for _ in range(D)]
G2 = G
seq = tuple(range(D))
x = tuple(permutations(seq, D))
infty=100000
def main():
    #print(x)
    ans = infty
    for cand in x:
        cnt = 0
        G=G2
        for ind in cand:
            probpoint = (ind + 1) * 100
            if (G<=0)or(cnt>=ans):
                break
            if G <= probpoint * (probs[ind][0] - 1):
                cnt = cnt + ceil(G / probpoint)
                G=G-probpoint*ceil(G / probpoint)
            else:
                cnt=cnt+probs[ind][0]
                G=G-(probpoint * probs[ind][0]+probs[ind][1])
        ans=min(ans,cnt)
    print(ans)

if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
from itertools import *
from math import *
input=sys.stdin.readline
D, G = map(int, input().split())
probs = [list(map(int, input().split())) for _ in range(D)]
G2 = G
seq = tuple(range(D))
x=[]
for i in range(0,D+1):
    l=combinations(seq,i)
    for j in l:
        x.append(j)
x=tuple(x)
#print(x)
infty=100000
#print(x)
ans = infty
for cand in x:
    cnt = 0
    G=G2
    l=[0]*D
    for ind in cand:
        probpoint = (ind + 1) * 100
        G=G-(probpoint * probs[ind][0]+probs[ind][1])
        cnt = cnt + probs[ind][0]
        l[ind]=1
    #print(l,G,cnt)
    for i in range(D-1,-1,-1):
        if G<=0:
            break
        elif l[i]==0:
            probpoint = (i + 1) * 100
            num=ceil(G/probpoint)
            if num<probs[i][0]:
                G=G-num*probpoint
                cnt=cnt+num
            #print(cnt)
            break
    if G<=0:
        ans=min(ans,cnt)
print(ans)
### BUGGY CODE ###

import sys
import numpy as np

n,W = map(int, input().split())
days = []
for _ in range(n):
    day = list(map(int, input().split()))
    days.append(day)
dp = [[1000000] * (W+1) for _ in range(n)]

# # 1日目
# dp[0][0] = days[0][0]
# dp[0][1] = days[0][1]
# dp[0][2] = days[0][2]


# for d in range(1,n):
#     for i in range(3):
#         mx = 0
#         for j in range(3):
#             if i != j:
#                 mx = max(dp[d-1][j] + days[d][i],mx)
#                 # mx = max(dp[d][i], dp[d-1][j]+ days[d][i])
#         dp[d][i] = mx
# print(max(dp[-1]))

for i in range(n):
    dp[i][0] = 0
for w in range(1,W+1):
    if w - days[0][0] >= 0:
        dp[0][w] = days[0][1]
    else:
        dp[0][w] = 0
for d in range(1,n):
    for w in range(1,W+1):
        if w - days[d][0] >= 0:
            dp[d][w] = max(dp[d-1][w], dp[d-1][w-days[d][0]] + days[d][1])
        else:
            dp[d][w] = dp[d-1][w]
print(dp[-1][-1])


### FIXED CODE ###

n,W = map(int, input().split())
w = []
v = []
for i in range(n):
    a,b = map(int, input().split())
    w.append(a)
    v.append(b)

c = [[0 for j in range(W)] for i in range(n)]
for i in range(W):
    if i+1 < w[0]:
        c[0][i] = 0
    else:
        c[0][i] = v[0]

for i in range(1,n):
    for j in range(W):
        if j+1 < w[i]:
            c[i][j] = c[i-1][j]
        else:
            diff = (j+1)-w[i]
            if diff > 0:
                c[i][j] = max(c[i-1][j], v[i]+c[i-1][diff-1])
            else:
                c[i][j] = max(c[i-1][j], v[i])
print(max(c[-1]))