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

mod = 10**9 + 7

def accmulate(array):
    cs = [0]*(len(array)+1)
    for i in range(len(array)):
        cs[i+1] = cs[i] + array[i]
    return cs

def query(l,r):
    return cs[r+1] - cs[l]

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

dp = [[0]*(K+1) for _ in range(N+1)]

dp[0][0] = 1

for i in range(1,N+1):
    cs = accmulate(dp[i-1])
    for j in range(K+1):
        dp[i][j] += query(max(j-A[i-1], 0), j)
        dp[i][j] %= mod

ans = dp[N][K]
print(ans)

### FIXED CODE ###

mod = 10**9 + 7

def accmulate(array):
    cs = [0]*(len(array)+1)
    for i in range(len(array)):
        cs[i+1] = cs[i] + array[i]
    return cs

def query(l,r):
    return cs[r+1] - cs[l]

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

dp = [[0]*(K+1) for _ in range(N+1)]

dp[0][0] = 1

for i in range(1,N+1):
    cs = accmulate(dp[i-1])
    for j in range(K+1):
        dp[i][j] += query(max(j-A[i-1], 0), j)
        dp[i][j] %= mod

ans = dp[N][K]
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]


#%%
# n, a = 4, [2, 10, 8, 40]


#%%


#%%

#%%
while len(a) >= 2:
    a.sort()

    for i in range(len(a) -1, 0, -1):
        a[i] = a[i] % a[0]
        if a[i] == 0:
            a.remove(a[i])
    


#%%
print(a[0])

#%%



### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]


def euclid_lcf(a, b):
    if b < a:
        a, b = b, a

    if b % a == 0:
        return a
    else:
        r = b % a
        return euclid_lcf(a, r)


com_factor = euclid_lcf(a[0], a[1])

if len(a) == 2:
    print(com_factor)
else:
    for i in range(2, len(a)):
        com_factor = euclid_lcf(com_factor, a[i])

    print(com_factor)
### BUGGY CODE ###

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

for _ in range(q):
    i = int(input()) - 1
    for j in range(n):
        if j != i:
            li[j] -= 1

for j in li:
    if j > 0 :
        print("Yes")
    else:
        print("No") 

### FIXED CODE ###

n, k, q = map(int, input().split())
li = [0 for _ in range(n)]

for _ in range(q):
    li[int(input())-1] += 1

for j in li:
    if k - q + j > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
li = [int(input()) for i in range(n)]

tmp = [li[0]]

for i in range(1,n):
    if li[i] <= min(li):
        tmp.append(li[i])
    else:
        for cnt, j in enumerate(tmp):
            if li[i] > j:
                tmp[cnt] = li[i]
                break

print(len(tmp))

### FIXED CODE ###

import bisect
# from collections import deque
# from collections import Counter
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt
 
n = int(input())
li = [int(input()) for i in range(n)]
li = [-x for x in li]

X = []
X.append(li[0])

for i in range(1,n):
    idx = bisect.bisect_right(X,li[i])
    if idx==len(X):
        X.append(li[i])
    else:
        X[idx] = li[i]

print(len(X))
### BUGGY CODE ###

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

import itertools

def main():
    X = int(raw_input())
    jumpTime = [ i for i in xrange(1,X+1) ]
    candidate = []
    for i in xrange(1, len(jumpTime)+1):
       candidate.append(list(itertools.combinations(jumpTime, i)))
    correct = []
    for can in candidate:
        for c in can:
            if sum(c) == X:
                correct.append(c)
    correctMax = map(max, correct)
    print min(correctMax)
        

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    X = int(raw_input())
    step = 0
    for i in xrange(1,X+1):
        step += i
        if step >= X:
            break
    print i

if __name__ == '__main__':
    main()
