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

import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
ec = [0] * (N - 1)


def dfs(v, pc):
    colors = set()
    colors.add(pc)

    for idx, e in enumerate(edge):
        if v not in e:
            continue
        if ec[idx] == 0:
            for c in range(1, N):
                if c not in colors:
                    ec[idx] = c
                    colors.add(c)
                    break

            nv = e[0] if e[1] == v else e[1]
            dfs(nv, c)


dfs(0, 0)
print(max(ec))
for c in ec:
    print(c)


### FIXED CODE ###

import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append((b - 1, i))
    edge[b - 1].append((a - 1, i))
ec = [0] * (N - 1)


def dfs(node, pc):
    color = 1

    for to, idx in edge[node]:
        if ec[idx] == 0:
            if color == pc:
                color += 1
            ec[idx] = color

            dfs(to, color)
            color += 1


dfs(0, -1)
print(max(ec))
for c in ec:
    print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, k = [int(i) for i in input().split()]
p = [0] * n
for i,v in enumerate(input().split()):
    p[i] = 1.0 + 0.5 * (int(v) -1)

_max_sum = 0
for i in range(n-k+1):
    _sum = sum(p[i:i+k])
    if _sum >= _max_sum:
        _max_sum = _sum
print(_max_sum)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, k = [int(i) for i in input().split()]
p = [0] * n
for i,v in enumerate(input().split()):
    p[i] = 1.0 + 0.5 * (float(v) - 1.0)

_max_sum = 0
_prev_sum = 0
for i in range(0, n-k+1):
    if i == 0:
        _sum = sum(p[:k])
    else:
        _sum = _prev_sum - p[i-1] + p[i+k-1]
    if _sum >= _max_sum:
        _max_sum = _sum
    _prev_sum = _sum
print(_max_sum)
### BUGGY CODE ###

#2020.07.13
N = int(input())
S = input()
ans = 0
for number in range(1000):
    strnum = str(number).zfill(3)
    a,b,c = list(strnum)
    
    for i in range(N-2):
        if a != S[i]:
            continue
        
        flag = False
        
        for j in range(i+1, N-1):
            if b != S[j]:
                continue
            
            if c in S[j+1:]:
                ans += 1
                flag = True
                break
        
        if flag:
            break
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

count = 0
numberlist = [str(i) for i in range(10)]

for a in numberlist:
    idx1 = S.find(a)
    if idx1 == -1 or idx1 >= N - 2:
        continue
    
    for b in numberlist:
        idx2 = S[idx1+1:].find(b)
        if idx2 == -1 or idx2 >= N - 1:
            continue

        count += len(set(S[idx1+idx2+2:]))

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

import numpy as np

N, C = list(map(int, input().split()))
X = np.zeros(N + 2, dtype = int)
V = np.zeros(N + 1, dtype = int)
sumVClockwiwse = np.zeros(N + 1, dtype = int)
#sumVAntiClockwiwse = np.zeros(N + 1, dtype = int)
X[N+1] = C

for n in range(1, N + 1):
    X[n], V[n] = list(map(int, input().split()))
    sumVClockwiwse[n] = sumVClockwiwse[n-1] + V[n]

sumVAntiClockwiwse = sumVClockwiwse[N] - sumVClockwiwse[::-1]

max = 0
for nA in range(N + 1):
    for nB in range(N - nA + 1):
        value = sumVClockwiwse[nA] + sumVAntiClockwiwse[nB]
        if max >= value:
            continue

        cost = min(X[nA] * 2 + (C - X[N - nB + 1]), X[nA] + (C - X[N - nB + 1]) * 2)
        value -= cost 
        if max >= value:
            continue
        # print(nA, nB, ":", cost)
        
        max = value


print(max)

### FIXED CODE ###

import sys
from collections import deque
from functools import lru_cache
import bisect
import copy
import heapq
import itertools
import math
import random
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, C = read_values()
    D = read_lists(N)
    A = [0] * (N + 1)
    A2 = [0] * (N + 1)
    V = 0
    res = 0
    for i, (X, v) in enumerate(D):
        V += v
        A[i + 1] = max(A[i], V - X)
        A2[i + 1] = max(A2[i], V - 2 * X)
        res = max(res, A[i + 1], A2[i + 1])

    V = 0
    for b in range(N - 1, -1, -1):
        x, v = D[b]
        X = C - x
        V += v
        res = max(res, V - 2 * X + A[b], V - X + A2[b])

    print(res)


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

