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

import sys
sys.setrecursionlimit(10**6) #for deep recursion

N, Q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(N-1)]
counts = [0] * N
operations = [list(map(int, input().split())) for _ in range(Q)]

counts = [0] * N
for op in operations:
    p, x = op
    counts[p-1] += x
    
all_connected_vertices = {i: [] for i in range(1, 1+N)}
for a, b in edges:
    all_connected_vertices[a].append(b)
    all_connected_vertices[b].append(a)
    
def get_connected_vertices(v):
    return all_connected_vertices[v]
    
visited_vertices = [] 
def dfs(point):
    visited_vertices.append(point)
    connected_vertices = get_connected_vertices(point)
    children = [v for v in connected_vertices if v not in visited_vertices]
    for c in children:
        counts[c-1] += counts[point-1]
        dfs(c)
    
dfs(1)
res = ""
for c in counts:
    res += " " + str(c)
    
print(res[1:])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6) #for deep recursion

N, Q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

counts = [0] * N
for op in operations:
    p, x = op
    counts[p-1] += x
    
all_connected_vertices = {i: [] for i in range(1, 1+N)}
for a, b in edges:
    all_connected_vertices[a].append(b)
    all_connected_vertices[b].append(a)
    
def dfs(point, pre):
    connected_vertices = all_connected_vertices[point]
    for c in connected_vertices:
        if c == pre:
            continue
        counts[c-1] += counts[point-1]
        dfs(c, point)
    
dfs(1, -1)
    
print(*counts)
### BUGGY CODE ###

n = int(input())
ab = [list(map(int, (input()+' '+str(i)).split())) for i in range(n-1)]
ab.sort()
count = [0]*n
for i in range(n-1):
  count[ab[i][0]-1] += 1
  count[ab[i][1]-1] += 1
color = max(count)
print(color)
uc = [0]*n
coloring = [0]*(n-1)
for i in range(n-1):
  j = 0
  while (uc[ab[i][0]-1]>>j | uc[ab[i][1]-1]>>j) & 1:
    j+=1
  else:
    coloring[ab[i][2]] = j+1
    uc[ab[i][0]-1] += 2**j
    uc[ab[i][1]-1] += 2**j
