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

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    #%% import
    from itertools import product
    from collections import defaultdict,deque
 
    #%% input
    n=int(input())
    # list-likeでhashableなのはstrとtuple
    Nodes=[(i,j) for i,j in product(range(n),range(n)) if i<j]
    N=len(Nodes) # N=n*(n-1)//2
 
    #%% adjacency list
    outs=defaultdict(list)
    indeg=defaultdict(int)
    for i in range(n):
        edge=list(map(lambda x:int(x)-1,input().split()))
        for j in range(len(edge)-1):
            # (min(i,edge[j]),max(i,edge[j])) to (min(i,edge[j+1]),max(i,edge[j+1]))
            v0 = (min(i,edge[j]),max(i,edge[j]))
            v1 = (min(i,edge[j+1]),max(i,edge[j+1]))
            outs[v0].append(v1)
            indeg[v1]+=1
 
    #%% topological sort
    Q=deque(v for v in Nodes if indeg[v]==0)
    res=[]
    #%%
    while(Q):
        v0=Q.popleft()
        res.append(v0)
        for v1 in outs[v0]:
            indeg[v1]-=1
            if indeg[v1]==0: Q.append(v1)
 
    #%% judge whether G is DAG
    if len(res)<N:
        print("-1")
        return
 
    #%% LPP(Longest Path Problem)
    LP=defaultdict(lambda :1)
    for v0 in res:
        for v1 in outs[v0]:
            LP[v1]=max(LP[v1],LP[v0]+1)
    print(max(LP.values()))
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    match=[[0]*n for _ in range(n)]
    V=0 # V=n(n-1)/2
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

    def toID(i,j):
        if(i>j): i,j=j,i
        return match[i][j]

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    # あとは頂点VのグラフをdfsしてLongest pathの長さを求める
    # -1: unchecked, -2: checked and uncalculated
    dp=[-1]*V
    flag=True
    def dfs(v):
        global flag
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    # calculate
    for i in range(V): dfs(i)
    print(max(dp)+1 if(flag) else -1)
resolve()
### BUGGY CODE ###

import math

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

wsum = sum(w)

def loadable(w, n, k, p, wsum):
    wait = 0
    for i in range(n):
        wait += w[i]
        wsum -= w[i]
        if wait > p:
            k -= 1
            wait = w[i]
            if k == 0:
                return False
    return True

P = max(int(math.ceil(wsum / k)), max(w))

while not loadable(w, n, k, P, wsum):
    P += 1
print(P)

### FIXED CODE ###

import math, sys

def loadable(w, n, k, p, wsum):
    wait = 0
    for i in range(n):
        wait += w[i]
        wsum -= w[i]
        if wait > p:
            k -= 1
            wait = w[i]
            if k == 0 or p < wsum / k:
                return False
    return True

n, k = map(int, sys.stdin.readline().split())
w = [int(sys.stdin.readline()) for _ in range(n)]

wsum = sum(w)

p = max(int(math.ceil(wsum / k)), max(w))
pre_f = p -1
pre_s = None

while True:
    if loadable(w, n, k, p, wsum):
        pre_s = p
    else:
        pre_f = p

    if pre_s != None and pre_s - pre_f == 1:
            break
    
    if pre_s:
        p = int((pre_s + pre_f) / 2)
    else:
        p = math.ceil(p * 1.01)
    
print(pre_s)
### BUGGY CODE ###

import math
import heapq

n, m =map(int,input().split()) 
a =list(map(int, input().split()))
h =[]
for i in a:
    heapq.heappush(h, i*(-1))


while m >0:
    heru = math.ceil((heapq.heappop(h))/2)
    heapq.heappush(h,heru)
    m = m-1
    if sum(h)==0:
        break
print((-1)*sum(h))

### FIXED CODE ###

import math
import heapq

n, m =map(int,input().split()) 
a =list(map(int, input().split()))
h =[]
for i in a:
    heapq.heappush(h, i*(-1))