### BUGGY CODE ###

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    MAX = 10 ** 5
    q = int(input())
    lr = [list(map(int, input().split())) for _ in range(q)]

    dp = [1] * (MAX + 1)
    dp[0] = dp[1] = 0
    for i in range(2, MAX + 1):
        if dp[i]:
            x = 2
            while i * x < MAX + 1:
                dp[i * x] = 0
                x += 1
    for i in reversed(range(2, MAX + 1)):
        if not dp[(i + 1) // 2]:
            dp[i] = 0
    for l, r in lr:
        print(sum(dp[l:r + 1]))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit
from itertools import accumulate


def main():
    input = stdin.buffer.readline
    MAX = 10 ** 5
    q = int(input())
    lr = [list(map(int, input().split())) for _ in range(q)]

    dp = [1] * (MAX + 1)
    dp[0] = dp[1] = 0
    for i in range(2, MAX + 1):
        if dp[i]:
            x = 2
            while i * x < MAX + 1:
                dp[i * x] = 0
                x += 1
    for i in reversed(range(2, MAX + 1)):
        if not dp[(i + 1) // 2]:
            dp[i] = 0

    summary = list(accumulate(dp))

    for l, r in lr:
        print(summary[r] - summary[l - 1])


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()
### BUGGY CODE ###

n=int(input())
mas=list(map(int,input().split()))
out=[]
mx=0
for i in range(n):
  if mx>n-i:
    break
  j=i
  ans=0
  while j<n-1:
    if mas[j]>=mas[j+1]:
      ans+=1
    else:
      break
    j+=1
  
  if ans>mx:
    mx=ans
  
print(mx)


### FIXED CODE ###

n=int(input())
mas=list(map(int,input().split()))
out=[]
mx=0
i=0
while i<n:
  if mx>n-i:
    break
  j=i
  ans=0
  while j<n-1:
    if mas[j]>=mas[j+1]:
      ans+=1
    else:
      break
    j+=1
  
  if ans>mx:
    mx=ans
  i+=ans+1
  
print(mx)
### BUGGY CODE ###

N=int(input())
n=0
while N>=2**n:
  n=+1
print(2**(n-1))

### FIXED CODE ###

N=int(input())
n=0
while N>=2**n:
  n+=1
print(2**(n-1))
### BUGGY CODE ###

s=input()[::-1]
l=len(s)
dp=[[0 for j in range(13)] for i in range(l)]
if s[0] == "?":
    for j in range(10):dp[0][j]=1
else:
    dp[0][int(s[0])]=1
for i in range(1,l):
    mod = 10**i % 13
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(k+j*mod)%13] += dp[i-1][k]
    else:
        for k in range(13):
            dp[i][(k+int(s[i])*mod)%13] += dp[i-1][k]
print(dp[-1][5]%(10**9+7))


### FIXED CODE ###

s=input()[::-1]
l=len(s)
dp=[[0 for j in range(13)] for i in range(l)]
if s[0] == "?":
    for j in range(10):dp[0][j]=1
else:
    dp[0][int(s[0])]=1
for i in range(1,l):
    mod = pow(10,i,13)
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i-1][k] %= 10**9+7
                dp[i][(k+j*mod)%13] += dp[i-1][k]
    else:
        for k in range(13):
            dp[i-1][k] %= 10**9+7
            dp[i][(k+int(s[i])*mod)%13] += dp[i-1][k]
print(dp[-1][5]%(10**9+7))
### BUGGY CODE ###


from operator import itemgetter
 
n,m=map(int, input().split())
A=[]
B=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])

A.sort(key=itemgetter(1))
bri=[1 for i in range(n)] #bri[0]は1,2番目の島をつなぐ

count=0

for i in range(m):
  a=A[i][0]
  b=A[i][1]
  
  if not 0 in bri[a-1:b-1]:
    bri[b-2]=0
    count+=1

print(count)


### FIXED CODE ###


from operator import itemgetter
 
n,m=map(int, input().split())
A=[]
B=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])

A.sort(key=itemgetter(1))
bri=0 #取った橋のうち番号最大の島のもの。bri=5なら4,5番目の島の橋

count=0