for i in range(n-1):
  print(coloring[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
ab = [list(map(int, input().split())) for i in range(n-1)]
ab2 = [[] for i in range(n)]
for i in range(n-1):
  ab2[ab[i][0]-1].append([ab[i][1]-1, i])
  ab2[ab[i][1]-1].append([ab[i][0]-1, i])
coloring = [0]*(n-1)

def f(x, y, z):
  c = 0
  for i in ab2[x]:
    if i[0] != y:
      c += 1
      if c == z:
        c += 1
      coloring[i[1]] = c
      x1 = i[0]
      y1 = x
      z1 = c
      f(x1, y1, z1)

f(0, None, None)
print(max(coloring))
for i in range(n-1):
  print(coloring[i])
### BUGGY CODE ###

n = int(input())
S = input()
l = len(S)

S += 'eeee'

cnt = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            # tmp = str(i)+str(j)+str(k)
            m = 0
            while S[m] != str(i):
                m += 1
                if m >= l:
                    break
            m += 1
            while S[m] != str(j):
                m += 1
                if m >= l:
                    break
            m += 1
            while S[m] != str(k):
                m += 1
                if m >= l:
                    break
            if m < l:
                cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
S = input()
l = len(S)

S += 'eeee'

cnt = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            # tmp = str(i)+str(j)+str(k)
            m = 0
            while S[m] != str(i):
                m += 1
                if m >= l:
                    break
            m += 1
            while S[m] != str(j):
                m += 1
                if m >= l:
                    break
            m += 1
            while S[m] != str(k):
                m += 1
                if m >= l:
                    break
            if m < l:
                cnt += 1

print(cnt)
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

int1 = lambda x: int(x) - 1
N, M = map(int, input().split())

frm, to = [], []
for _ in range(M):
    u, v = map(int1, input().split())
    for i in range(3):
        frm.append(i + 3 * u)
        to.append((i + 1) % 3 + 3 * v)

S, T = map(int1, input().split())
matr = csr_matrix(([1] * len(frm), (frm, to)), shape=(3 * N, 3 * N))
way = dijkstra(matr, indices=3 * S).astype(int)

res = way[3 * T]
print(res // 3 if res >= 0 else -1)


### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.buffer.readline
int1 = lambda x: int(x) - 1

N, M = map(int, input().split())
G = [[] for _ in range(3 * N)]
for _ in range(M):
    u, v = map(int1, input().split())
    G[u * 3].append(v * 3 + 1)
    G[u * 3 + 1].append(v * 3 + 2)
    G[u * 3 + 2].append(v * 3)

S, T = map(int1, input().split())
S *= 3
T *= 3

# bfs
d = deque([S])
distance = [0] * (3 * N)
while d:
    v = d.popleft()
    dist_v = distance[v]
    if v == T:
        print(dist_v // 3)
        exit()
    for x in G[v]:
        if not distance[x]:
            d.append(x)
            distance[x] = dist_v + 1
print(-1)
### BUGGY CODE ###

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

#x=dict(zip(range(1,N+1),a))
#print(x)
route=[1,]
for _ in range(N):
#while 2 not in route:
  #print(x[route[-1]])
  if route[-1]==2:
    break
  elif x[route[-1]-1] not in route:
    route.append(x[route[-1]-1])
  else:
    print(-1)
    exit()
        
print(len(route)-1)

### FIXED CODE ###

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

on=1
ans=0
for _ in range(N):
  on=x[on-1]
  ans=ans+1
  if on==2:
    print(ans)
    exit()
  
print(-1)
### BUGGY CODE ###

X, Y=list(map(int,(input().split())))
m=10**9+7
N=(X+Y)//3
bikkuri=[1 for i in range(N+2)]
gyaku=[1 for i in range(N+2)]
for i in range(1, N+1):
    bikkuri[i+1] =((i+1)*bikkuri[i])%m
    gyaku[i+1] = pow(bikkuri[i+1], m-2, m)
def comb(n, r):
    return (bikkuri[n]*gyaku[r]*gyaku[n-r])%m
if (X+Y)%3==1 or (X+Y)%3==2:
    print(0)
else:
    if X<N or Y<N:
        print(0)
    else:
        print(comb((X-N)+(Y-N), Y-N))

### FIXED CODE ###

X, Y=list(map(int,(input().split())))
m=10**9+7
N=(X+Y)//3
bikkuri=[1 for i in range(N+2)]
gyaku=[1 for i in range(N+2)]
for i in range(1, N+1):
    bikkuri[i+1] =((i+1)*bikkuri[i])%m
    gyaku[i+1] = pow(bikkuri[i+1], m-2, m)
def comb(n, r):
    return (bikkuri[n]*gyaku[r]*gyaku[n-r])%m
if (X+Y)%3==1 or (X+Y)%3==2:
    print(0)
else:
    if X<N or Y<N:
        print(0)
    else:
        print(comb((X-N)+(Y-N), Y-N))
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      if l[i]+l[j]>l[k]:
        ans=ans+1
      else:
        break
print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n):
  for j in range(i+1,n):
    kmax=n
    kmin=j
    while True:
      k=(kmax+kmin)//2
      if l[i]+l[j]>l[k]:
        ans=ans+k-kmin
        kmin=k
      else:
        kmax=k
      if kmax-kmin==1:
        break
print(ans)
### BUGGY CODE ###

md=1000003
q=int(input())
for _ in range(q):
    x,d,n=map(int,input().split())
    ans=1
    s=x
    for _ in range(n):
        ans*=s
        s+=d
    print(ans%md)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

md=10**6+3
n_max = md-1
fac = [1]
for i in range(1, n_max + 1): fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1) % md

def main():
    for _ in range(II()):
        x,d,n=MI()
        if x==0:ans=0
        elif d==0:ans=pow(x,n,md)
        else:
            invd=pow(d,md-2,md)
            x=x*invd%md
            if x+n-1>=md:ans=0
            else:
                ans=fac[x+n-1]*ifac[x-1]*pow(d,n,md)%md
        print(ans)

main()
### BUGGY CODE ###

def likes(i,j,ai,aj):
    if(i == aj and j == ai):
        return True
    else:
        return False

n = int(input())
a = list(map(int,input().split()))
count = 0
for i in range(n-1):
    for j in range(i+1,n):
        if(likes(i+1,j+1,a[i],a[j])):
            count += 1
print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
count = 0
for i in range(n):
    if(a[a[i]-1] == i+1):
        count += 1
print(int(count/2))
### BUGGY CODE ###

n,k,q = map(int,input().split())
ans = [k]*n
for i in range(q):
    idx = int(input()) - 1
    for i in range(n):
        if idx != i:
            ans[i] -= 1
for i in ans:
    print('Yes' if i >0 else 'No')

### FIXED CODE ###

n,k,q = map(int,input().split())
ans = [0]*n
for i in range(q):
    idx = int(input()) -1
    ans[idx] += 1
for i in ans:
    print('Yes' if q-k<i else 'No')
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
import bisect
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    a=l[i]
    b=l[j]
    idxl=bisect.bisect_right(l[j+1:],abs(a-b))
    idxr=bisect.bisect_left(l[j+1:],abs(a+b))
    ans+=idxr-idxl
print(ans)


### FIXED CODE ###

n=int(input())
l=sorted(list(map(int,input().split())))
import bisect
ans=0
for i in range(n):
  for j in range(i):
    index=bisect.bisect_right(l,l[i]-l[j])#このindexよりも右側のものでかつjより左のものが当てはまるもの
    ans += max(j - index,0)
print(ans)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
mod = 2*K
field = np.zeros((2*K+1, 2*K+1), dtype='i')


def gen_pattern(x):
    if x < K-1:
        return [[0, x+1], [x+K+1, 2*K]]
    else:
        return [[x-K+1, x+1]]

for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W':
        y += K
    x %= mod
    y %= mod
    for tmp in [0, K]:
        for l, r in gen_pattern((x+tmp) % mod):
            for b, t in gen_pattern((y+tmp) % mod):
                field[l][b] += 1
                field[l][t] -= 1
                field[r][b] -= 1
                field[r][t] += 1

print(field.cumsum(axis=0).cumsum(axis=1).max())


### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
mod = 2*K
#field = np.zeros((2*K+1, 2*K+1), dtype='i')
field = [[0]*(2*K+1) for _ in range(2*K+1)]

def gen_pattern(x):
    if x < K-1:
        return [[0, x+1], [x+K+1, 2*K]]
    else:
        return [[x-K+1, x+1]]

for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    if c == 'W':
        y += K
    x %= mod
    y %= mod
    for tmp in [0, K]:
        for l, r in gen_pattern((x+tmp) % mod):
            for b, t in gen_pattern((y+tmp) % mod):
                field[l][b] += 1
                field[l][t] -= 1
                field[r][b] -= 1
                field[r][t] += 1

field = np.array(field)
print(field.cumsum(axis=0).cumsum(axis=1).max())
### BUGGY CODE ###

N = int(input())
a = [int(x) for x in input().split()]
mod = 10**9+7
#最小公倍数を割った商の和を求める
import fractions
lcm = a[0]
for i in range(1,N):
    lcm = lcm * a[i] // fractions.gcd(lcm,a[i])
ans = 0
for i in range(N):
    ans = (ans + (lcm//a[i]))%mod
print(ans)

### FIXED CODE ###

N = int(input())
a = [int(x) for x in input().split()]
mod = 10**9+7
#最小公倍数を割った商の和を求める
import fractions
lcm = a[0]
for i in range(1,N):
    lcm = lcm * a[i] // fractions.gcd(lcm,a[i])
ans = 0
for i in range(N):
    ans += lcm//a[i]
print(ans%mod)
### BUGGY CODE ###

N, H = map(int, input().split())
a_list = []
b_list = []
for i in range(N):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
count = 0
a_list.sort()
a_list.reverse()
b_list.sort()
b_list.reverse()
while True:
    if len(b_list) >= 1:
        if b_list[0] >= a_list[0]:
            b = b_list.pop(0)
            H -= b
            count += 1
            if H <= 0:
                break
        else:
            a = a_list[0]
            H -= a
            count += 1
            if H <= 0:
                break
    else:
        a = a_list[0]
        H -= a
        count += 1
        if H <= 0:
            break
        
print(count)

### FIXED CODE ###

N, H = map(int, input().split())
a_list = []
b_list = []
for i in range(N):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
count = 0
a = max(a_list)
b_list.sort()
while len(b_list) >= 1 and H >= 1:
    if b_list[-1] >= a:
        b = b_list.pop(-1)
        H -= b
        count += 1
    else:
        break
if H <= 0:
    print(count)
else:
    tmp = H // a if H % a == 0 else H //a + 1
    print(count + tmp)
### BUGGY CODE ###

from itertools import combinations
import numpy as np

list_len = int(input())
A_list = list(map(int, input().split()))

comb = list(combinations(A_list, 2))
comb_mul = list(map(lambda row: row[0]*row[1], comb))
total_sum = sum(comb_mul)
mod_result = total_sum % (10**9+7)

print(mod_result)

### FIXED CODE ###

N = int(input()) #入力する整数
A = list(map(int,input().split())) #入力する数列A
SUMA = sum(A) #数列の和
MOD = 10**9 + 7 # mod
C = [0] * (N-1) #累積和数列
for i in range(N-1): #\sum_{j = i+1}^{N}を求めて数列に代入する
  SUMA -= A[i]
  C[i] = SUMA
ans = 0 #求める答え
for i in range(N-1):
  ans += A[i]*C[i]
  ans %= MOD #その都度modで割った余りにする
print(ans) #答えを出力する
### BUGGY CODE ###

n, m = map(int, input().split())
a = list( map(int, input().split()))
a_modm=[ai%m for ai in a]

from itertools import accumulate
B = [0] + a_modm
B = list(accumulate(B))
ans = 0
for i in range(0,n):
    for j in range(i,n):
        if (B[j+1]-B[i])%m == 0:
            ans+=1

print(ans)


### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

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

from itertools import accumulate
b = [0] + a
b = list(accumulate(b))

count_mod = defaultdict(int)

for i in range(n+1):
    bi_modm = b[i]%m
    if count_mod[bi_modm] is None: count_mod[bi_modm]=1
    else: count_mod[bi_modm] += 1

ans = 0
for count in count_mod.values():
    ans += count*(count-1)//2
print(ans)
### BUGGY CODE ###

#print("UNKO"[2:3])

N,Q=map(int,input().split())
S=input()
LR=[[list(map(int,input().split())),i,0] for i in range(Q)]
LR=sorted(LR,key=lambda x: x[0][1])
#print(LR)
minl=min([i[0][0] for i in LR])
maxr=max([i[0][1] for i in LR])
Qidx=0
for i in range(minl-1,maxr-1):
    #print(i,Qidx, S[i]+S[i+1])
    if S[i]+S[i+1]=="AC":
        for q in range(Qidx,Q):
            if i+1>LR[q][0][1]-1:
                Qidx=q+1
                continue
            if i<LR[q][0][0]-1:
                continue

            LR[q][2]+=1

LR=sorted(LR,key=lambda x: x[1])
for i in LR:
    print(i[2])


### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
LR=[map(int,input().split()) for i in range(Q)]

data=[0 for i in range(N)]
for i in range(N-1):
    data[i+1]=data[i]
    if S[i]+S[i+1]=="AC":
        data[i+1]+=1
for l,r in LR:
    print(data[r-1]-data[l-1])
### BUGGY CODE ###

N = int(input())
X = input()
B = X.count('1')
#print(B, 'B')

base_mod_1 = [1 for i in range(N)] # 2^i mod B+1
if B > 1:
  base_mod_2 = [1 for i in range(N)] # 2^i mod B-1

for i in range(1, N):
  base_mod_1[i] = (base_mod_1[i-1] * 2) % (B+1)
  if B > 1:
    base_mod_2[i] = (base_mod_2[i-1] * 2) % (B-1)

def num(A):
  b = 1
  r = 0
  for i in range(len(A)):
    r += b * int(A[-i-1])
    b *= 2
  return r

def f(n):
  global call
  call += 1
  bit = 0
  m = n
  while m > 0:
    if m % 2 == 1:
      bit += 1
    m //= 2
  next_n = n % bit
  if next_n > 0:
    f(next_n)

x = num(X)
#print(x, 'x')

for i in range(N):
  call = 0
  if X[i] == '0':
    y = (x + base_mod_1[-i-1]) % (B+1)
    R = B + 1
    call = 1
  else:
    if B > 1:
      y = (x - base_mod_2[-i-1]) % (B-1)
      R = B - 1
      call = 1
    else:
      y = 0
#  print(y, '+', call)
  if y > 0:
    f(y)
  print(call)

### FIXED CODE ###

N = int(input())
X = input()
B = X.count('1')
#print(B, 'B')

base_mod_1 = [1 for i in range(N)] # 2^i mod B+1
if B > 1:
  base_mod_2 = [1 for i in range(N)] # 2^i mod B-1

for i in range(1, N):
  base_mod_1[i] = (base_mod_1[i-1] * 2) % (B+1)
  if B > 1:
    base_mod_2[i] = (base_mod_2[i-1] * 2) % (B-1)

def num(A):
  b = 1
  r = 0
  for i in range(len(A)):
    r += b * int(A[-i-1])
    b *= 2
  return r

def f(n):
  global call
  call += 1
  bit = 0
  m = n
  while m > 0:
    if m % 2 == 1:
      bit += 1
    m //= 2
  next_n = n % bit
  if next_n > 0:
    f(next_n)

x = num(X)
x1 = x % (B+1)
if B > 1:
  x2 = x % (B-1)
#print('x', len(X))

for i in range(N):
  call = 0
  if X[i] == '0':
    y = (x1 + base_mod_1[-i-1]) % (B+1)
    R = B + 1
    call = 1
  else:
    if B > 1:
      y = (x2 - base_mod_2[-i-1]) % (B-1)
      R = B - 1
      call = 1
    else:
      y = 0
#  print(y, '+', call)
  if y > 0:
    f(y)
  print(call)
### BUGGY CODE ###

N,M = map(int,input().split())
prefecture = [[] for i in range(N+1)]
ans = []
for i in range(M):
    p,y = map(int,input().split())
    prefecture[p].append([y,i])
    prefecture[p].sort()
for i in range(1,N+1):#iは県の番号
    tmp_p = str(i)
    while(len(tmp_p)!=6):
         tmp_p = '0'+tmp_p
    for j in range(1,len(prefecture[i])+1):#jは何番目か，すなわちx
        tmp_x = str(j)
        while (len(tmp_x)!=6):
            tmp_x = '0'+tmp_x
        ans.append([prefecture[i][j-1][1],tmp_p+tmp_x])
ans.sort()
for i in range(len(ans)):
    print(ans[i][1])
        

### FIXED CODE ###

N,M = map(int,input().split())
prefecture = [[] for i in range(N+1)]
ans = []
for i in range(M):
    p,y = map(int,input().split())
    prefecture[p].append([y,i])

for i in range(1,N+1):#iは県の番号
    prefecture[i].sort()
    for j in range(1,len(prefecture[i])+1):#jは何番目か，すなわちx
        ans.append([prefecture[i][j-1][1],i,j])
ans.sort()
for i in range(len(ans)):
    print('{:06}{:06}'.format(ans[i][1],ans[i][2]))
### BUGGY CODE ###

import sys

if sys.platform in ['ios','win32','darwin']:
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

H, W = MAP()
M = [input().rstrip() for _ in range(H)]
# for m in M:
# 	print(m)

O = []
for i in range(H):
	for j in range(W):
		if M[i][j] == '#': O.append([i, j])

# print(O)

DU = [-1,1]
LR = [-1,1]
D = [[0]*W for _ in range(H)]
memo = [[-1]*W for _ in range(H)]
ans = 0
for i in range(H):
	for j in range(W):
		if M[i][j] == '#':
			D[i][j] = 9
			continue
		tmp = [0,0]
		
		skip = -1
		if memo[i-1][j] != -1:
			tmp[0] = memo[i-1][j][0]
			skip = 1
			D[i][j] = 1
		if memo[i][j-1] != -1:
			tmp[1] = memo[i][j-1][1]
			skip = 5 if skip == 1 else 2
			D[i][j] = 5 if D[i][j]==1 else 2
		
		if skip == 1 or skip == -1:
			lr = 0
			for idx,move in enumerate(LR):
				nw = j
				dw = move
				while True:
					nw += dw
					# print(i, j, nh, nw)
					if nw>W-1 or nw<0 or M[i][nw] == '#': break
					lr += 1
				tmp[1] = lr

		if skip == 2 or skip == -1:
			du = 0
			for idx,move in enumerate(DU):
				nh = i
				dh = move
				while True:
					nh += dh
					# print(i, j, nh, nw)
					if nh>H-1 or nh<0 or M[nh][j] == '#': break
					du += 1
				tmp[0] = du
		
		memo[i][j] = tmp
		ans = max(ans, sum(tmp)+1)
	
# for mem in memo:
# 	print(mem)
# for m in M:
# 	print(m)
# for d in D:
# 	print(d)
print(ans)

### FIXED CODE ###

import sys

if sys.platform in ['ios','win32','darwin']:
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	H, W = MAP()
	M = [input().rstrip() for _ in range(H)]

	DU = tuple([-1,1])
	LR = tuple([-1,1])
	memo = [[-1]*W for _ in range(H)]
	ans = 0
	for i in range(H):
		for j in range(W):
			if M[i][j] == '#': continue
			tmp = [0,0]
			
			skip = -1
			if memo[i-1][j] != -1:
				tmp[0] = memo[i-1][j][0]
				skip = 1
			if memo[i][j-1] != -1:
				tmp[1] = memo[i][j-1][1]
				skip = 5 if skip == 1 else 2
			
			if skip == 1 or skip == -1:
				lr = 0
				for move in LR:
					nw = j
					dw = move
					while True:
						nw += dw
						# print(i, j, nh, nw)
						if nw>W-1 or nw<0 or M[i][nw] == '#': break
						lr += 1
					tmp[1] = lr

			if skip == 2 or skip == -1:
				du = 0
				for move in DU:
					nh = i
					dh = move
					while True:
						nh += dh
						# print(i, j, nh, nw)
						if nh>H-1 or nh<0 or M[nh][j] == '#': break
						du += 1
					tmp[0] = du
			
			memo[i][j] = tuple(tmp)
			ans = max(ans, sum(tmp)+1)
		
	# for mem in memo:
	# 	print(mem)
	# for m in M:
	# 	print(m)
	print(ans)

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

n,w=map(int,input().split())
goods=[list(map(int,input().split())) for _ in range(n)]
DP=[[0]*(w+1) for _ in range(n+1)]
for i in list(range(n))[::-1]:
  wi,vi=goods[i][0],goods[i][1]
  for j in range(w+1):
    if j<wi:
      DP[i][j]=DP[i+1][j]
    else:
      DP[i][j]=max(DP[i+1][j],DP[i+1][j-wi]+vi)
print(DP[0][w])


### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w+1) for _ in range(n+1)]

def rec(i, j):
  if dp[i][j] != 0:
    return dp[i][j]
  if i == n:
    res = 0
  elif j < a[i][0]:
    res = rec(i+1, j)
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1])
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))
### BUGGY CODE ###