import fractions
N, M = map(int, input().split())

k = M // N
ans = 1
for i in reversed(range(1, k+1)):
    if ans > i:
        break
    ans = max(ans, fractions.gcd(i, M - (N-1)*i))

print(ans)


### FIXED CODE ###

import fractions
N, M = map(int, input().split())

k = M // N + 1
ans = 1
for i in reversed(range(1, k+1)):
    if ans > i:
        break
    tmp = max(M - (N-1)*i, 1)
    if tmp % i == 0:
        ans = max(ans, i)

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

a, b, c, d = map(int, input().split())

cnt = 0
for i in range(a, b+1):
  if i % c != 0 and i % d != 0:
    cnt += 1
    
print(cnt)

### FIXED CODE ###

A, B, C, D = map(int, input().split())
 
def gcd(a, b):
    while a%b!=0:
        a, b = b, a%b
    return b
 
X = B//C - (A-1)//C
Y = B//D - (A-1)//D
CD = C*D // gcd(C, D)
XY = B//CD - (A-1)//CD
 
print(B-A+1-(X+Y-XY))
### BUGGY CODE ###

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

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].add(y)
    graph[y].add(x)

dp_1 = [None] * (N+1)
products = [None] * (N+1)

def dfs_1(v=1,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    # dp_1 + 1 の積
    x = 1
    graph[v].discard(parent)
    arr = [dfs_1(w,v)+1 for w in graph[v]]
    L = [1] + list(itertools.accumulate(arr, lambda x,y: x*y%MOD))
    R = list(itertools.accumulate(arr[1:][::-1], lambda x,y: x*y%MOD))[::-1] + [1]
    products[v] = [x*y%MOD for x,y in zip(L,R)]
    dp_1[v] = 1 if not arr else products[v][0] * arr[0] % MOD
    return dp_1[v]

dp_1 = [0] * (N+1) # 自分を黒く塗って、子側の部分木を適切に塗る方法
dfs_1()

dp_1

products

def dfs_2(v=1,parent=None,x=1):
    # それぞれの子以外の情報をマージして、子に渡さなければいけない
    dp[v] = x * dp_1[v] % MOD
    for w,p in zip(graph[v],products[v]):
        dfs_2(w,v,x*p%MOD+1)

dp = [None] * (N+1)
dfs_2()

print('\n'.join(map(str,dp[1:])))

### FIXED CODE ###

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

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N)]
for row in sys.stdin.readlines():
    x,y = map(int,row.split())
    graph[x-1].add(y-1)
    graph[y-1].add(x-1)

ldp = [None] * N
rdp = [None] * N