for i in range(m):
  a=A[i][0]
  b=A[i][1]
  
  if a>=bri:
    bri=b
    count+=1

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

from collections import Counter

def cal_factors(num):
    factors = []
    mod = 2
    while num >= 2:
        if num % mod == 0:
            factors.append(mod)
            num //= mod
        else:
            mod += 1

    return factors


def comb(n, r, mod):
    result = 1
    r = min(r, n-r)
    for i in range(n, n-r, -1):
        result *= i
    for i in range(2, r+1):
        result //= i
    result %= mod

    return result


n, m = [int(v) for v in input().split()]

mod = 1000000000 + 7
factors = Counter(cal_factors(m))
ans = 1
for v in factors.values():
    ans *= comb(v + n - 1, v, mod)
    ans %= mod

print(ans)

### FIXED CODE ###

from math import sqrt

def cal_factors(num):
    factors = {}
    i = 0
    while True:
        d, q = divmod(num, 2)
        if q == 0:
            num = d
            i += 1
            factors[2] = i
        else:
            break

    maxmod = int(sqrt(num)) + 1
    for mod in range(3, maxmod, 2):
        i = 0
        while True:
            d, q = divmod(num, mod)
            if q == 0:
                num = d
                i += 1
                factors[mod] = i
            else:
                break

    if num > 1:
        factors[num] = 1

    return factors


def comb(n, r, mod):
    result = 1
    r = min(r, n-r)
    for i in range(n, n-r, -1):
        result *= i
    for i in range(2, r+1):
        result //= i
    result %= mod

    return result


n, m = [int(v) for v in input().split()]

mod = 1000000000 + 7
factors = cal_factors(m)
ans = 1
for v in factors.values():
    ans *= comb(v + n - 1, v, mod)
    ans %= mod

print(ans)
### BUGGY CODE ###

n = int(input())

a = list(map(int, input().split(' ')))
for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

n = int(input())

a = list(map(int, input().split(' ')))
res = [0]*n
for i in a:
    res[i-1] += 1

[print(i) for i in res]
### BUGGY CODE ###

