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

def main():
    s=input()
    m=int(input())
    tank=[]
    n=len(s)
    alpha=[chr(i) for i in range(97, 97+26)]
    for i in range(26):
        for j in range(n):
            if alpha[i]==s[j]:
                for k in range(n-j):
                    if s[j:j+k+1] not in tank:
                        tank.append(s[j:j+k+1])
        if len(tank)>=m:
            break
    tank.sort()
    print(tank[m-1])
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    s=input()
    m=int(input())
    tank=[]
    n=len(s)
    alpha=[chr(i) for i in range(97, 97+26)]
    for i in range(26):
        for j in range(n):
            if alpha[i]==s[j]:
                for k in range(min(n-j,m)):
                    if s[j:j+k+1] not in tank:
                        tank.append(s[j:j+k+1])
        if len(tank)>=m:
            break
    tank.sort()
    print(tank[m-1])
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())

x = map(int, input().split())

res = 1

for i in x:
  res = res * i
  if(res > int(1e18)):
    res = -1

if 0 in x:
  print(0)
else:
  print(res)

### FIXED CODE ###

n = int(input())

x = list(map(int, input().split()))

if 0 in x:
  print(0)
else:
  res = 1
  ok = False
  for i in x:
    res = res * i
    if res > int(1e18):
      print(-1)
      ok = True
      break
  if not ok :
    print(res)
### BUGGY CODE ###

import numpy as np
from collections import deque
N,M = [int(i) for i in input().split()]
roads = []
for _ in range(M):
    A,B = [int(i) for i in input().split()]
    roads.append([A,B])
    roads.append([B,A])
roads = np.array(roads)
places = [0]*(N+1)
places[1] = 1
q = deque([1])
vis = [False]*(N+1)
vis[1] = True
while q:
    now = q.popleft()
    L = roads[roads[:,0] == now][:,1]
    for j in L:
        if vis[j]:
            continue
        vis[j] = True
        places[j] = now
        q.append(j)

print("Yes")
s = "\n".join(map(str, places[2:]))
print(s)

### FIXED CODE ###

import numpy as np
from collections import deque
N,M = [int(i) for i in input().split()]
roads = [[] for _ in range(N+1)]
for _ in range(M):
    A,B = [int(i) for i in input().split()]
    roads[A].append(B)
    roads[B].append(A)
places = [0]*(N+1)
places[1] = 1
q = deque([1])
vis = [False]*(N+1)
vis[1] = True
while q:
    now = q.popleft()
    L = roads[now]
    for j in L:
        if vis[j]:
            continue
        vis[j] = True
        places[j] = now
        q.append(j)

print("Yes")
s = "\n".join(map(str, places[2:]))
print(s)
### BUGGY CODE ###

import numpy as np
import copy

n = int(input())
c = np.zeros((n-1), dtype=np.int)
s = np.zeros((n-1), dtype=np.int)
f = np.zeros((n-1), dtype=np.int)
for i in range(n-1):
    c[i], s[i], f[i] = map(int, input().split(" "))

t = np.zeros(n, dtype=np.int)
for i in range(n-1):
    w = np.zeros((n-1), dtype=np.int)
    w = copy.deepcopy(s)
    t[i] = s[i] + c[i]
    for j in range((i+1), (n-1), 1):
        k = 0
        while(True):
            if(w[j] >= t[i]):
                t[i] = w[j]
                break
            for l in range(n-1):
                if(t[i] > w[l]):
                    w[l] += f[l]
        t[i] += c[j]

for i in range(n):
    print(t[i])

### FIXED CODE ###

import numpy as np
import copy

n = int(input())
c = np.zeros((n-1), dtype=np.int)
s = np.zeros((n-1), dtype=np.int)
f = np.zeros((n-1), dtype=np.int)
for i in range(n-1):
    c[i], s[i], f[i] = map(int, input().split(" "))