import sys
import socket

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def solve():
  N, M = read_int_list()
  A = [0] * M
  B = [0] * M
  for i in range(M):
    A[i], B[i] = read_int_list()

  res = [0] * (N - 1)
  done = []
  l = [1]
  for i in range(N):
    l2 = []
    for k in range(M):
      for t in l:
        if t == A[k]:
          if B[k] not in l and B[k] not in done:
            l2.append(B[k]) 
            res[B[k] - 2] = A[k]

        if t == B[k]:
          if A[k] not in l and A[k] not in done:
            l2.append(A[k])
            res[A[k] - 2] = B[k]

    done += l
    l = l2

  return res


def main():
    res = solve()
    print('Yes', *res, sep='\n')


main()


### FIXED CODE ###

import sys
import socket

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def solve():
  N, M = read_int_list()
  A = [0] * M
  B = [0] * M
  v = [set() for i in range(N)] 
  for i in range(M):
    A[i], B[i] = read_int_list()
    v[A[i] - 1].add(B[i])
    v[B[i] - 1].add(A[i])

  res = [0] * (N - 1)
  done = set()
  l = set([1])
  for i in range(N):
    l2 = set()
    for t in l:
      for r in v[t - 1]:
        if r not in l and r not in done:
          l2.add(r) 
          res[r - 2] = t

    # done = done.union(set(l))
    done.update(l)
    l = l2

  return res


def solve0():
  N, M = read_int_list()
  A = [0] * M
  B = [0] * M
  v = [set()] * N
  for i in range(M):
    A[i], B[i] = read_int_list()
    v[A[i] - 1].add(B[i])
    v[A[i] - 1].add(B[i])

  res = [0] * (N - 1)
  done = set()
  l = set([1])
  for i in range(N):
    l2 = set()
    for k in range(M):
      for t in l:
        if t == A[k]:
          if B[k] not in l and B[k] not in done:
            l2.add(B[k]) 
            res[B[k] - 2] = A[k]

        if t == B[k]:
          if A[k] not in l and A[k] not in done:
            l2.add(A[k])
            res[A[k] - 2] = B[k]

    # done = done.union(set(l))
    done.update(l)
    l = l2

  return res


def main():
    res = solve()
    print('Yes', *res, sep='\n')


main()