Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
"""
D - Ki
https://atcoder.jp/contests/abc138/tasks/abc138_d

"""
import sys


from functools import lru_cache
from collections import deque

def solve(N, Q):
    @lru_cache(maxsize=None)
    def calc_score(n):
        if n == 1 or nodes[n][3]:
            return nodes[n][0]
        res = calc_score(nodes[n][2]) + nodes[n][0]
        nodes[n][3] = True
        return res

    nodes = [[0, -1, -1, False] for _ in range(N+1)]
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges[a].append(b)
    for _ in range(Q):
        p, x = map(int, input().split())
        nodes[p][0] += x

    visited = set()
    q = deque([1])
    while q:
        n = q.popleft()
        if n not in visited:
            visited.add(n)
            for m in edges[n]:
                q.appendleft(m)
                nodes[m][2] = n
    ans = [calc_score(i) for i in range(1, N+1)]
    return ans


def main(args):
    N, Q = map(int, input().split())
    ans = solve(N, Q)
    print(*ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]
 
sys.setrecursionlimit(1000000)
mod = 1000000007
 
#A
def A():
    a = I()
    s = input()
    if a >= 3200:
        print(s)
    else:
        print("red")
    return
 
#B
def B():
    n = I()
    a = LI()
    ans = 0
    for i in a:
        ans += 1/i
    print(1/ans)
    return
 
#C
def C():
    n = I()
    v = LI()
    q = []
    for i in v:
        heappush(q,i)
    while q:
        x = heappop(q)
        if not q:
            print(x)
            return
        y = heappop(q)
        heappush(q,(x+y)/2)
    return
 
#D
def D():
    def dfs(x,d,s):
        for y in v[x]:
            if d[y]:
                s += f[y]
                ans[y] = s
                d[y] = 0
                dfs(y,d,s)
                s -= f[y]
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    f = [0]*n
    for i in range(q):
        p,x = LI()
        p -= 1
        f[p] += x
    ans = [0]*n
    d = [1]*n
    d[0] = 0
    ans[0] = f[0]
    s = f[0]
    dfs(0,d,s)
    print(*ans)
    return
 
#E
def E():
    s = input()
    t = input()
 
    return
 
#F
def F():
 
    return
 
#Solve
if __name__ == "__main__":
    D()
N, K = map(int, input().split())
A = list(map(int, input().split()))
count_li = Counter(A)
li = sorted(list(count_li.values()), reverse=True)
print(sum(li[K:]))

### FIXED CODE ###

from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
count_li = Counter(A)
li = sorted(list(count_li.values()), reverse=True)
print(sum(li[K:]))
import sys
sys.setrecursionlimit(10**8)
N = int(input())
li = [[int(x) for x in input().split()] for _ in range(N)]
map = [[-1 for _ in range(101)] for _ in range(101)]
ans = [0]*3
for i in range(101):
    for j in range(101):
        h = -1
        flag = True
        for x in li:
            if(h == -1):
                h=x[2]+abs(x[0]-i)+abs(x[1]-j)
            else:
                if(h!=x[2]+abs(x[0]-i)+abs(x[1]-j)):
                    flag = False
        if(flag):
            ans=[str(i),str(j),str(h)]
            break
print(ans[0]+' '+ans[1]+' '+ans[2])


### FIXED CODE ###

import sys
from operator import itemgetter
sys.setrecursionlimit(10**7)
N = int(input())
li = [[int(x) for x in input().split()] for _ in range(N)]
li.sort(key=itemgetter(2),reverse=True)
map = [[-1 for _ in range(101)] for _ in range(101)]
ans = [0]*3
for i in range(101):
    for j in range(101):
        h = -1
        flag = True
        for x in li:
            if(h == -1):
                h=x[2]+abs(x[0]-i)+abs(x[1]-j)
            else:
                if(x[2]!=0):
                    if(h!=x[2]+abs(x[0]-i)+abs(x[1]-j)):
                        flag = False
                else:
                    if(h>abs(x[0]-i)+abs(x[1]-j)):
                        flag = False
        if(flag):
            if(h>ans[2]):
                ans=[i,j,h]