t = np.zeros(n, dtype=np.int)
for i in range(n-1):
    t[i] = s[i] + c[i]
    for j in range((i+1), (n-1), 1):
        if(s[j] >= t[i]):
            t[i] = s[j]
        elif(t[i] % f[j] != 0):
            t[i] += f[j] - (t[i] % f[j])
        t[i] += c[j]

for i in range(n):
    print(t[i])
### BUGGY CODE ###

N = int(input())
S =[]
for i in range(N):
  s = input()
  t = [s[0],s[1],s[2],s[3],s[4],s[5],s[6],s[7],s[8],s[9]]
  t.sort()
  S.append(t)

c = 0
for i in range(N-1):
  for j in range(i+1,N):
    if S[i] == S[j]:
      c += 1
print(c)


### FIXED CODE ###

N = int(input())
S = []
Y = {}
c = 0
for i in range(N):
  s = input()
  t = [s[0],s[1],s[2],s[3],s[4],s[5],s[6],s[7],s[8],s[9]]
  t.sort()
  u = t[0]+t[1]+t[2]+t[3]+t[4]+t[5]+t[6]+t[7]+t[8]+t[9]
  if u not in Y:
    Y[u] = 1
  else :
    c += Y[u]
    Y[u] += 1
    


print(c)
### BUGGY CODE ###

import math
X = [0] * 1000000

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

for a in A:
    m = int(math.sqrt(a))
    for i in range(2, m + 1):
        if a % i == 0:
            X[i] += 1
        while a % i == 0:
            a /= i
    a = int(a)
    if a != 1:
        X[a] += 1

ans = 'pairwise coprime'
for x in X:
    if x == N:
        print('not coprime')
        exit()
    if x > 1:
        ans = 'setwise coprime'
print(ans)


### FIXED CODE ###

import math

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

g = 0
for a in A:
    g = math.gcd(g, a)
if g != 1:
    print('not coprime')
    exit()

is_prime = [1] * 1000001
D = [0] * 1000001

for i in range(2, 1001):
    if is_prime[i]:
        D[i] = i
        j = 2 * i
        while j <= 1000000:
            if is_prime[j]:
                D[j] = i
                is_prime[j] = 0
            j += i
for i in range(1001, 1000001):
    if is_prime[i]:
        D[i] = i

count = [0] * 1000001
for a in A:
    k = a
    pre = 0
    while k != 1:
        if pre != D[k]:
            count[D[k]] += 1
            if count[D[k]] == 2:
                print('setwise coprime')
                exit()
        pre = D[k]
        k = int(k / D[k])
print('pairwise coprime')
### BUGGY CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
S = str(input())
N = len(S)
M = 13
c = [0]*(N)
for i in range(N):
    c[i] = (10**i)%M
#    c[i] = pow(10,i,M)
#print(c)
c.reverse()
#print(c)
"""
dp = [[0]*M for _ in range(N+1)]
i = int(0)
for j in range(M):
    dp[0][j] = 1
for s in S:
    if s == "?":
        for l in range(10):
            m = l * c[i] % M
            dp[i+1][(M - m) % M] += dp[i][j]
    else:
        m = int(s) * c[i] % M
        dp[i][(M - m) % M] +=dp[i][j]
    i +=1




dp = [[0]*M for _ in range(N)]
c = (10**(N-1))%M
if S[0] == "?":
    for l in range(10):
        dp[0][l*c%M] += 1
else:
    m = int(S[0]) * c%M
    dp[0][m] = 1
S = S[1:]
i = int(1)
for s in S:
    c = (10 ** (N - 1-i)) % M
    if s == "?":
        for j in range(13):
            for l in range(10):
                dp[i][j] += dp[i-1][(j-l*c)%13]
    else:
        st = int(s)
        for j in range(13):
            dp[i][j] = dp[i-1][(j-st*c)%13]
    i +=1

"""
dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1

for i in range(1,N):
    if S[i] == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]%mod
    else:
        for j in range(M):
            m = int(S[i])*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]%mod