s=list(map(int,input().split()))
t=list(map(int,input().split()))
u=[0]*s[0]
a=0
b=0
for i in range(s[0]):
  u[i]=int((t[i]*(t[i]+1))//2)
for j in range(s[0]-s[1]+1):
  for l in range(j,j+s[1]):
    a+=(u[l]/t[l])
  b=max(b,a)
  a=0
print(b)

### FIXED CODE ###

s=list(map(int,input().split()))
t=list(map(int,input().split()))
c=s[1]
d=0
a=sum(t[0:c])
b=0
for j in range(s[0]-s[1]+1):
  if j==0:
    b=sum(t[:c])
    continue
  else:
    a+=(t[j+c-1]-t[j-1])
    b=max(b,a)
b+=s[1]
print(b/2)
### BUGGY CODE ###

n,k=map(int,input().split())
p=0
for a in range(1,n+1):
  for b in range(1,n+1):
    for c in range(1,n+1):
      if (a+b)%k==0 and (b+c)%k==0 and (c+a)%k==0:
        p+=1
print(p)

### FIXED CODE ###

n,k=map(int,input().split())
a=n//k
if k%2==0:
  b=0
  for i in range(1,n+1):
    if i%k==int(k/2):
      b+=1
  print(a**3+b**3)
else:
  print(a**3)
### BUGGY CODE ###

# O(n) solution (Accepted)
# Author : code_marshal

n, k = map(int, input().split())
a = list(map(int, input().split()))
l, m, j = [], 1, 0
for i in range(n):
    l.append(a[i])
    m*=a[i]
    if i>=k:
        n = m//a[i]
        m//=l[j]
        j+=1
        if n<m: print('Yes')
        else: print('No')

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    if i>=k:
      if a[i]>a[i-k]: print('Yes')
      else: print('No')
### BUGGY CODE ###

n = int(input())
s = input()
r = []
g = []
b = []
for i,j in enumerate(s):
  if j == 'R':
    r.append(i)
  if j == 'G':
    g.append(i)
  if j == 'B':
    b.append(i)
cnt = 0
for i in r:
  for j in g:
    cnt += len(b)
    if 2*j-i in b:
      cnt -= 1
    if 2*i-j in b:
      cnt -= 1
    if (i+j)%2 == 0 and (i+j)//2 in b:
      cnt -= 1
print(cnt)
  


### FIXED CODE ###

N=int(input())
S=input()
r=S.count('R')
b=S.count('B')
g=S.count('G')
ans=r*b*g
for i in range(N):
    for s in range(N):
        j=i+s
        k=j+s
        if k>=N:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            ans-=1
print(ans)
### BUGGY CODE ###

from sys import stdin,setrecursionlimit
import sys
from math import factorial
setrecursionlimit(10**6)
input=stdin.readline

a,b=map(int,input().split())
if abs(a-b)>1:
    print(0)
else:
    ans=factorial(a)*factorial(b)
    print(ans if abs(a-b)==1 else ans*2)


### FIXED CODE ###

from sys import stdin,setrecursionlimit
import sys
from math import factorial
setrecursionlimit(10**6)
input=stdin.readline

a,b=map(int,input().split())
if abs(a-b)>1:
    print(0)
else:
    mod=10**9+7
    fact=[0]*(max(a,b)+1)
    fact[0],fact[1]=1,1
    for i in range(2,max(a,b)+1):
        fact[i]=(i*fact[i-1])%mod
    ans=(fact[a]*fact[b])%mod
    print(ans if abs(a-b)==1 else (ans*2)%mod)
### BUGGY CODE ###

import math
N,M = map(int,input().split())
Price_List = list(map(int,input().split()))
for i in range(M):
    Price_List[Price_List.index(max(Price_List))] = Price_List[Price_List.index(max(Price_List))]/2
print(sum(map(lambda x:math.floor(x),Price_List)))


### FIXED CODE ###

import bisect
 
N,M = map(int,input().split())
Price_List = list(map(int,input().split()))
Price_List.sort()
for i in range(M):
    New_Price = Price_List.pop(-1)//2
    Price_List.insert(bisect.bisect(Price_List,New_Price),New_Price)
print(sum(Price_List))
### BUGGY CODE ###


n = input()
s = raw_input()

result = 300000

for i in range(n):
    cnt = 0
    for j in range(n):
        if i < j:
            if s[j] == "E":
                cnt = cnt + 1
        elif j < i:
            if s[j] == "W":
                cnt = cnt + 1
    result = min(result, cnt)
print result

### FIXED CODE ###

n = input()
s = raw_input()

result = 300000

before = 0
after = 0

for i in range(n):
    if s[i] == "E":
        before = before + 1
    if before > after:
        before = after
    if s[i] == "W":
        after = after + 1

print min(before, after)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())
a = list(map(int,input().split()))
dp = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
def rec(i,j,k):
    #global res
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0

    if i > 0: res += rec(i-1,j,k)*i
    if j > 0: res += rec(i+1,j-1,k)*j
    if k > 0: res += rec(i,j+1,k-1)*k
    res += N
    res *= 1.0/(i+j+k)
    dp[i][j][k] = res
    return res

one = 0
two = 0
three = 0
for aa in a:
    if aa == 1:one+=1
    if aa == 2:two+=1
    if aa == 3:three+=1

#print(dp)
print(rec(one,two,three))
#print(dp)


### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K