while m >0:
    heru = math.ceil((heapq.heappop(h))/2)
    heapq.heappush(h,heru)
    m = m-1
print((-1)*sum(h))
### BUGGY CODE ###

S = input()
ans = 0

while 1:
    c = S.count('ABC')
    if c==0: break
    ans += c
    S = S.replace('ABC','BCA')
print(ans)

### FIXED CODE ###

S = input()
S = S.replace('BC','D')
ans = 0
a = 0
for c in S:
    if c=='A':
        a += 1
    elif c=='D':
        ans += a
    else:
        a = 0
print(ans)
### BUGGY CODE ###

# coding: utf-8
from collections import deque
S = deque(input())
Q = int(input())
for i in range(Q):
    q = input().split()
    if q[0] == "1":
        S.reverse()
    else:
        if q[1] == "1":
            S.appendleft(q[2])
        else:
            S.append(q[2])
print("".join(S))


### FIXED CODE ###

# coding: utf-8
from collections import deque
S = deque(input())
Q = int(input())
cnt = 0
for i in range(Q):
    q = input().split()
    if q[0] == "1":
        cnt += 1
    else:
        if (int(q[1]) + cnt) % 2 == 1:
            S.appendleft(q[2])
        else:
            S.append(q[2])
ans = "".join(S)
print(ans if cnt % 2 == 0 else ans[::-1])
### BUGGY CODE ###

n = int(input())
pp = list(input())
cnt = 0
lis = []
for i in range(n):
    for j in range(i):
        if pp[j] == "W":
            cnt += 1
    for k in range(i+1,n):
        if pp[k] =="E":
            cnt += 1
    lis.append(cnt) 
    cnt = 0
print(min(lis))


### FIXED CODE ###

n = int(input())
pp = list(input())
cnt = 0
lis = [0]*n
w = [0]*n
e = [0]*n
if pp[0] =="W":
    w[0] =1
else:
    e[0] =1
for i in range(1,n):
    if pp[i] == "W":
        w[i] = w[i-1]+1
        e[i] = e[i-1]

    else:
        e[i] = e[i-1]+1
        w[i] = w[i-1]
for i in range(1,n):
    lis[i] = w[i-1]+e[n-1]-e[i]
lis[0] = e[n-1]-e[0]

print(min(lis))
### BUGGY CODE ###

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

ans = []
a_s = sorted(a)
for i in range(len(a)):
    for j in range(len(a)):
        if a_s[j]-a_s[i] <= 2:
            ans.append(j-i+1)

print(max(ans))

### FIXED CODE ###


n = int(input())
cnt = [0] * 100002
a = list(map(int, input().split()))
for v in a:
    cnt[v] += 1
    cnt[v+1] += 1
    cnt[v+2] += 1
    
print(max(cnt))
### BUGGY CODE ###

n = input()
sum = 0

for i in range(len(n)):
    sum += int(n[i]) * 10**(len(n) - i - 1)
  
if sum % 9 == 0:
    print("Yes")
  
else:
    print("No")

### FIXED CODE ###

n = input()
sum = 0

for i in range(len(n)):
    sum += int(n[i]) 
  
if sum % 9 == 0:
    print("Yes")
  
else:
    print("No")
### BUGGY CODE ###

a,b,c,k = map(int, open(0).read().split())

if a!=b:
    n,m = 1,0
    for i in range(k):
        n,m = m*2,n+m
    print((a-b)*(n-m))
else:
    print(0)

### FIXED CODE ###

a,b,c,k = map(int, open(0).read().split())

fact = 1
if k%2:
    fact = -1
print((a-b)*fact)
### BUGGY CODE ###