#print(dp)
print(dp[-1][5]%mod)

### FIXED CODE ###

import sys
 
 
def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])
 
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

def cal_minX(A,N,M):
    """
    hit A内の数全てでXが割り切れ、かつ商が奇数だったらTrue
    """
    max_A=max(A)
    i=0
    fin=False
    no_ans=False
    while fin==False:
        coef=2*i+1
        hit=True
        if max_A*coef>M:
            fin=True
            no_ans=True
        else:
            for n in range(N):
                if max_A*coef%A[n]==0:
                    if (max_A*coef//A[n])%2==1:
                        pass
                    else:
                        hit=False
                        break
                else:
                    hit=False
                    break

            if hit==False:
                i+=1
            else:
                fin=True
    return no_ans,max_A*coef

def main():
    #input
    N,M=map(int,input().strip().split())
    A=list(map(int,input().strip().split()))
    A=list(map(lambda x:x//2,A))
    
    #題意を満たす最小のXを求める。
    no_ans,minX=cal_minX(A,N,M)
    #1-Mの中にminXの奇数倍数がいくつあるか調べる
    if minX>M or no_ans:
        return 0
    else:
        if M//minX%2==1:
            return M//minX//2+1
        else:
            return M//minX//2
if __name__=="__main__":
    print(main())

### FIXED CODE ###

def divider(A,N):
    """
    リストA内の全要素が全て2**nで割れるときTrueを返す
    """
    cnt_list=[]
    same=True
    for n in range(N):        
        tmp=A[n]
        cnt=0
        while tmp%2==0:
            tmp//=2
            cnt+=1
        cnt_list.append(cnt)
        if n>=1 and cnt!=cnt_list[n-1]:
            same=False
            break
    return same       

def cal_minX(A,N,M):
    """
    hit A内の数全てでXが割り切れ、かつ商が奇数だったらTrue
    """
    max_A=max(A)

    if divider(A,N)==False:
        no_ans=True
        minX=0
    else:
        fin=False
        no_ans=False
        i=0
        while fin==False:
            coef=2*i+1
            if max_A*coef>M:
                fin=True
                no_ans=True
            else:
                hit=True
                for n in range(N):
                    if max_A*coef%A[n]==0:
                        if (max_A*coef//A[n])%2==1:
                            pass
                        else:
                            hit=False
                            break
                    else:
                        hit=False
                        break

                if hit==False:
                    i+=1
                else:
                    fin=True
        minX=max_A*coef
    return no_ans,minX

def main():
    #input
    N,M=map(int,input().strip().split())
    A=list(map(int,input().strip().split()))
    A=list(map(lambda x:x//2,A))
    
    #題意を満たす最小のXを求める。
    no_ans,minX=cal_minX(A,N,M)
    #1-Mの中にminXの奇数倍数がいくつあるか調べる
    if no_ans:
        return 0
    else:
        if M//minX%2==1:
            return M//minX//2+1
        else:
            return M//minX//2
if __name__=="__main__":
    print(main())
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

def solve():
    n, q = MI()
    e = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = MI1()
        e[a].append(b)
        e[b].append(a)

    point = [0]*n
    for _ in range(q):
        p, x = MI()
        p -= 1
        point[p] += x

    # print(point)

    def dfs(v, v_pre=-1, pp=0):
        # ans = pp + point[v]
        # print(v)
        point[v] += pp
        for nv in e[v]:
            if nv == v_pre: continue
            dfs(nv, v, point[v])

    dfs(0)
    printlist(point, ' ')


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')
from collections import deque
def solve():
    n, q = MI()
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = MI1()
        e[a].append(b)
        e[b].append(a)

    point = [0] * n
    for _ in range(q):
        p, x = MI()
        p -= 1
        point[p] += x

    d = deque([(0, point[0])])
    used = [False] * n
    used[0] = True

    while len(d) > 0:
        v, p = d.popleft()
        for nv in e[v]:
            if used[nv]: continue
            used[nv] = True
            point[nv] += p
            d.append((nv, point[nv]))

    printlist(point, " ")

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

import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
ST = np.array(read().split(), dtype=np.int64)
S = ST[::2]
T = ST[1::2]

edge = np.zeros((N + 1, N + 1), dtype=np.int64)
edge[S, T] = 1
edge_sum = np.sum(edge, axis=1) # edge_sum[i] = iから出ている道の本数

dp = np.zeros(N + 1, dtype = np.float64) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = (edge_sum[i] + (edge[i][i + 1:]*dp[i + 1:]).sum())/edge_sum[i]

E = dp[1]
#print(E)

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    to = np.where(edge[i] == 1)[0]
    x = to[np.argmax(dp[to])] #iからxへの道を塞ぐ
    edge[i][x] = 0
    edge_sum[i] -= 1
    for j in range(i, 0, - 1):
        dp[j] = (edge_sum[j] + (edge[j][j + 1:]*dp[j + 1:]).sum())/edge_sum[j]
    edge[i][x] = 1
    edge_sum[i] += 1
    E = min(E, dp[1])
print(E)

### FIXED CODE ###

N, M = map(int, input().split())
edge_out = [[] for i in range(N)] #edge_out[i]はiから出ている道
edge_in = [[] for i in range(N + 1)] # edge_in[i]はiに行く道
for i in range(M):
    s, t = map(int, input().split())
    edge_out[s].append(t)
    edge_in[t].append(s)

edge_sum = [len(edge_out[i]) for i in range(N)] # edge_sum[i] = iから出ている道の本数

dp = [0.0]*(N + 1) # dp[i]はiからNへの距離の期待値
dp[N - 1] = 1.0
# 道を塞がない場合
for i in range(N - 2, 0, - 1):
    dp[i] = 1 + sum(dp[j] for j in edge_out[i])/edge_sum[i]
    
p_to_i = [0]*(N + 1) # p_to_i[i]は1から各iへ到達する確率
p_to_i[1] = 1
for i in range(2, N + 1):
    p_to_i[i] = sum(p_to_i[j]/edge_sum[j] for j in edge_in[i])


t = 0

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    t = max(t, p_to_i[i]*(dp[i] - 1- ((dp[i] - 1)*edge_sum[i] - max(dp[j] for j in edge_out[i]))/(edge_sum[i] - 1)))
    
print(dp[1] - t)
### BUGGY CODE ###

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

start = 0
cnt = 0
for i in range(1, N+1):
  try:
    start = a[start:].index(i)
  except:
    break
  else:
    cnt += 1

if cnt == 0:
  print(-1)
else:
  print(N - cnt)

### FIXED CODE ###

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

start = 0
cnt = 0
for i in range(1, N+1):
  try:
    start = a.index(i, start)
  except:
    break
  else:
    cnt += 1

if cnt == 0:
  print(-1)
else:
  print(N - cnt)
### BUGGY CODE ###

import sys;

def putQueen(i, row, col, dpos, dneq):
    if(i == 8):
        global finding
        if(finding == 0):
            return
        finding = 0
        printBoard(row[0:])
    

    for j in range(8):
        if i in myset:
            putQueen(i+1,row[0:], col[0:], dpos[0:], dneq[0:])
            continue
        if(col[j] == 1 or dpos[i+j] == 1 or dneq[i-j+7] == 1):
            continue
        row[i] = j
        col[j] = dpos[i+j] = dneq[i-j+7] = 1
        putQueen(i+1,row[0:], col[0:], dpos[0:], dneq[0:])
        col[j] = dpos[i+j] = dneq[i-j+7] = 0

def printBoard(row):
    for k in range(8):
        if(row[k] == 0):
            print("Q.......")
        elif(row[k] == 1):
            print(".Q......")
        elif(row[k] == 2):
            print("..Q.....")
        elif(row[k] == 3):
            print("...Q....")
        elif(row[k] == 4):
            print("....Q...")
        elif(row[k] == 5):
            print(".....Q..")
        elif(row[k] == 6):
            print("......Q.")
        else:
            print(".......Q")

n = (int)(input());
row = [0 for i in range(8)]
col = [0 for i in range(8)]
dpos = [0 for i in range(15)]
dneq = [0 for i in range(15)]

myset = set()

for i in range(n):
    r,c = map(int, input().split());
    myset.add(r)
    row[r] = c
    col[c] = 1
    dpos[r+c] = 1
    dneq[r-c+7] = 1

finding = 1

putQueen(0,row, col, dpos, dneq)



### FIXED CODE ###

import sys;

def putQueen(i, row, col, dpos, dneq):
    global finding
    if(finding == 0):
        return
        
    if(i == 8):
        finding = 0
        printBoard(row[0:])
        return
    

    for j in range(8):
        if i in myset:
            putQueen(i+1,row[0:], col[0:], dpos[0:], dneq[0:])
            continue
        if(col[j] == 1 or dpos[i+j] == 1 or dneq[i-j+7] == 1):
            continue
        row[i] = j
        col[j] = dpos[i+j] = dneq[i-j+7] = 1
        putQueen(i+1,row[0:], col[0:], dpos[0:], dneq[0:])
        col[j] = dpos[i+j] = dneq[i-j+7] = 0

def printBoard(row):
    for k in range(8):
        if(row[k] == 0):
            print("Q.......")
        elif(row[k] == 1):
            print(".Q......")
        elif(row[k] == 2):
            print("..Q.....")
        elif(row[k] == 3):
            print("...Q....")
        elif(row[k] == 4):
            print("....Q...")
        elif(row[k] == 5):
            print(".....Q..")
        elif(row[k] == 6):
            print("......Q.")
        else:
            print(".......Q")

n = (int)(input());
row = [0 for i in range(8)]
col = [0 for i in range(8)]
dpos = [0 for i in range(15)]
dneq = [0 for i in range(15)]

myset = set()

for i in range(n):
    r,c = map(int, input().split());
    myset.add(r)
    row[r] = c
    col[c] = 1
    dpos[r+c] = 1
    dneq[r-c+7] = 1

finding = 1

putQueen(0,row, col, dpos, dneq)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
for v in range(min(A), max(A) + 1):
    ans = max(A.count(v - 1) + A.count(v) + A.count(v + 1), ans)
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
C = Counter(A)
ans = 0
start, end = min(A), max(A) + 1
for v in range(start, end):
    ans = max(C[v - 1] + C[v] + C[v + 1], ans)
print(ans)
### BUGGY CODE ###

N,M =map(int,input().split())
L = [0]*M
R = [0]*M
ans = int(0)

for i in range(M):
    L[i],R[i] = list(map(int,input().split()))


for i in range(N):
    j = int(0)
    while (R[j]>=i+1>=L[j]) :
        j += 1
        if j==M:
            ans +=1
            break


print(ans)


### FIXED CODE ###

N,M =map(int,input().split())
L = [0]*M
R = [0]*M
ans = int(0)

for i in range(M):
    L[i],R[i] = list(map(int,input().split()))

a1 = max(L)
a2 = min(R)

ans = a2-a1+1

if ans<0 : ans = int(0)

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

from math import gcd

def prime_factorize(n):
    a = set()
    for i in range(2, int(n**0.5)+1):
        while n%i == 0:
            a.add(i)
            n //= i
    if n != 1:
        a.add(n)
    return a

n = int(input())
a = list(map(int, input().split()))
c0 = False
vals = []
for i, j in enumerate(a):
    vals += prime_factorize(j)
    if len(vals) != len(set(vals)) and c0 is False:
        c0 = True
        
if c0 is False:
    print('pairwise coprime')
else:
    b = gcd(a[0], a[1])
    for i in range(2, n):
        b = gcd(b, a[i])
    if b == 1:
        print('setwise coprime')
    else:
        print('not coprime')

        


### FIXED CODE ###

import sys
from math import gcd

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

b = gcd(a[0], a[1])
for i in range(2, n):
    b = gcd(b, a[i])
if b != 1:
    print('not coprime')
else:
    c = set()
    num = max(a)
    m = 1000000
    vals = [0]*(m+1)

    for i in range(2, m):
        if vals[i] != 0:
            continue
        j = 1
        while True:
            t = i*j
            if t > m:
                break
            if vals[t] == 0:
                vals[t] = i
            j += 1
    d = dict()
    for i in a:
        p = i
        while p != 1:
            if p in d:
                print("setwise coprime")
                sys.exit()
            d[p] = 1
            p = int(p/vals[p])
    print("pairwise coprime")
### BUGGY CODE ###

N, T = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort()

ans = 0
dp = dp = [[0 for _ in range(3005)] for _ in range(3005)]
for i in range(N):
    a, b = AB[i]
    for j in range(T):
        # iを使わないパターン
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        # iを使うパターン
        nj = j + a
        if nj < T:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + b)
    now = dp[i][T - 1] + b
    ans = max(ans, now)

print(ans)


### FIXED CODE ###

from copy import deepcopy

# 多次元配列を作成する
def make_multi_list(initial, degree):
    ans = [initial for _ in range(degree[-1])]
    for d in reversed(degree[:-1]):
        ans = [deepcopy(ans) for _ in range(d)]
    return ans


N, T = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort()

ans = 0
dp = make_multi_list(0, [3005, 3005])
for i in range(N):
    a, b = AB[i]
    for j in range(T):
        # iを使わないパターン
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        # iを使うパターン
        nj = j + a
        if nj < T:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + b)
    now = dp[i][T - 1] + b
    ans = max(ans, now)

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


N=int(input())
A=list(map(int, input().split()))
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

ans=0

for i in range(N):
    Acp=A.copy()
    kkk=Acp.pop(i)
    a=set(make_divisors(A[i]))
    b = a&set(Acp)
    if len(b)==0:
        ans+=1
print(ans)

### FIXED CODE ###

N= int(input())
a =list(map(int,input().split()))
a.sort()
ans=0
Amax=max(a)
DP=[1]*(Amax+1)#これが0のとき、該当する数はカウント済み
#上から順に攻めていく
for i in range(N-1):
    p=a[i]
    if DP[p]==1:#まだ数えられていなかったら
        for j in range(Amax//p+1):#倍数をすべて0にする
            DP[p*j]=0
        if p!=a[i+1]:#隣の数と違うならば
            ans+=1
if DP[Amax]==1:#最後の数は隣の数と比べられんので個別判断
    ans+=1

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

n=int(input())  #->n=5
ai=list(map(int,input().split()))  #->nl=[1,2,-,n]

temp = 0
for i in range(n-1):
    for j in range(i+1,n):
        temp = temp + ai[i]*ai[j]

temp = temp % (10**9+7)
print(temp)



### FIXED CODE ###

#!/usr/bin/env python3

n=int(input())  #->n=5
a=list(map(int,input().split()))  #->nl=[1,2,-,n]
mod=int(1e9+7)

# Accumulate
pre=[0]*n
pre[0]=a[0]
for i in range(1,n):  pre[i]=pre[i-1]+a[i]
ans=0
for i in range(1,n):  ans=(ans+(a[i-1]*(pre[n-1]-pre[i-1]))%mod)%mod
print(ans)
### BUGGY CODE ###

import re
N, Q = map(int, input().split())
S = input()
lr = []
for i in range(Q):
    k = map(int, input().split())
    lr.append(k)

index = []
result = re.finditer('AC', S)
r_list = [0] * len(S)
for r in result:
    r_list[r.start()] = 1

for i in range(Q):
    count = 0
    l, r = lr[i]
    count = sum(r_list[l-1:r-1])
    print(count)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
	t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])