def dfs_1(v=0,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    graph[v].discard(parent)
    ldp[v] = [1] * (len(graph[v])+1)
    rdp[v] = [1] * (len(graph[v])+1)
    vals = [dfs_1(w,v)+1 for w in graph[v]]
    for i,x in enumerate(vals,1):
        ldp[v][i] = ldp[v][i-1] * x % MOD
    for i,x in enumerate(reversed(vals),1):
        rdp[v][-i-1] = rdp[v][-i] * x % MOD
    return ldp[v][-1]

dfs_1()

dp = [None] * N
q = [(0,1)]
while q:
    v,x = q.pop()
    dp[v] = x*ldp[v][-1]%MOD
    for w,L,R in zip(graph[v],ldp[v][:-1],rdp[v][1:]):
        q.append((w,x*L*R%MOD+1))

print('\n'.join(map(str,dp)))
### BUGGY CODE ###

a, b, c, k = map(int, input().split())
cnt=0
s=0
# print(a,b,c,k)
while a > 0 and cnt < k:
#     print("a")
    s+=1
    a-=1
    cnt+=1
#     print(a,b,c,k, cnt, s)
while b > 0 and cnt < k:
    #print("b")
    s+=0
    b-=1
    cnt+=1
while c > 0 and cnt < k:
    s-=1
    c-=1
    cnt+=1
print(s)

### FIXED CODE ###

a, b, c, k = map(int, input().split())
cnt=0
s=0
if a >= k:
    s = k
    k = 0
else:
    s+=a
    k-=a
    if b >= k:
        s+=0
        k =0
    else:
        s+=0
        k-=b
        if c >= k:
            s-=k
            k =0
        else:
            s-=c
            k=0
print(s)
### BUGGY CODE ###

r = []

n = int(input())
for i in range(n):
    i = int(input())
    r.append(i)

maxv = r[1] - r[0]

for j in range(1,n):
    for i in range(j):
        maxv = max(maxv, r[j]-r[i])

print(maxv)



### FIXED CODE ###

'''
Rjの最小値を保持することで最大利益の更新判定をn回で終わらせる
'''

r = []

n = int(input())
for i in range(n):
    i = int(input())
    r.append(i)

minv = r[0]
maxv = r[1] - r[0]

for j in range(1,n):
    maxv = max(maxv, r[j]-minv)
    minv = min(minv, r[j])

print(maxv)
### BUGGY CODE ###

n = int(input())
num = 0

for a in range(1, n+1):
  for b in range(1, n//a+1):
    c = n - a * b
    if c != 0:
      num += 1

print(num)

### FIXED CODE ###

n = int(input())
num = 0

for a in range(1, n):
  for b in range(n//a):
    num += 1
  if n % a == 0:
    num -= 1

print(num)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
flug=1

while 1:
    flug=0
    for i in range(n):
        if a[i]%2==0 and flug==0:
            a[i]=a[i]//2
            flug=1
        else:
            a[i]=a[i]*3
    else:
        if flug==1:
            ans+=1
        else:
            print(ans)
            exit()

### FIXED CODE ###

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

for i in range(n):
    while a[i]%2==0:
        a[i]=a[i]//2
        ans+=1

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

def solve():
    N, K = map(int, input().split())
    ps = list(map(int, input().split()))
    res = 0
    for left in range(N - K + 1):
        right = left + K
        expected = sum([(x + 1) / 2 for x in ps[left:right]])
        if expected > res:
            res = expected
    print(res)

solve()

### FIXED CODE ###

def solve():
    N, K = map(int, input().split())
    ps = list(map(int, input().split()))
    curSum = sum(ps[:K])
    curMax = curSum
    i = K; j = 0
    while i < N:
        curSum -= ps[j]
        curSum += ps[i]
        curMax = max(curSum, curMax)
        i += 1; j += 1
    print((curMax + K) / 2)
solve()
### BUGGY CODE ###

n=int(input())
k=int(input())
count=0
for i in range(1,n+1):
  s=str(i)
  n=len(s)
  if n-s.count('0')==k:
    count+=1
print(count)

### FIXED CODE ###

N = int(input())
K = int(input())

strN = str(N)
maxD = len(strN)

dp = [[[0]*(K+1) for j in range(2)] for i in range(maxD+1)]
dp[0][0][0] = 1
for d, Nd in enumerate(strN):
    Nd = int(Nd)
    for isLeN in range(2):
        for m in range(K+1):
            x = 0
            if not isLeN and x > Nd: continue
            isLeN2 = isLeN or x < Nd
            dp[d+1][isLeN2][m] += dp[d][isLeN][m]
            for x in range(1, 10):
                if not isLeN and x > Nd: continue
                isLeN2 = isLeN or x < Nd
                m2 = m+1
                if m2 > K: continue
                dp[d+1][isLeN2][m2] += dp[d][isLeN][m]
#    print(d+1, Nd, dp[d+1])

#print(dp[-1])
print(dp[-1][0][K]+dp[-1][1][K])
### BUGGY CODE ###

#%%
def count(a, k, n):
    l = []
    i, j, count = 0, n-1, 0
    while True:
        tmp = a[i] + a[j]
        if tmp >= k: 
            if j > 0:
                j -= 1
        elif tmp < k:
            l.append(n-j-1)
            count += n - j - 1
            i += 1
        if i >= n:
            break
        tmp = a[i] + a[j]
        if j == 0 and tmp >= k:
            l.append(n-j)
            count += n - j
            i += 1
        if i >= n:
            break
    return [count, l]

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l, r = 10**6, 1


while l - r > 1:
    mid = (l+r)//2
    if count(a, mid, n)[0] < m:
        l = mid
    elif count(a, mid, n)[0] > m:
        r = mid
    else :
        l = mid
        r = mid

ans = 0
if l == r:
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
else:
    p = count(a, l, n)
    q = count(a, r, n)
    check = -1
    for i in range(n):
        if p[1][i] != q[1][i]:
            check = i
            break
    ans += (a[i] + a[n - p[1][check] - 1]) * (m - p[0])
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
print(ans)



    


### FIXED CODE ###

#%%
def count(a, k, n):
    l = []
    i, j, count = 0, n-1, 0
    while True:
        tmp = a[i] + a[j]
        if tmp >= k: 
            if j > 0:
                j -= 1
        elif tmp < k:
            l.append(n-j-1)
            count += n - j - 1
            i += 1
        if i >= n:
            break
        tmp = a[i] + a[j]
        if j == 0 and tmp >= k:
            l.append(n-j)
            count += n - j
            i += 1
        if i >= n:
            break
    return [count, l]

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l, r = 10**6, 1


while l - r > 1:
    mid = (l+r)//2
    if count(a, mid, n)[0] < m:
        l = mid
    elif count(a, mid, n)[0] > m:
        r = mid
    else :
        l = mid
        r = mid

ans = 0
if l == r:
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
else:
    p = count(a, l, n)
    q = count(a, r, n)
    check = -1
    for i in range(n):
        if p[1][i] != q[1][i]:
            check = i
            break
    ans += (a[i] + a[n - p[1][check] - 1]) * (m - p[0])
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
print(ans)
### BUGGY CODE ###

import numpy as np

N, X = map(int, input().split())
S = list(map(int, input().split()))


MOD = 1000000007
numbers = S[:]
numbers.sort()


dp = np.zeros((N+1, X+1))
dp[0] = [x for x in range(X+1)]


for i, n  in enumerate(numbers):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % n]
        dp[i+1][x] += dp[i][x] * i 

print(int(dp[N][X] % MOD))


### FIXED CODE ###

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort(reverse=True)


dp = {X: 1}

for i, n in enumerate(numbers):
    tmp_dp = {}
    for k, v in dp.items():
        if k < n:
            tmp_dp[k] = (tmp_dp.get(k,0)+v*(N-i))
        else:
            tmp_dp[k]=(tmp_dp.get(k,0)+v*(N-i-1)) 
            tmp_dp[k%n]=(tmp_dp.get(k%n,0)+v) 
    dp = tmp_dp.copy()
        
ans = 0
for k, v in dp.items():
    ans += k *  v

print(ans % MOD)
### BUGGY CODE ###

import sys

Num = int(sys.stdin.readline().rstrip())
list_stu_Num = list(sys.stdin.readline().rstrip().split())
list_attend_stu = []
list_stu_Serial_Num = list(range(1, Num + 1))
for i in list_stu_Serial_Num:
    i = str(i)
    l = list_stu_Num.index(i) + 1
    list_attend_stu.append(l)
print(*list_attend_stu)

### FIXED CODE ###

import sys
import numpy as np

Num = int(sys.stdin.readline().rstrip())
list_stu_Num = list(sys.stdin.readline().rstrip().split())
list_stu_Num_int = [int(s) for s in list_stu_Num]
print(*np.argsort(list_stu_Num_int) + 1)
### BUGGY CODE ###

import os

N,M = (int(x) for x in input().split())
list = list(map(int,input().split()))

for i in range(0,M):
    list.sort()
    list[len(list)-1] = list[len(list)-1]//2

ans = 0
for j in list:
    ans += j
print(ans)


### FIXED CODE ###

import os
import heapq

N,M = (int(x) for x in input().split())
list = [-int(i) for i in input().split()]

heapq.heapify(list)
ans = 0
for i in range(0,M):
    a = heapq.heappop(list)
    heapq.heappush(list,-((-a)//2))
for j in list:
    ans += j*(-1)
print(ans)
### BUGGY CODE ###

INPUT = [int(i) for i in input().split(" ")]

N = INPUT[0]
K = INPUT[1]
Q = INPUT[2]
#print(INPUT)
A = []
for i in range(Q):
        A.append(int(input()))
#print(A)

P = [K]*N
#print(P)
for a in A:
    for i in range(len(P)):
        P[i] = P[i] - 1
    P[a-1] = P[a-1] + 1

#print(P)

for i in P:
    if(i >= 1):
        print("Yes")
    else:
        print("No")
    

### FIXED CODE ###

INPUT = [int(i) for i in input().split(" ")]

N = INPUT[0]
K = INPUT[1]
Q = INPUT[2]
#print(INPUT)
A = []
for i in range(Q):
        A.append(int(input()))
#print(A)

P = [K]*N
#print(P)
for i in range(len(P)):
    P[i] = P[i] - Q

for i in A:
    P[i-1] = P[i-1] + 1
    

#print(P)

for i in P:
    if(i >= 1):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
arr = list(map(int, input().split(' ')))

maxi = 62
mod = int(1e9) + 7
ones = [0 for _ in range(maxi)]
for num in arr:
    x = bin(num)[2:]
    # print(x)
    for idx, val in enumerate(reversed(x)):
        ones[idx] += int(val)

ans = 0
for idx, val in enumerate(ones):
    ans += ((pow(2, idx) % mod) * (((n - val)%mod) * (val%mod))) % mod

    ans %= mod

print(ans)

### FIXED CODE ###

import sys
lines = sys.stdin.readlines()
n = int(lines[0])
arr = list(map(int, lines[1].split(' ')))

maxi = 62
mod = int(1e9) + 7
ones = [0 for _ in range(maxi)]
for num in arr:
    for idx, val in enumerate(range(maxi)):
        ones[idx] += (num >> idx ) & 1

ans = 0
for idx, val in enumerate(ones):
    ans += ((pow(2, idx) % mod) * (((n - val)%mod) * (val%mod))) % mod

    ans %= mod

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

N, K = [int(zz) for zz in input().split()]
A = [int(zz) for zz in input().split()]

A.sort(reverse=True)
p = sum(A)
flag = 0
for i in range(N-1):
    if K >= p - sum(A[:i+1]):
        p//=(i+1)
        flag=1
        break

if flag == 0:
    p //= N

while p > 0:
    z = 0
    for i in range(N):
        z += A[i] % p
    if z % p == 0:
        B = [i % p for i in A]
        B.sort(reverse=True)
        q = z//p
        j = 0
        for i in range(q):
            j += p-B[i]
        if K >= j:
            print(p)
            exit()
    p -= 1

print(p)


### FIXED CODE ###

N, K = [int(zz) for zz in input().split()]
A = [int(zz) for zz in input().split()]

A.sort(reverse=True)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

P = make_divisors(sum(A))
P.sort(reverse=True)

for p in P:
    z = 0
    for i in range(N):
        z += A[i] % p
    if z % p == 0:
        B = [i % p for i in A]
        B.sort(reverse=True)
        q = z//p
        j = 0
        for i in range(q):
            j += p-B[i]
        if K >= j:
            print(p)
            exit()
            
print(p)
### BUGGY CODE ###

N = int(input())

kind = []
for i in range(N):
    S = input()

    if S not in kind:
        kind.append(S)

print(len(kind))


### FIXED CODE ###

N = int(input())

kind = {}
for i in range(N):
    S = input()

    if S not in kind:
        kind[S] = 1

print(len(kind))
### BUGGY CODE ###

n,m = map(int,input().split())
price_list = sorted(list(map(int,input().split())),reverse = True)
for num in range(m):
    price_list[0] = price_list[0]//2
    price_list = sorted(price_list,reverse = True)
print(sum(price_list))

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
price_list =list(map(lambda x : -int(x),input().split()))
heapq.heapify(price_list)

for i in range(m):
    dis = heapq.heappop(price_list)
    heapq.heappush(price_list, -(-dis//2)) 
print(-1*sum(price_list))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
M=N**2
P=tuple(map(int1,input().split()))
d=[0]*M
for i in range(N):
    for j in range(N):
        d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
used=[1]*M
ans=0
que=deque()
for p in P:
    ans+=d[p]
    used[p]=0
    que.append(p)
    while que:
        x=que.popleft()
        for ddx in (-1,1,-N,N):
            nx=x+ddx
            if 0<=nx<M:
                if used[x]==0 and d[nx]-d[x]>=1:
                    d[nx]-=1
                    que.append(nx)
                elif used[x]==1 and d[nx]-d[x]>=2:
                    d[nx]-=1
                    que.append(nx)
print(ans)



### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
M=N**2
P=tuple(map(int1,input().split()))
d=[0]*M
for i in range(N):
    for j in range(N):
        d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
used=[1]*M
ans=0
que=[]
for p in P:
    ans+=d[p]
    used[p]=0
    que.append(p)
    while que:
        x=que.pop()
        for ddx in (-1,1,-N,N):
            nx=x+ddx
            if 0<=nx<M:
                if used[x]==0 and d[nx]-d[x]>=1:
                    d[nx]-=1
                    que.append(nx)
                elif used[x]==1 and d[nx]-d[x]>=2:
                    d[nx]-=1
                    que.append(nx)
print(ans)
### BUGGY CODE ###

#python3
n = int(input())
a = [input() for _ in range(n)]
sep=''
b = [sep.join(sorted(a[i])) for i in range(n)]
dic = {letters: b.count(letters) for letters in set(b)}

ans=0
for i in dic.values():
  ans+=i*(i-1)//2
print(ans)

### FIXED CODE ###

#python3
n = int(input())
s = [str(input()) for _ in range(n)]
sep = ''
dic = dict()
for string in s:
  tmp = sep.join(sorted(string))
  if tmp in dic:
    dic[tmp] += 1 
  else :
    dic[tmp] = 1
ans = 0
for i in dic.values(): 
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

#D - Triangles

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

L_sorted = sorted(L, reverse = False)#昇順

def judge(A,B,x):#cが三角形になるか判定する関数
    if A + B <= L_sorted[x]:#a + b = cの時はfinを持ってくる
        return 'high'
    else :
        return 'low'

count = 0
for i in range(N):#aの選び方
    for j in range(i+1,N):#bの選び方
        a = L_sorted[i]
        b = L_sorted[j]#b <= c < a+b
        sta = 0
        fin = N#Lの個数+1
        while fin > sta + 1:#cの選び方
            m = ((fin - sta) // 2) + sta
            if judge(a,b,m) == 'high':
                fin = m
            elif judge(a,b,m) == 'low':
                sta = m
        count += sta  - j    
print(count)

### FIXED CODE ###

#D - Triangles

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

L_sorted = sorted(L, reverse = False)#昇順

def judge(A,B,x):#cが三角形になるか判定する関数
    if A + B <= L_sorted[x]:#a + b = cの時はfinを持ってくる
        return 'high'
    else :
        return 'low'

count = 0
for i in range(N):#aの選び方
    for j in range(i+1,N):#bの選び方
        a = L_sorted[i]
        b = L_sorted[j]#b <= c < a+b
        sta = 0
        fin = N#Lの個数+1
        while fin > sta + 1:#cの選び方
            m = ((fin - sta) // 2) + sta
            if judge(a,b,m) == 'high':
                fin = m
            elif judge(a,b,m) == 'low':
                sta = m
        count += sta  - j    
print(count)
### BUGGY CODE ###

num, capacity = map(int, input().split())
dp = [0 for i in range(capacity + 1)]

for _ in range(1, num + 1):
    weight, value = map(int, input().split())
    for w in range(capacity,-1,-1):
        if w - weight >= 0:
            dp[w] = max( dp[w - weight] + value,  dp[w] )
print(dp[capacity])

### FIXED CODE ###

def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]

num, capacity = map(int, input().split())
print(calc(num,capacity))