from math import sqrt
import heapq
def dijkstra(G, s):
    dist = [float("inf")]*len(G)
    q = []
    dist[s] = 0
    heapq.heapify(q)
    heapq.heappush(q, [0, s])
    while 0 < len(q):
        pre_cost, p = heapq.heappop(q)
        if dist[p] < pre_cost:
            continue
        for v, d in G[p]:
            if dist[v] > dist[p] + d:
                dist[v] = dist[p] + d
                heapq.heappush(q, [dist[v], v])
    return dist

def calc(arr, i, j):
    d = sqrt((arr[i][0] - arr[j][0])**2 + (arr[i][1] - arr[j][1])**2)
    if arr[i][2] + arr[j][2] <= d:
        return d - arr[i][2] - arr[j][2]
    else:
        return 0

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    arr.append([xs, ys, 0])
    arr.append([xt, yt, 0])
    n += 2
    G = [[[j, calc(arr, i, j)] for j in range(n)] for i in range(n)]
    dist = dijkstra(G, n-2)
    print(dist[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import sqrt
import heapq

def calc(arr, i, j):
    d = sqrt((arr[i][0] - arr[j][0])**2 + (arr[i][1] - arr[j][1])**2)
    if arr[i][2] + arr[j][2] <= d:
        return d - arr[i][2] - arr[j][2]
    else:
        return 0

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    arr.append([xs, ys, 0])
    arr.append([xt, yt, 0])
    n += 2
    st = set()
    for i in range(n):
        st.add(i)
    dist = [float("inf")]*n
    dist[n-2] = 0
    dist[n-1] = calc(arr, n-2, n-1)
    hq = []
    heapq.heappush(hq, [0, n-2])
    while len(hq) > 0:
        _, p = heapq.heappop(hq)
        if p in st:
            st.remove(p)
            for nxt in st:
                d = calc(arr, p, nxt)
                if dist[nxt] > dist[p] + d:
                    dist[nxt] = dist[p] + d
                    heapq.heappush(hq, [dist[nxt], nxt])
    print(dist[-1])

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

import math
def sieve_advance(n):  #n未満の整数iについてi以下でiを割り切る最小の素数を求める。
    minfactor=[-1]*n
    minfactor[0],minfactor[1]=0,1
    isprime=[True]*n
    isprime[0],isprime[1]=False,False

    for i in range(2,n):
        if isprime[i]:
            minfactor[i]=i
            for j in range(i**2,n,i):
                isprime[j]=False
                if minfactor[j]==-1:
                    minfactor[j]=i
    
    return minfactor

minfactor=sieve_advance(10**6+1)
def prime_factor(n): #nをminfactorを利用して素因数分解する
    res={}
    while n!=1:
        prime=minfactor[n]
        exp=0
        while minfactor[n]==prime:
            exp+=1
            n//=prime
        res[prime]=exp

    return res

n=int(input())
nums=list(map(int,input().split()))
mod=10**9+7

factor=[[] for _ in range(n)]
lcm={}
for i in range(n):
  num=nums[i]
  factor[i]=prime_factor(num)
  for p in factor[i].keys():
    e=factor[i][p]
    if p in lcm:
      lcm[p]=max(lcm[p],e)
    else:
      lcm[p]=e
#print(lcm)

b=[1]*n
for p in lcm.keys():
  e_lcm=lcm[p]
  for i in range(n):
    if p in factor[i]:
      e_a=factor[i][p]
    else:
      e_a=0
    b[i]*=p**(e_lcm-e_a) 
    b[i]%=mod
    
#print(b)
print(sum(b)%mod)

### FIXED CODE ###

def main():
  def sieve(n):
    prime=[]
    limit=n*0.5
    data=[i+1 for i in range(1,n)]
    p_append=prime.append
    while True:
        p=data[0]
        if limit<=p:
            return prime+data
        p_append(p)
        data=[e for e in data if e%p!=0]
        
  prime=sieve(1000)
  import sys
  import numpy as np
  input=sys.stdin.readline
  mod=10**9+7
  
  n=int(input())
  num=list(map(int,input().split()))
  num_copy=np.array(num)
  
  lcm=1
  for p in prime:
    while np.any(num_copy%p==0):
      num_copy[num_copy%p==0]//=p
      lcm *= p
      lcm %= mod
  
  for i in set(num_copy.tolist()):
    lcm *= i
    lcm %= mod
    
  #print(lcm,num)
  ans=0
  for i in range(n):
    ans += lcm * pow(num[i] ,mod-2 ,mod)
    ans %= mod 
    #print(ans)
  print(ans)
  
if  __name__=='__main__':
  main()
### BUGGY CODE ###

import sys
import itertools
import collections

input = sys.stdin.readline

def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for _ in range(q):
        n, x, m = map(int, input().split())
        dmodm = [y%m for y in d]
        kmod = (n-1)%k
        kdiv = (n-1)//k
        dmodmCounter = collections.Counter(dmodm)
        dmodmkCounter = collections.Counter(dmodm[:kmod])
        dmodcum = list(itertools.accumulate(dmodm))
        p0 = dmodmCounter[0] * kdiv + dmodmkCounter[0]
        an = x + (kmod != 0) * dmodcum[kmod-1] + dmodcum.pop() * kdiv
        p1 = an//m - x//m
        ans = n - (p0 + p1) - 1
        print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import itertools
import collections

input = sys.stdin.readline

def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for _ in range(q):
        n, x, m = map(int, input().split())
        dmodm = [y%m for y in d]
        kmod = (n-1)%k
        kdiv = (n-1)//k
        cnt = 0; cntm = 0
        for i in range(k):
            cnt += dmodm[i] == 0
            cntm += (dmodm[i] == 0 and i < kmod)
        #dmodmCounter = collections.Counter(dmodm)
        #dmodmkCounter = collections.Counter(dmodm[:kmod])
        dmodcum = list(itertools.accumulate(dmodm))
        #p0 = dmodmCounter[0] * kdiv + dmodmkCounter[0]
        p0 = cnt * kdiv + cntm
        an = x + (kmod != 0) * dmodcum[kmod-1] + dmodcum.pop() * kdiv
        p1 = an//m - x//m
        ans = n - (p0 + p1) - 1
        print(ans)

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

N = int(input())
s = [list(sorted(input())) for i in range(N)]
# s.sort()

ans = 0
for c in s:
        tmp = s.count(c)
        if tmp > 1:
                ans += tmp - 1

print(ans // 2)


### FIXED CODE ###

N = int(input())
s = [list(sorted(input())) for i in range(N)]
s.sort()

ans = []
tmp = 1
for idx,val in enumerate(s):
        if idx == 0:
                continue
        if val == s[idx - 1]:
                tmp += 1
        else:
                ans.append(tmp)
                tmp = 1
else:
        ans.append(tmp)

res = 0
for i in ans:
        res += (i * (i - 1)) // 2
print(res)
### BUGGY CODE ###

A, B, C=map(int,input().split())
K=int(input())
x=0
while x<K:
  if A>B:
    B*=2
    x+=1
  elif B>C:
    C*=2
    x+=1
  elif C>B>A:
    break
if C>B>A:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

A, B, C=map(int,input().split())
K=int(input())
ab=int(A/B)
if ab==0:
  x=0
else:
  x=int(len(bin(ab))-2)
B1=B*(2**x)
bc=int(B1/C)
if bc==0:
  y=0
else:
  y=int(len(bin(bc))-2)
if x+y<=K:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

x=input()
while "S"*10+"T"*10 in x:x=x.replace("S"*10+"T"*10,"")
while "ST" in x:x=x.replace("ST","")
print(len(x))

### FIXED CODE ###

l=[]
for i in input():
    if i=="S":l.append("S")
    elif len(l)==0 or l[-1]=="T":l.append("T")
    else:l.pop()
print(len(l))
### BUGGY CODE ###

import hashlib
M = 15140366

def getkey(text):
    dic = {'A': 1, 'T': 2, 'G': 3, 'C': 4}
    sum = 0
    p = 1
    for c in text:
        sum += p*dic[c]
        p *= 5
    return sum

dict = {}
def find(text):
    global dict
    # key = getkey(text)
    i = 0
    while i < M:
        h = hashlib.md5(text.encode()).hexdigest()
        if dict.get(h) == None:
            break
        elif dict[h] == text:
            return True
        i += 1
    return False

def insert(text):
    global dict
    # key = getkey(text)
    i = 0
    while i < M:
        j = hashlib.md5(text.encode()).hexdigest()
        if dict.get(j) == None:
            dict[j] = text
            break
        else:
            i += 1

n = int(input())
for i in range(n):
    op, text = input().split(' ')
    if op == 'insert':
        insert(text)
    elif op == 'find':
        rst = find(text)
        if rst:
            print('yes')
        else:
            print('no')



### FIXED CODE ###

import sys

M = 1046527
def h1(key):
    return key % M

def h2(key):
    return 1 + (key %(M-1))

def h3(key, i):
    return (h1(key) + i*h2(key)) % M

word_dic = {'A': 1, 'T': 2, 'G': 3, 'C': 4}
def getkey(text):
    sum = 0
    p = 1
    for c in text:
        sum += p*word_dic[c]
        p *= 5
    return sum

dict = [None for i in range(M)]
def find(text):
    key = getkey(text)
    i = 0
    while i < M:
        h = h3(key, i)
        if dict[h] == None:
            break
        elif dict[h] == text:
            return True
        i += 1
    return False

def insert(text):

    key = getkey(text)
    i = 0
    while i < M:
        j = h3(key, i)
        if dict[j] == None:
            dict[j] = text
            break
        else:
            i += 1

n = int(input())
operations = sys.stdin.readlines()
for ope in operations:
    op, text = ope.rstrip().split(' ')
    if op == 'insert':
        insert(text)
    elif op == 'find':
        rst = find(text)
        if rst:
            print('yes')
        else:
            print('no')
### BUGGY CODE ###

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

for _ in range(K):
    B = [0] * N
    for i, d in enumerate(A):
        l = max(0, i - d)
        r = min(N - 1, i + d)
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
    
    for i in range(1, N):
        B[i] += B[i-1]
    
    A = B.copy()
    if min(A) == N:
        break

print(" ".join(map(str, A)))

### FIXED CODE ###

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

for _ in range(K):
    B = [0] * N
    for i, d in enumerate(A):
        l = max(0, i-d)
        r = min(N-1, i+d)
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
    
    for i in range(1, N):
        B[i] += B[i-1]
    
    A = B.copy()
    if min(A) == N:
        break

print(" ".join(map(str, A)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

s=input().rstrip()
n=len(s)
beki=[0 for i in range(n+1)]
beki[0]=1
for i in range(n):
    beki[i+1]=(beki[i]*10)%13

u=[[0 for i in range(13)] for j in range(n+1)]
u[0][0]=1
s=list(reversed(s))
for i in range(n):
    #z=i%3
    for j in range(13):
        if s[i]!="?":
            u[i+1][(j+beki[i]*int(s[i]))%13]+=u[i][j]%mod
        else:
            for k in range(10):
                u[i+1][(j+beki[i]*k)%13]+=u[i][j]%mod
#print(u)
print(u[n][5]%mod)

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

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

H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
Iplus=[[-1 for j in range(W)] for i in range(H)]
Iminus=[[-1 for j in range(W)] for i in range(H)]
Jplus=[[-1 for j in range(W)] for i in range(H)]
Jminus=[[-1 for j in range(W)] for i in range(H)]
for j in range(W):
    if S[0][j]==".":
        Iplus[0][j]=0
for i in range(1,H):
    for j in range(W):
        if S[i][j]==".":
            Iplus[i][j]=Iplus[i-1][j]+1
        else:
            Iplus[i][j]=-1
for j in range(W):
    if S[-1][j]==".":
        Iminus[-1][j]=0
for i in range(H-1)[::-1]:
    for j in range(W):
        if S[i][j]==".":
            Iminus[i][j]=Iminus[i+1][j]+1
        else:
            Iminus[i][j]=-1
for i in range(H):
    if S[i][0]==".":
        Jplus[i][0]=0
for j in range(1,W):
    for i in range(H):
        if S[i][j]==".":
            Jplus[i][j]=Jplus[i][j-1]+1
        else:
            Jplus[i][j]=-1
for i in range(H):
    if S[i][-1]==".":
        Jminus[i][-1]=0
for j in range(W-1)[::-1]:
    for i in range(H):
        if S[i][j]==".":
            Jminus[i][j]=Jminus[i][j+1]+1
        else:
            Jminus[i][j]=-1
ans=0
for i in range(H):
    for j in range(W):
        tmp=Iplus[i][j]+Iminus[i][j]+Jplus[i][j]+Jminus[i][j]+1
        if ans<tmp:
            ans=tmp
            #print(i,j,tmp)
#print(Iplus[2][5],Iminus[2][5],Jplus[2][5],Jminus[2][5])
print(ans)
#for line in Jminus:
#    print(line)
    


### FIXED CODE ###

H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
Iplus=[[-1 for j in range(W)] for i in range(H)]
Iminus=[[-1 for j in range(W)] for i in range(H)]
Jplus=[[-1 for j in range(W)] for i in range(H)]
Jminus=[[-1 for j in range(W)] for i in range(H)]
for j in range(W):
    if S[0][j]==".":
        Iplus[0][j]=0
for i in range(1,H):
    for j in range(W):
        if S[i][j]==".":
            Iplus[i][j]=Iplus[i-1][j]+1
        else:
            Iplus[i][j]=-1
for j in range(W):
    if S[-1][j]==".":
        Iminus[-1][j]=0
for i in range(H-1)[::-1]:
    for j in range(W):
        if S[i][j]==".":
            Iminus[i][j]=Iminus[i+1][j]+1
        else:
            Iminus[i][j]=-1
for i in range(H):
    if S[i][0]==".":
        Jplus[i][0]=0
for j in range(1,W):
    for i in range(H):
        if S[i][j]==".":
            Jplus[i][j]=Jplus[i][j-1]+1
        else:
            Jplus[i][j]=-1
for i in range(H):
    if S[i][-1]==".":
        Jminus[i][-1]=0
for j in range(W-1)[::-1]:
    for i in range(H):
        if S[i][j]==".":
            Jminus[i][j]=Jminus[i][j+1]+1
        else:
            Jminus[i][j]=-1
ans=0
for i in range(H):
    for j in range(W):
        tmp=Iplus[i][j]+Iminus[i][j]+Jplus[i][j]+Jminus[i][j]+1
        if ans<tmp:
            ans=tmp
            #print(i,j,tmp)
#print(Iplus[2][5],Iminus[2][5],Jplus[2][5],Jminus[2][5])
print(ans)
#for line in Jminus:
#    print(line)
### BUGGY CODE ###

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

sv = {}
for ww, vv in a:
    added = {}
    for k, v in sv.items():
        added[ww+k] = vv+v
    for k, v in added.items():
        if (k <= w) and (k not in sv or v > sv[k]):
            sv[k] = v

    if (ww <= w) and (ww not in sv or vv > sv[ww]):
        sv[ww] = vv

print(max(sv.values()))

### FIXED CODE ###

import numpy as np

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

s = np.full(1000*100+1, 10**11, dtype=np.int64)
s[0] = 0
for i in range(n):
    w, v = map(int, input().split())
    s[v:] = np.minimum(s[v:], s[:-v] + w)

print(np.max(np.where(s<=ww)))