dp=[[[0.0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):
    for m in range(min(n,M)+1):#m=j+k
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            #print(i,j,k)
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = [0] + LI()

from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(n,money):
    if n == N+1:
        return money
    else:
        res = money
        for i in range(n,N):  # 購入
            for j in range(i+1,N+1):  # 売却
                if A[i] < A[j]:
                    res = max(res,dfs(j+1,money+(A[j]-A[i])*(money//A[i])))
        return res

print(dfs(1,1000))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
B = [0] + LI()

A = [0,B[1]]
for i in range(1,N):
    if B[i] != B[i+1]:
        A.append(B[i+1])

N = len(A)-1

MAX = [0,1000] + [0]*N

from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(n,money):
    if n == N+1:
        return money
    else:
        res = money
        for i in range(n,N):  # 購入
            for j in range(i+1,N+1):  # 売却
                if A[i] == min(A[i:j+1]) and A[j] == max(A[i:j+1]) and A[i] < A[j]:
                    if money+(A[j]-A[i])*(money//A[i]) > MAX[j+1]:
                        res = max(res,dfs(j+1,money+(A[j]-A[i])*(money//A[i])))
                        MAX[j+1] = money+(A[j]-A[i])*(money//A[i])
        return res

print(dfs(1,1000))
### BUGGY CODE ###

mul = 1
input()
l = map(int, input().split())
for i in l:
    mul = mul * i
    if mul == 0:
        break
print(-1 if mul>1000000000000000000 else mul)

### FIXED CODE ###

mul,f = 1, 0
input()
l = list(map(int, input().split()))
if l.__contains__(0):
    print(0)
    f = 1
else:
    for i in l:
        mul = mul * i
        if mul>1000000000000000000:
            print(-1); break;
    else:
        print( mul)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if abs(i - j) == A[i] + A[j]:
            ans += 1
print(ans)

### FIXED CODE ###

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

Ai = dict()
ans = 0
for i, v in enumerate(A):
    ai = i + v
    if ai in Ai:
        Ai[ai].append(i)
    else:
        Ai[ai] = [i]
for i, v in enumerate(A):
    aj = i - v
    if aj in Ai:
        ans += len(Ai[aj])
print(ans)
### BUGGY CODE ###

H, N = map(int, input().split())
ATK, MP = zip(*(tuple(map(int, input().split())) for _ in range(N)))
MAX_ATK = max(ATK)
table = [0] * (H + MAX_ATK)
for damage in range(1, H + 1):
    table[damage] = min(table[damage - ATK[magic]] + MP[magic] for magic in range(N))
print(table[H])


### FIXED CODE ###

H, N = map(int, input().split())
ATK, MP = zip(*(tuple(map(int, input().split())) for _ in range(N)))
MAX_ATK = max(ATK)
table = [0] * (H + MAX_ATK)
for damage in range(1, H + 1):
    table[damage] = min(table[damage - ATK[magic]] + MP[magic] for magic in range(N))
print(table[H])
### BUGGY CODE ###

K = int(input())

list = [1,2,3,4,5,6,7,8,9]
i = 0
while len(list) != 0:
    v = list.pop(0)

    i += 1
    if i == K:
        break

    if v%10 == 0:
        list.append(v*10)
        list.append(v*10+1)
    elif v%10 == 9:
        list.append(v*10+8)
        list.append(v*10+9)
    else:
        t = v%10
        list.append(v*10 + (t-1))
        list.append(v*10 + t)
        list.append(v*10 + (t+1))

print(v)

### FIXED CODE ###

from collections import deque

K = int(input())

list = deque(range(1,10))
i = 0
for i in range(K):
    v = list.popleft()

    t = v%10

    if t != 0:
        list.append(10*v + (t-1))

    list.append(10*v + t)

    if t != 9:
        list.append(10*v + (t+1))


print(v)
### BUGGY CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(n - 1, 1, -1):
    for j in range(i - 1, 0, -1):
        d = l[i] - l[j]
        cnt = bisect.bisect_right(l[:j], d)
        if j - cnt <= 0:
            break
        ans += j - cnt


print(ans)


### FIXED CODE ###

import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(n - 2):
    l = L[i]
    for j in range(i + 1, n - 1):
        ll = l + L[j]

        ind = bisect.bisect_left(L, ll)
        ans += ind - j - 1

print(ans)
### BUGGY CODE ###

def ss(n):
    s = 1
    for i in range(1,(n//2) + 1):
        if n % i == 0:
            s += 1
    return(s)

n = int(input())
answer = int(0)

for i in range(n+1):
    c = ss(i)
    answer += int(c * i)


print(answer)

### FIXED CODE ###

def g(x,n):
    y = n // x
    s = int(y * (y+1) * x / 2)
    return s

n = int(input())

answer = 0
for i in range(1,n+1):
    answer += int(g(i,n))

print(answer)
### BUGGY CODE ###

k,a,b=map(int,input().split(" "))
x=1
count=0
if a>b or b-a<2:
  print(k+1)
  exit()
while(count<k):
  if x<a and k-count>=a-x:
    count+=a-x
    x=a
  if count+2>k:
    x+=1
    break
  else:
    x=x-a+b
    count+=2
print(x)


### FIXED CODE ###

k,a,b=map(int,input().split(" "))
x=1
count=0
if a>b or b-a<2:
  print(k+1)
  exit()
if x<a and k-count>=a-x:
  count+=a-x
  x=a
c,ex=divmod((k-count),2)
x+=(b-a)*c
if ex==1:
  x+=1
print(int(x))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

s = input().split() 
s = list(s[0])
t = input().split() 
t = list(t[0])

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j] = max(dp[i-1][j-1]+1,dp[i-1][j],dp[i][j-1])
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
#print(dp[len(s)][len(t)])

ans = ""
i = len(s)
j = len(t)
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans = s[i-1]+ans
        i-=1
        j-=1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

s = input().split() 
s = list(s[0])
t = input().split() 
t = list(t[0])

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j] = max(dp[i-1][j-1]+1,dp[i-1][j],dp[i][j-1])
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
#print(dp[len(s)][len(t)])

ans = ""
i = len(s)
j = len(t)
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans = s[i-1]+ans
        i-=1
        j-=1
print(ans)
### BUGGY CODE ###


import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    N, M = LMIIS()
    dp = [0] * (M+1)

    DV = [[0] for _ in range(M+1)]

    for _ in range(N):
        A,B = LMIIS()
        if A > M:
            continue
        DV[A].append(B)

    # for i in range(1,M+1):
    #     DV[i].sort(reverse=True)
    #     DV[i] = DV[i][:M-i+1]
    ans = 0
    tmpL = []
    for l in DV:
        tmpL += l
        tmpL.sort(reverse=True)
        ans += tmpL.pop(0)
    print(ans)
        
        



    pass
if __name__ == '__main__':
    main()


### FIXED CODE ###


import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    N, M = LMIIS()
    dp = [0] * (M+1)

    DV = [[0] for _ in range(M+1)]

    for _ in range(N):
        A,B = LMIIS()
        if A > M:
            continue
        DV[A].append(B)


    from heapq import heappush, heappop
    ans = 0
    h = []
    for l in DV:
        for item in l:
            heappush(h,-item)
        ans -= heappop(h)
    print(ans)
        
        



    pass
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

for _ in range(K):
    b = [0]*N
    for i, a in enumerate(A):
        for j in range(max(i-a, 0), min(a+i+1, N)):
            b[j] += 1
    A = b

print(" ".join(str(a) for a in A))

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
c = [0]*N

for _ in range(min(K, 100)):
    b = [0]*(N+1)
    for i, a in enumerate(A):
        b[max(i-a, 0)] += 1
        b[min(i+a+1, N)] -= 1
    
    x = 0
    for i in range(N):
        x += b[i]
        A[i] = x

print(" ".join(str(a) for a in A))
### BUGGY CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
s=set(t)
for i in s:
  if d.count(i)<t.count(i):
    print('NO')
    exit()
print('YES')

### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
if n<m:
  print('NO')
  exit()
d.sort()
t.sort()
i=0
j=0
while i<n and j<m:
  if d[i]==t[j]:
    i+=1
    j+=1
  else:
    i+=1
if j==m:
  print('YES')
else:
  print('NO')