Harryxun/stf_run huggingface dataset:
from collections import Counter
import math
MOD=10**9+7
N=int(input())
li=[]
for i in range(N):
    A,B=map(int,input().split())
    g=math.gcd(A,B)
    li.append((A//g,B//g))
c=Counter(li)
dic={}
ans=1
for a,b in c.keys():
    if (a,b) in dic:
        continue
    l,r=(-b,a),(b,-a)
    s=c.get(l,0)+c.get(r,0)
    dic[l],dic[r]=1,1
    res=(pow(2,c[(a,b)],MOD)+pow(2,s,MOD)-1)%MOD
    ans=(ans*res)%MOD
print(ans-1)

### FIXED CODE ###

from collections import Counter
import math
MOD=10**9+7
N=int(input())
li=[]
zcnt=0
az,bz=0,0
for i in range(N):
    A,B=map(int,input().split())
    if A==0 and B==0:
        zcnt+=1
        continue
    if A!=0 and B==0:
        bz+=1
        continue
    elif A==0 and B!=0:
        az+=1
        continue
    g=math.gcd(A,B)
    if A<0 and B<0:
        li.append((-(A//g),-(B//g)))
    elif A<0 and B>0:
        li.append((-(A//g),-(B//g)))
    else:
        li.append((A//g,B//g))
c=Counter(li)
dic={}
ans=(pow(2,az,MOD)+pow(2,bz,MOD)-1+MOD)%MOD
for a,b in c.keys():
    if (a,b) in dic:
        continue
    l,r=(-b,a),(b,-a)
    s=c.get(l,0)+c.get(r,0)
    dic[l],dic[r]=1,1
    res=(pow(2,c[(a,b)],MOD)+pow(2,s,MOD)-1+MOD)%MOD
    ans=(ans*res)%MOD
print((ans-1+zcnt)%MOD)
import math

N,X = map(int,input().split())
x = list(map(int,input().split()))
if N == 1:
    print((x[0] - X))
else:
    xlen = [(x[0]-X)]
    for i in range(N-1):
        xlen.append(x[i+1]- x[i])
    ans = xlen[0]
    for i in range(1,N):
        ans = math.gcd(ans,xlen[i])
    print(ans)

### FIXED CODE ###

def gcd(a,b) :
    if b>0 :
        return gcd(b,a % b)
    elif b == 0:
        return a


N,X = map(int,input().split())
x = list(map(int,input().split()))
if N == 1:
    print(abs(x[0] - X))
else:
    xlen = []
    for i in range(N):
        xlen.append(abs(x[i] - X))
        #print(xlen[i])
    ans = xlen[0]
    for i in range(1,N):
        ans = gcd(ans,xlen[i])
        #print(ans)
    print(ans)
N=int(input())
S=str(input())
for i in range(len(S)-1):
    if S[i]==S[i+1]:
        idx=i        
idx=idx+1
sub_X=S[:idx]
sub_Y=S[idx:]
import collections
count_list_X=list(collections.Counter(sub_X).keys())
count_list_Y=list(collections.Counter(sub_Y).keys())
max_count=0
count=0
for str1 in count_list_X:
    for str2 in count_list_Y:
        if str1==str2:
            count+=1
if count>max_count:
    max_count=count
print(max_count)

### FIXED CODE ###

N=int(input())
S=list(input())
a=[]

for i in range(1,N):
    x=set(S[:i-1:])
    y=set(S[i-1::])
    a.append(len(list(x&y)))
    
print(max(a))
x = input()
print(x**3)



### FIXED CODE ###

x = int(input())
print(x ** 3)
N = int(input())
X = input()
ans = [1 for _ in range(N)]
#original 1 count
l = 0
for k in range(N):
  if X[k] == '1':
    l+=1


intN = int(X, 2)
if l >1:
  N1 = intN %(l-1)
N0 = intN % (l+1)


start = []
if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()
else:
  s1 = 1
  s0 = 1
  for k in range(N-1, -1, -1):
    if X[k] == '1':
      if l == 1:
        ans[k] = 0
        ia =0
      else:  
        ia = (N1 - s1)%(l-1)
    else:
      ia = (N0 + s0)%(l+1)
    start.append(ia)
    s1 = s1*2%(l-1)
    s0 = s0*2%(l+1)
start = start[::-1]
"""
ml = len(bin(l+1))-2
poplist = [0 for _ in range(N)]
t = 1
while t < N + 1:
  t *= 2
  for k in range(t//2, N, t):
    for j in range(t//2):
      if k+j>N-1:
        break
      poplist[k+j] += 1
"""

def popcount(n):
  c = 0
  n = bin(n)[2:]
  for k in range(len(n)):
    if n[k] == '1':
      c+=1
  return c

for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % popcount(start[k])

for k in range(N):
  print(ans[k])

### FIXED CODE ###

N = int(input())
X = input()
ans = [1 for _ in range(N)]
#original 1 count
l = 0
for k in range(N):
  if X[k] == '1':
    l+=1
if l == 0:
  for _ in range(N):
    print(1)
  exit()
if l == 1:
  if X[-1] == '1':
    for _ in range(N-1):
      ans[_] = 2
  else:
    ans[-1] = 2 
  for k in range(N):
    if X[k] =='1':
      ans[k] = 0 
  for _ in range(N):
    print(ans[_])
  exit()


intN = int(X, 2)
N1 = intN %(l-1)
N0 = intN % (l+1)


start = []
if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()
else:
  s1 = 1
  s0 = 1
  for k in range(N-1, -1, -1):
    if X[k] == '1':      
      ia = (N1 - s1)%(l-1)
    else:
      ia = (N0 + s0)%(l+1)
    start.append(ia)
    s1 = s1*2%(l-1)
    s0 = s0*2%(l+1)
start = start[::-1]
"""
ml = len(bin(l+1))-2
poplist = [0 for _ in range(N)]
t = 1
while t < N + 1:
  t *= 2
  for k in range(t//2, N, t):
    for j in range(t//2):
      if k+j>N-1:
        break
      poplist[k+j] += 1
"""

def popcount(n):
  c = 0
  n = bin(n)[2:]
  for k in range(len(n)):
    if n[k] == '1':
      c+=1
  return c

for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % popcount(start[k])

for k in range(N):
  print(ans[k])
import numpy as np


def main():
    N = int(input())
    A = np.array(list(map(int, input().split())))

    B = np.zeros([N, N])
    np.fill_diagonal(B, 1)
    ps = list(range(1, N)) + [0]
    B = B[ps, :]
    np.fill_diagonal(B, 1)
    iB = np.linalg.inv(B)

    X = np.dot(iB, A) * 2
    X = X.astype(np.int32)
    print(*X)


main()


### FIXED CODE ###

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

ans = [0 for _ in range(N)]

sign = 1
for a in A:
    ans[0] += sign * a
    sign *= -1


for i in range(1, N):
    ans[i] = 2 * A[0] - ans[i - 1]

    t = A.pop(0)
    A.append(t)

print(*ans)
from  itertools import combinations
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]
li = list(combinations(use_li*3,3))
sum_li = []
for i in get_unique_list(li):
  sum_li.append(reduce(gcd,i))
sum(sum_li)

### FIXED CODE ###

from math import gcd
from functools import reduce

def func(a,b,c):
  if a == b and b == c:
    return a
  elif a == b and b !=c:
    return gcd(a,c)
  elif a != b and b ==c:
    return gcd(a,b)
  else:
    return reduce(gcd,(a,b,c))

k = int(input())
li = []
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      li.append(func(a,b,c))

print(sum(li))
n = list(map(int, input().split()))
flg = 0
if n[0]==7:
  flg = 1
if n[1]==7:
  flg = 1
if n[2]==7:
  flg = 1

if flg == 1:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

n = list(map(int, input()))
flg = 0
if n[0]==7:
  flg = 1
if n[1]==7:
  flg = 1
if n[2]==7:
  flg = 1

if flg == 1:
  print('Yes')
else:
  print('No')
n,k = map(int,input().split())
x = list(map(int,input().split()))

m = []
p = []
for i in range(n):
    if x[i] < 0:
        m.append(x[i])
    elif x[i] > 0:
        p.append(x[i])

if m and p:
    z = len(m)-1
    if k-len(m) > 0:
        s = 0
    else:
        s = abs(k-len(m))+1
    
    i = 0
    ans = float('inf')
    while z+s+i < n and s+i < len(m):
        ans = min(ans, min(abs(x[s+i])*2 + abs(x[k-1+s+i]), abs(x[s+i]) + abs(x[k-1+s+i])*2))
        i += 1
        
    print(ans)
elif m:
    print(abs(x[-k]))
elif p:
    print(x[k-1])
else:
    print(0)

### FIXED CODE ###

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

if len(x) == 1 and x[0] == 0:
    print(0)
    exit()

m = []
p = []
for i in range(n):
    if x[i] < 0:
        m.append(x[i])
    elif x[i] > 0:
        p.append(x[i])

ans = float('inf')
if len(m) >= k:
    ans = min(ans,abs(m[-k]))
    m = m[-k+1:]
if len(p) >= k:
    ans = min(ans,p[k-1])
    p = p[:k-1]

x = m+p
i = 0
for i in range(len(x)-k+1):
    ans = min(ans, min(abs(x[i])*2+abs(x[i+k-1]), abs(x[i])+abs(x[i+k-1])*2))

print(ans)
a, b, c, d = map(int, raw_input().split())
print(a*b if a*b > c*d else c*d)

### FIXED CODE ###

a, b, c, d = map(int, raw_input().split())
print a*b if a*b > c*d else c*d
n,k=map(int,input().split())
s=input()
a=s[k-1].lower
print(s[:k-1]+a+s[k:])

### FIXED CODE ###

n,k=map(int,input().split())
s=input()
print(s[:k-1]+s[k-1].lower()+s[k:])
import sys

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

for i in range(x + 1):
  for j in range(x + i):
    if i * 2 + j * 4 == y and i + j == X:
      print('yes')
      sys.exit()
 
print('no')
      

### FIXED CODE ###

x, y = map(int, input().split())
ans = 'No'

for i in range(x + 1):
	j = x - i
	if i * 2 + j * 4 == y:
		ans = 'Yes'
print(ans)
S=input()
T=input()
ans=0
for i in range(3):
if s[i]=s[i]:
ans+=1
print(ans)

### FIXED CODE ###

S=input()
T=input()
ans=0
for i in range(3):
 if S[i]==T[i]:
     ans+=1
print(ans)
print(input()[::2])

### FIXED CODE ###

print(input()[::2])
K,X=map(int,input().split)

if 500*K>=X:
  print("yes")
else:
  print("no")

### FIXED CODE ###

K,X=map(int,input().split())

if 500*K >= X:
  print('Yes')
else:
  print('No')
import math
a,b = map(int,input().split())

def trial(k):
    factor = []
    m = int(math.sqrt(k)) + 1
    for i in range(2,m):
        while k % i == 0:
            k = k // i
            factor.append(i)
    if not factor:
        return [1,k]
    else:
        factor.append(k)
        factor.append(1)
        return factor

k = gcd(a,b)

ps = trial(k)

count = 1
for i in range(len(ps)-1):
    if ps[i] != ps[i + 1]:
        count += 1
        
print(count)



### FIXED CODE ###

import math
def gcd(a,b):
    while a > 0 and b > 0:
        if a > b:
            a = a % b
        elif a < b:
            b = b % a
        else:
            b = 0
    return max(a,b)

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

def trial(k):
    factor = []
    m = int(math.sqrt(k)) + 1
    for i in range(2,m):
        while k % i == 0:
            k = k // i
            factor.append(i)
    if not factor:
        return [1,k]
    else:
        factor.append(k)
        factor.append(1)
        return factor

k = gcd(a,b)

ps = trial(k)

count = 1
for i in range(len(ps)-1):
    if ps[i] != ps[i + 1]:
        count += 1

print(count)
n,a,b = map(int,input().split())
ans = 0

for i in range(n+1):
    if a<= sum(list(map(int,list(str(i))) <=b:
        ans += i
print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())
ans = 0
for i in range(n+1):
    if a <= sum(list(map(int, list(str(i))))) <= b:
        ans += i
print(ans)
import sys
input = sys.stdin.readline

n = int(input())
uvw = [list(map(int, input().split())) for _ in range(n-1)]

graph = [[] for _ in range(n)]
for i in range(n-1):
    graph[uvw[i][0]-1].append((uvw[i][1]-1, uvw[i][2]))
    graph[uvw[i][1]-1].append((uvw[i][0]-1, uvw[i][2]))

stack = [0]
visited = []
ans = [0]*n
while stack:
    node = stack.pop()
    visited.append(node)
    for child in graph[node]:
        if child[0] not in visited:
            stack.append(child[0])
            if child[1]%2 == 0:
                ans[child[0]] = ans[node]
            else:
                ans[child[0]] = (ans[node]+1)%2

[print(ans[i]) for i in range(n)]


### FIXED CODE ###


n,k = map(int, input().split())
s = input()

s_temp = s.swapcase()

ans = s[:k-1]+s_temp[k-1]+s[k:]

print(ans)
n,t=map(int,input().split())
a=[int(i) for i in input().split()]
p=a[0]
c=0
for i a:
  c+=t-i if p+t>i else t
print(c)

### FIXED CODE ###

n,T=map(int,input().split())
t=[int(i) for i in input().split()]
ans=0
pre=t[0]
for i in range(1,n):
    c=t[i]
    if c-pre>T:
        ans+=T
    else:
        ans+=c-pre
    pre=c
print(ans+T)
print(chr(ord(input()+1)

### FIXED CODE ###

c=input()
print(chr(ord(c)+1))
if __name__ == "__main__":
    n = int(input())
    """studentNumbers = [(x, str(i)) for x, i in
        zip(input().split(), range(1, 1000000))]
    studentNumbers.sort(key=lambda tup: tup[0])
    print(' '.join([x[1] for x in studentNumbers]))"""
    studentNumbers = [(str(i + 1), x) for i, x in enumerate(input().split())]
    if (n > 1):
        studentNumbers.sort(key=lambda tup: tup[1])
    print(' '.join([x[0] for x in studentNumbers]))


### FIXED CODE ###

from math import ceil

if __name__ == "__main__":
    n = int(input())
    print(ceil(n/2)/n)
# -*- coding: utf-8 -*-

import math
import functools

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

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

max_under_lcm = functools.reduce(lcm, numbers) - 1
answer = sum([ max_under_lcm % n for n in numbers])

print(answer)

### FIXED CODE ###

import functools
import fractions

N = int(input())
numbers = list(map(int, input().split()))
answer = sum([n - 1 for n in numbers])

print(answer)
s,t = input().split()
if s == t[:-1]:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = input()
t = input()
if s == t[:-1]:
    print('Yes')
else:
    print('No')
def coin(a, b, c):

    global count
    global m

    if a % c[0] == 0:

        count = min(count, b + a // c[0])

        return count

    elif b + a // c[0] >= count:

        return n

    elif c[0] < n:

        return min(coin(a - c[0], b + 1, c), cs(a, b, c[1:]))

    else:

        return coin(a, b, c[1:])


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

money = sorted(list(map(int, input().split())), reverse = True)

count = print(coin(n, 0, money))


### FIXED CODE ###

def coin(n, p, c):
    global count
    global m
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] >= count:
        return n
    elif c[0] < n:
        return min(coin(n - c[0], p + 1, c), coin(n, p, c[1:]))
    else:
        return coin(n, p, c[1:])

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

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

mon.sort(reverse = True)

count = n

print(coin(n, 0, mon))
def resolve():
    from collections import deque
    n, m = map(int, input().split())
    a = deque(map(int, input().split()))

    for i in range(m):
        a = deque(sorted(a))
        maxa = a.pop()
        maxa //= 2
        a.appendleft(maxa)
    print(sum(a))
resolve()

### FIXED CODE ###

def resolve():
    n,k,q = map(int, input().split())
    a = [int(input()) for i in range(q)]
    point = [0]*n
    for i in range(q):
        point[a[i]-1] += 1
    for j in range(n):
        if k-q+point[j] > 0:
            print("Yes")
        else:
            print("No")
resolve()
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def make_divisors(n): #約数列挙の関数を一部改変
    lower_divisors , upper_divisors = [], [] 
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    if i == 1:
        return 1
    else:
        return upper_divisors[-1]

N = int(readline())
ans = make_divisors(N)
print(len(str(ans)))

### FIXED CODE ###

n = int(input())
ans = float('inf')
for i in range(1,int(n**0.5) + 1):
  if n % i == 0:
    ans = min(ans,len(str(n // i)))
print(ans)
n = int(input())
li = []
for i in range(n):
    command = input().split()
    if command[0] == 'insert':
        li.insert(0, command[1])
    elif command[0] == 'delete':
        li.remove(command[1])
    elif command[0] == 'deleteFirst':
        li.pop(0)
    else:
        li.pop()
print(*li)

### FIXED CODE ###

from collections import deque
import sys
 
dq = deque()
num = int(sys.stdin.readline())
line = sys.stdin.readlines()
 
for i in range(num):
 
    order = line[i].split()
 
    if order[0] == 'insert':
        dq.appendleft(order[1])
    elif order[0] == 'deleteFirst':
        dq.popleft()
    elif order[0] == 'deleteLast':
        dq.pop()
    else:
        if order[1] in dq:
            dq.remove(order[1])
 
print(' '.join(dq))
N = int(input())
Lifes = map(int, input().split())

Lifes.sort(key=lambda x:-x)

ans = Lifes[N-1]

for i in range(N):
  for j in range(i, N):
    life = Lifes[i] - Lifes[j]
    if life > 0:
	  ans = min(ans, life)
print(ans)

### FIXED CODE ###

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

Lifes.sort(key=lambda x:-x)

ans = Lifes[N-1]

# for i in range(N):
#   for j in range(i, N):
#     life = Lifes[i]%Lifes[j]
#     if life > 0:
#       ans = min(ans, life)
# print(ans)

update = True
while update:
    min_num = ans
    for i in range(N):
        life_mod = Lifes[i]%ans
        if life_mod > 0:
            Lifes[i] = life_mod
            if min_num > life_mod:
                min_num = life_mod
    if ans == min_num:
        update=False
    else:
        ans = min_num
print(ans)
S,T = map(str,imput().split())
print(S + T)


### FIXED CODE ###

S,T = map(str,input().split())
print(T + S)
n = int(input())
int_list = list(map(int, input().split()))
count = 0
while True:
    isOdd = False
    for i in range(n):
        if(int_list[i] % 2 != 0):
            isOdd = True
    if isOdd:
        break
    for i in range(n):
        int_list[i] = int_list[i]/2
    count = count + 1
print(count)


### FIXED CODE ###

str_list = input()
count = 0
if str_list[0] == '1':
  count = count + 1
if str_list[1] == '1':
  count = count + 1
if str_list[2] == '1':
  count = count + 1
print(count)
ar = list(input())
br = set(ar)
if br.count("N") == br.count("S") and br.count("W") == br.count("E"):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

ar = list(input())
br = set(ar)
if len(br) == 4:
    print("Yes")
elif len(br) == 1 or len(br) == 3:
    print("No")
else:
    if "N" in br and "S" in br:
        print("Yes")
    elif "E" in br and "W" in br:
        print("Yes")
    else:
        print("No")
from copy import deepcopy
from collections import deque
import sys
input = sys.stdin.readline

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

C = deepcopy(B)
C.reverse()
C = deque(C)

ans = deque([])

for i in range(N):
    p = C.popleft()
    if A[i] != p:
        ans.append(p)
        continue
    q = C.pop()
    if A[i] != q:
        C.append(p)
        ans.append(q)
        continue

    print("No")
    exit()
print("Yes")
print(*ans)


### FIXED CODE ###

"""
T E S T
"""

from collections import Counter, deque

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

cnt_a = Counter(A)
cnt_b = Counter(B)

cnt_ab = cnt_a + cnt_b

for i in cnt_ab.values():
    if i > N:
        print("No")
        exit()


print("Yes")
dq_a = deque(A)
dq_b = deque(B)

ans = []

dq_b.rotate(N // 2)

while dq_a:
    if dq_a[0] != dq_b[0]:
        dq_a.popleft()
        p = dq_b.popleft()
        ans.append(p)
        # ans.append(b.popleft())
    else:
        dq_b.rotate()
print(*ans)
from math import factorial,sqrt,ceil,gcd
import numpy as np

N = int(input())
lisA = list(map(int,input().split()))
arrA = np.array(lisA)

mean = np.mean(arrA)

targetnum = round(mean)

arrans = (arrA - targetnum)**2
ans = sum(arrans)

print(ans)

### FIXED CODE ###

from math import factorial,sqrt,ceil#,gcd
import numpy as np

N = int(input())
lisA = list(map(int,input().split()))
arrA = np.array(lisA)

mean = np.mean(arrA)

targetnum = round(mean)

arrans = (arrA - targetnum)**2
ans = sum(arrans)

print(int(ans))
a,b,c,d = map(int, input().split())
if b < c or d < a:
    print("No")
else:
    print("Yes")

### FIXED CODE ###

k = int(input())

ans = "ACL" * k

print(ans)
import sys
from collections import deque
from functools import reduce
import copy
import math


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    n = int(inputs[0])
    LIMIT = 100000
    sixs = [6]
    nines = [9]
    while sixs[-1] <= LIMIT:
        sixs.append(6 * sixs[-1])
    sixs.pop()
    while nines[-1] <= LIMIT:
        nines.append(9 * nines[-1])
    nines.pop()

    choises = [1, *sixs, *nines]
    # [count]
    dp = [0]

    for i in range(1, n+1):
        candidates = []
        for c in choises:
            if i - c >= 0:
                candidates.append(dp[i-c] + 1)
        dp.append(min(candidates))

    return dp[-1]


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)


### FIXED CODE ###

import sys
from collections import deque
from functools import reduce
import copy
import math


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    n = int(inputs[0])
    LIMIT = 100000
    sixs = [6]
    nines = [9]
    while sixs[-1] <= LIMIT:
        sixs.append(6 * sixs[-1])
    sixs.pop()
    while nines[-1] <= LIMIT:
        nines.append(9 * nines[-1])
    nines.pop()

    choises = [1]
    choises.extend(sixs)
    choises.extend(nines)

    # [count]
    dp = [0]

    for i in range(1, n+1):
        candidates = []
        for c in choises:
            if i - c >= 0:
                candidates.append(dp[i-c] + 1)
        dp.append(min(candidates))

    return dp[-1]


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)
N,W,*l = map(int,open(0).read().split())
wl = l[::2]
vl = l[1::2]
M = N*max(vl)
INF = float("inf")
dp = [[INF]*(M+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
	w,v = wl[i],vl[i]
	for j in range(M+1):
		if j >= v:
			dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
		else:
			dp[i+1][j] = dp[i][j]

ans=0
for val,wei in enumerate(dp[-1]):
	if wei <= W:
		ans = max(ans,val)
print(ans)


### FIXED CODE ###

N,W,*L=map(int,open(0).read().split())
w1=L[0]
l=[[] for _ in range(4)]
for w,v in zip(*[iter(L)]*2):
	l[w-w1].append(v)
l=[sorted(t)[::-1] for t in l]
a,b,c,d=map(len,l)
ans=0
for h in range(a+1):
	for i in range(b+1):
		for j in range(c+1):
			for k in range(d+1):
				if w1*h+(w1+1)*i+(w1+2)*j+(w1+3)*k<=W:
					ans=max(ans,sum(l[0][:h]+l[1][:i]+l[2][:j]+l[3][:k]))
print(ans)
from sys import stdin

def main():
  def find(parent, i):
    t = parent[i]
    if t == -1:
      return i
    t = find(parent, t)
    parent[i] = t
    return t

  def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
      return
    parent[i] = j

  from builtins import int, map, range
  readline = stdin.readline()

  n, k, l = map(int, readline().split())

  roads = [-1] * n
  rails = [-1] * n

  for i in range(k):
    p, q = map(int, readline().split())
    unite(roads, p - 1, q - 1)

  for i in range(l):
    p, q = map(int, readline().split())
    unite(rails, p - 1, q - 1)

  d = {}
  for i in range(n):
    t = (find(roads, i), find(rails, i))
    if t in d:
      d[t] += 1
    else:
      d[t] = 1

  print(*[d[(find(roads, i), find(rails, i))] for i in range(n)])

main()


### FIXED CODE ###

from sys import stdin

def find(parent, i):
  if parent[i] == i:
    return i
  parent[i] = find(parent, parent[i])
  return parent[i]

def unite(parent, i, j):
  i = find(parent, i)
  j = find(parent, j)
  if i == j:
    return
  parent[i] = j

n, k, l = map(int, stdin.readline().split())

roads = list(range(n))
rails = list(range(n))

for i in range(k):
  p, q = map(int, stdin.readline().split())
  unite(roads, p - 1, q - 1)

for i in range(l):
  p, q = map(int, stdin.readline().split())
  unite(rails, p - 1, q - 1)

d = {}
for i in range(n):
  t = (find(roads, i), find(rails, i))
  if t in d:
    d[t] += 1
  else:
    d[t] = 1

print(*[d[(find(roads, i), find(rails, i))] for i in range(n)])
#!/usr/bin/env python

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

if a == b:
    print(c)
elif b == c:
    print(a)
elif c == a:
    print(b)
else
    pass

### FIXED CODE ###

#!/usr/bin/env python

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

if a == b:
    print(c)
elif b == c:
    print(a)
elif c == a:
    print(b)
else:
    pass