print(str(ans[0])+' '+str(ans[1])+' '+str(ans[2]))
a,b=map(int,input())
print(0--a//b)

### FIXED CODE ###

a,b=map(int,input().split(' '))
print(-(-a//(1+2*b)))
N, M = map(int, input().split())
bre = []
flag = 0
A = []
for i in range(M):
    bre.append(int(input()))
#print(bre)
A.append(bre[0] - 1)
count = 0
if len(bre) >= 2:
    for i in range(len(bre) - 1):
        a = bre[i + 1] - bre[i]
        A.append(a - 2)
        if a == 1:
            #print(0)
            flag = 1
A.append(N - bre[len(bre) - 1] - 1)

if flag == 0:
    suu = [0, 1, 2]
    for i in range(2, max(A)+1):
        suu.append(suu[i] + suu[i-1] )
    #print(suu)
    for i in A:
        if count == 0:
            count = suu[i]
        else :
            count *= suu[i]
            count = count % 1000000007
    print(count)


### FIXED CODE ###

P = list(map(int, input().split()))
P.sort()
print(P[0]+  P[1])
import math
A, B = map(int, input().split())
print(int(A * B / math.gcd(A, B)))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
now = 1

for i in range(len(A)):
    if A[i] == now:
        now += 1
    else:
        count += 1

print(count if now != 1 else -1)
import numpy as np
mod = 10 ** 9 + 7

if __name__ == "__main__":
	N = int(input())
	L = list(map(int, input().split()))
	L = np.array(L)
	ans = 0
	for i in range(60 + 2):
		A = L % 2
		L = L // 2
		ans += np.sum(A) * (N - np.sum(A)) * (2 ** i) % mod
	print(ans % mod)

### FIXED CODE ###

if __name__ == "__main__":
	A1, A2, A3 = map(int, input().split())
	if A1 + A2 + A3 <= 21:
		print("win")
	else:
		print("bust")
def dfs(i,x):
    ans[i]+=x
    if dist[i]==bottom:
        return
    for n in tree[i]:
        if dist[n]>dist[i]:
            dfs(n,x)

from collections import deque

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

tree=[[] for _ in range(N)]

for _ in range(N-1):
    A,B=map(int,input().split())
    tree[A-1].append(B-1)
    tree[B-1].append(A-1)

#BFSで各ノードの深さを調べる
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in tree[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

#カウンターをDFSで制御
ans=[0 for _ in range(N)]
bottom=max(dist)
for j in range(Q):
    p,x=map(int,input().split())
    dfs(p-1,x)

print(*ans)

### FIXED CODE ###

from collections import deque

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

tree=[[] for _ in range(N)]

for _ in range(N-1):
    A,B=map(int,input().split())
    tree[A-1].append(B-1)
    tree[B-1].append(A-1)

ans=[0 for _ in range(N)]
for j in range(Q):
    p,x=map(int,input().split())
    ans[p-1]+=x

#BFSで親のカウンターを子に継がせる
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in tree[v]:
        if dist[w] > -1:
            continue
        que.append(w)
        dist[w]=d+1
        ans[w]+=ans[v]

print(*ans)
import numpy as np
import math

input_line = input().split()

x = int(input_line[0])
y = int(input_line[1])

print((x * y) // math.gcd(x, y))

### FIXED CODE ###

import numpy as np

input_line = input().split()

a = int(input_line[0])
b = int(input_line[1])

x = a * b

if a < b:
	tmp = a
	a = b
	b = tmp

r = a % b
while r != 0:
	a = b
	b = r
	r = a % b

print(int(x / b))
X = int(input())
if X > 30:
  print("Yes")
 else:
   print("No")

### FIXED CODE ###

X = int(input())
if X >= 30:
    print("Yes")
else:
    print("No")
import sys
input = sys.stdin.readline

import numpy as np

def main():
    n, m_num = map(int, input().split())
    a_list = np.array([int(i) for i in input().split()])
    a_list.sort()

    def func(a, m):
        temp = a[-1]//2
        a[-1] = temp
        a.sort()
        ind = np.where(a==temp)[0][0]
        m -= 1
        if m == 0:
            print(np.sum(a))
        elif n - ind < m:
            a[a>=temp] = a[a>=temp]//2
            a.sort()
            m = m - (n-ind)
            if m>0:
                func(a, m)
            else:
                print(np.sum(a))
        else:
            a[-m:] = a[-m:]//2
            print(np.sum(a))

    func(a_list, m_num)

main()


### FIXED CODE ###

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

import numpy as np

def main():
    n, m = map(int, input().split())
    a = np.array([int(i) for i in input().split()])
    a.sort()

    while True:
        temp = a[-1]//2
        a[-1] //= 2
        a.sort()
        ind = np.where(a==temp)[0][0]
        m -= 1
        if m == 0:
            print(np.sum(a))
            break
        elif n - ind < m:
            a[ind:] = a[ind:]//2
            a.sort()
            m = m - (n-ind)
        else:
            a[-m:] = a[-m:]//2
            print(np.sum(a))
            break

main()
N,M = map(int, input().split())
if N != 1:
    answer = ['0']* (N-1)
answer.insert(0,1)
s_list = []
c_list = []
end = 0
for i in range(0,M):
    s, c = map(int, input().split())
    answer[s-1]= str(c)
    s_list.append(s)
    c_list.append(c)
    for i in range(0,len(s_list)):
        if (s_list[i] == s) &  (c_list[i] != c):
            end =1
            break

if end == 1:
    print(-1)
elif (len(answer) == 1) & (answer[0]=='0'):
    print(0)
elif answer[0] == '0':
    print(-1)
else:
    print(int(''.join(answer)))




### FIXED CODE ###


N,M = map(int, input().split())
if N != 1:
    answer = ['0']* (N-1)
    answer.insert(0,'1')
else:
    answer =['0']
s_list = []
c_list = []
end = 0
for i in range(0,M):
    s, c = map(int, input().split())
    answer[s-1]= str(c)
    s_list.append(s)
    c_list.append(c)
    for i in range(0,len(s_list)):
        if (s_list[i] == s) &  (c_list[i] != c):
            end =1
            break

if end == 1:
    print(-1)
elif (len(answer) == 1) & (answer[0]=='0'):
    print(0)
elif answer[0] == '0':
    print(-1)
else:
    print(int(''.join(answer)))
import math
import time
from collections import defaultdict,deque
from sys import stdin,stdout
from bisect import bisect_left,bisect_right
n=int(input())
ans=0
c=defaultdict(lambda:0)
for _ in n:
    s=int(input())
    if(s in c):
        ans+=1
        c[s]+=1
print(ans)

### FIXED CODE ###

import math
import time
from collections import defaultdict, deque
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
n = int(input())
ans = 0
c = defaultdict(lambda: 0)
for _ in range(n):
    s = input()
    if(s not in c):
        ans += 1
        c[s] += 1
print(ans)
import sys
import  math
import fractions
from collections import defaultdict
from functools import reduce
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
ans=0
min_bai=1
for i in range(N):#最大公倍数
    min_bai=min_bai*A[i]//fractions.gcd(min_bai,A[i])

#lcm = reduce(lambda x,y: x//fractions.gcd(x,y)*y, A)
 
for i in range(N):
    ans+=lcm//A[i]

#ans = sum(lcm//x for x in A)
print(ans%mod)
    

### FIXED CODE ###

import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
print('Yes' if N==M else 'No')
def calc_prime(n):
    primes = set(list(range(3, n, 2)))
    primes.add(2)
    for a in range(3, n, 2):
        for i in range(a, n):
            x = a * i
            if x >= n:
                break
            if x in primes:
                primes.remove(x)

    return primes


def collect_likes(ps):
    likes = set([p for p in ps if (p + 1) / 2 in ps])
    return likes


def line(xs, n):
    ps = list(xs)
    ps.sort()
    cs = [0] * n
    s = 0
    for i in range(n):
        if i in xs:
            cs[i] = s
            s += 1
        else:
            cs[i] = s

    return cs


def main():
    n = 10 ** 5
    primes = calc_prime(n)
    likes = collect_likes(primes)
    cums = line(likes, n)
    #print(sorted(list(primes))[:100])
    print(sorted(list(likes))[:100])
    #print(cums[:10])

    q = int(input())
    for _ in range(q):
        l, r = [int(x) for x in input().split()]
        ans = cums[r + 1] - cums[l]
        print(ans)


main()


### FIXED CODE ###

def calc_prime(n):
    primes = set(list(range(3, n, 2)))
    primes.add(2)
    for a in range(3, n, 2):
        for i in range(a, n):
            x = a * i
            if x >= n:
                break
            if x in primes:
                primes.remove(x)

    return primes


def collect_likes(ps):
    likes = set([p for p in ps if (p + 1) / 2 in ps])
    return likes


def line(xs, n):
    ps = list(xs)
    ps.sort()
    cs = [0] * n
    s = 0
    for i in range(n):
        if i in xs:
            cs[i] = s
            s += 1
        else:
            cs[i] = s

    return cs


def main():
    n = 10 ** 5 + 9
    primes = calc_prime(n)
    likes = collect_likes(primes)
    cums = line(likes, n)
    #print(sorted(list(primes))[:100])
    #print(sorted(list(likes))[:100])
    #print(cums[:10])

    q = int(input())
    for _ in range(q):
        l, r = [int(x) for x in input().split()]
        ans = cums[r + 1] - cums[l]
        print(ans)


main()
n = int(input())
d = {}
for i in range(n):
    s = input()
    d[s] = d[s]+1 if (s in d) else 1
d_sorted = sorted(d.items(), key=lambda x:x[1], reverse=True)
m = d_sorted[0][1]
result = []
for i in range(n):
    if d_sorted[i][1]!=m:
        break
    result.append(d_sorted[i][0])
print(*sorted(result), sep='\n')

### FIXED CODE ###

n = int(input())
d = {}
for i in range(n):
    s = input()
    d[s] = d[s]+1 if (s in d) else 1
d_sorted = sorted(d.items(), key=lambda x:x[1], reverse=True)
m = d_sorted[0][1]
result = []
for i in d_sorted:
    if i[1]!=m:
        break
    result.append(i[0])
print(*sorted(result), sep='\n')
N,X=map(int,input().split())
M = []
cnt = 0
for j in range(N):
  M.append(int,input())
a=X-sum(M)
cnt=a//min(M)+N
print(cnt)


### FIXED CODE ###

N,X = map(int,input().split())
M = [int(input()) for i in range(N)]
X -= sum(M)
M.sort()
ans = -1
while X >= 0:
  X -= M[0]
  ans += 1
print(ans+N)
from copy import deepcopy

def warshallfloyd(cost,V):
    INF = float("inf")
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k]!=INF and cost[k][j]!=INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

    for i in cost:
        if float("inf") in i:
            return False
    
    return True

N,M = map(int,input().split())
edge = [[float("inf") for i in range(N)] for j in range(N)]

for _ in range(M):
    a,b = map(int,input().split())
    edge[a-1][b-1] = 1
    edge[b-1][a-1] = 1

ans = 0

for i in range(N-1):
    for j in range(i+1,N):
        if edge[i][j]:
            tmp = deepcopy(edge)
            tmp[i][j] = float("inf")
            tmp[j][i] = float("inf")
            if not warshallfloyd(tmp,N):
                ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter
a = Counter(list(map(int,input().split()))).most_common()
print(a[1][0])
import numpy as np

def f(X, C, D):
    return X - X//C - X//D + X//np.lcm(C,D)


def main():
    A, B, C, D = map(int, input().split())

    ans = f(B, C, D) - f(A-1, C, D)
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x


def lcm(x, y):
    return x*y//gcd(x,y)


def f(X, C, D):
    return X - X//C - X//D + X//lcm(C,D)


def main():
    A, B, C, D = map(int, input().split())

    ans = f(B, C, D) - f(A-1, C, D)
    print(ans)


if __name__ == '__main__':
    main()
# usr/bin/python
# coding: utf-8
################################################################################
# Is it a Right Triangle?
# Write a program which judges wheather given length of three side form a right triangle.
# Print "YES" if the given sides (integers) form a right triangle, "NO" if not so.
#
# Input
# Input consists of several data sets. In the first line, the number of data set,
# N is given. Then, N lines follow, each line corresponds to a data set.
# A data set consists of three integers separated by a single space.
#
# Constraints
# 1 ??? length of the side ??? 1,000
# N ??? 1,000
# Output
# For each data set, print "YES" or "NO".
#
# Sample Input
# 3
# 4 3 5
# 4 3 6
# 8 8 8
# Output for the Sample Input
# YES
# NO
# NO
#
################################################################################

if __name__ == "__main__":
    line = input()
    a = int(line.split(" ")[0])
    b = int(line.split(" ")[1])
    c = int(line.split(" ")[2])
    if (a*a+b*b==c*c or a*a+c*c==b*b or b*b+c*c==a*a) :
        print("YES")
    else :
        print("NO")
    exit(0)

### FIXED CODE ###

# usr/bin/python
# coding: utf-8
################################################################################
# Is it a Right Triangle?
# Write a program which judges wheather given length of three side form a right triangle.
# Print "YES" if the given sides (integers) form a right triangle, "NO" if not so.
#
# Input
# Input consists of several data sets. In the first line, the number of data set,
# N is given. Then, N lines follow, each line corresponds to a data set.
# A data set consists of three integers separated by a single space.
#
# Constraints
# 1 ??? length of the side ??? 1,000
# N ??? 1,000
# Output
# For each data set, print "YES" or "NO".
#
# Sample Input
# 3
# 4 3 5
# 4 3 6
# 8 8 8
# Output for the Sample Input
# YES
# NO
# NO
#
################################################################################

if __name__ == "__main__":
    num = int(input())
    inputline = [""]*num
    for i in range(0,num):
        inputline[i] = input()
    for line in inputline:
        a = int(line.split(" ")[0])
        b = int(line.split(" ")[1])
        c = int(line.split(" ")[2])
        if (a*a+b*b == c*c or b*b+c*c == a*a or c*c+a*a == b*b):
            print("YES")
        else:
            print("NO")
#include <bits/stdc++.h>
using namespace std;
long long n,tiln = 0;
int counter=0;
int main() {
    cin >> n;
    vector<int> a(10001);
        for(int x = 1;x<;x++){
            for(int y = 1;y<100;y++){
                for(int z = 1;z<100;z++){
                    tiln = (x*x) + (x*y) + (y*y) + z*(y+x) + z*z;
                    a(tiln)++;
                }
            }
        }
    for(int i = 1;i<=tiln;i++){
        cout << a.at(i) << endl;
    }
    return 0;
}


### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
	for j in range(1,105):
		for k in range(1,105):
			v = i*i+j*j+k*k+i*j+j*k+k*i;
			if v<10050:
				ans[v]+=1
for i in range(n):
	print(ans[i+1])
n = int(input())
p = [0] + list(map(int, input().split()))
num = 0
for i in range(1, n + 1):
    if i == p[i]:
        num += 1
        p[i], p[i + 1] = p[i + 1], p[i]

print(num)


### FIXED CODE ###

n = int(input())
p = [0] + list(map(int, input().split()))
num = 0
for i in range(1, n + 1):
    if i == n:
        if i == p[i]:
            num += 1
            break
    if i == p[i]:
        num += 1
        p[i], p[i + 1] = p[i + 1], p[i]

print(num)
a,b=input(str,input().split())
if a=='H':
  print(b)
else:
  if b=='H':
    print('D')
  else:
    print('H')

### FIXED CODE ###

a,b=map(str,input().split())
if a=='H':
  print(b)
else:
  if b=='H':
    print('D')
  else:
    print('H')
from collections import deque

S = input()
Q = int(input())
L = ""
R = ""
flag = 0

for i in range(Q):
    q = list(map(str , input().split()))
    if q[0] == "1":
        if flag == 0:
            flag = 1
        else:
            flag = 0
    else:
        if q[1] == "1":
            if flag == 0:
                L.append(q[2])
            else:
                R.append(q[2])
        else:
            if flag == 0:
                R.appned(q[2])
            else:
                L.append(q[2])
K = L[::-1] + R

if flag == 0:
    print("".join(K))
else:
    print("".join(K[::-1]))

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
q = deque(S)
fg = False
for i in range(Q):
    que = list(map(str , input().split()))
    if que[0] == "1":
        fg = not fg
    elif (que[1] == "1" and fg == False) or (que[1] == "2" and fg == True) :
        q.appendleft(que[2])
    else:
        q.append(que[2])
if fg:
    q.reverse()
print("".join(q))
import math
a,b = map(int,input().split())


def lcm(x,y):
    return (x*y) // math.gcd(x,y)


print(lcm(a,b))


### FIXED CODE ###

def gcd(a,b):
  while b != 0:
    a, b = b, a % b
  return a


def lcm(a,b):
    return (a*b) // gcd(a,b)


a,b = map(int,input().split())
print(lcm(a,b))
import sys

values = [int(input()) for i in range(int(input()))]

maxv = - sys.maxsize - 1
minv = values[0]

for value in enumerate(values):
    maxv = max(maxv, value - minv)
    minv = min(minv, value)         # 今までの最小値を保持(自分と自分を比較しない様に、最大値の評価後に計算)

print(maxv)


### FIXED CODE ###

values = [int(input()) for _ in range(int(input()))]
maxv = values[1] - values[0]
minv = values[0]

for val in values[1:]:
    maxv = max(maxv, val - minv)
    minv = min(minv, val)         # 今までの最小値を保持(自分と自分を比較しない様に、最大値の評価後に計算)
print(maxv)
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,t = inpl()
wv = [inpl() for _ in range(n)]
udp = [[0] * t for _ in range(n)]
ddp = [[0] * t for _ in range(n)]

for i in range(n-1):
    w,v = wv[i]
    for j in range(t):
        if j < w:
            udp[i+1][j] = udp[i][j]
        else:
            udp[i+1][j] = max(udp[i][j], udp[i][j-w] + v)
res = udp[n-1][t-1] + wv[n-1][1]

for i in range(n-1):
    w,v = wv[n-1-i]
    for j in range(t):
        if j < w:
            ddp[i+1][j] = ddp[i][j]
        else:
            ddp[i+1][j] = max(ddp[i][j], ddp[i][j-w] + v)
    res = max(res,ddp[n-1][t-1] + wv[0][1])

for i in range(1,n-1):
    u = i; d = n-i-2
    mx = 0
    for j in range(t):
        tmp = udp[u][j] + ddp[d][n-1-j]
        mx = max(mx, tmp)
    res = max(res, mx)
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,w = inpl()
wv = [inpl() for i in range(n)]
dp = [[0 for i in range(w+1)] for j in range(n+1)]
wv.sort()
wv.sort(key=lambda x:x[1])
ww = [0] * n
vv = [0] * n
for i in range(n):
    ww[i],vv[i] = wv[i][0], wv[i][1]
for i in range(n-1):
    for j in range(w+1):
        if j >= ww[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-ww[i]]+vv[i])
        else:
            dp[i+1][j] = dp[i][j]
res = dp[n-1][w-1]+wv[n-1][1]

dp = [[0 for i in range(w+1)] for j in range(n+1)]
ww[-1],ww[-2] = ww[-2],ww[-1]
vv[-1],vv[-2] = vv[-2],vv[-1]
for i in range(n-1):
    for j in range(w+1):
        if j >= ww[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-ww[i]]+vv[i])
        else:
            dp[i+1][j] = dp[i][j]
print(max(res,dp[n-1][w-1]+vv[n-1]))