CodeEff/ECCO huggingface dataset:
# Original solution
def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

B,W=list(map(int,input().split()))

p=[1]
for i in range(1,B+W+1) :
    p.append((p[-1]*inverse[2])%mod)

BD=[0]
for i in range(1,B+W+1):
    t=(BD[-1]+cmb(i-1,B-1,mod)*p[i])%mod
    BD.append(t)

WD=[0]
for i in range(1,B+W+1):
    t=(WD[-1]+cmb(i-1,W-1,mod)*p[i])%mod
    WD.append(t)

for i in range(1,B+W+1):
    ans=(1-BD[i-1]-WD[i-1])*p[1]+WD[i-1]
    ans%=mod
    print(ans)

# Optimized solution
def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import sys
write=sys.stdout.write

B,W=list(map(int,input().split()))

p=[1]
for i in range(1,B+W+1) :
    p.append((p[-1]*inverse[2])%mod)

BD=[0]
for i in range(1,B+W+1):
    t=(BD[-1]+cmb(i-1,B-1,mod)*p[i])%mod
    BD.append(t)

WD=[0]
for i in range(1,B+W+1):
    t=(WD[-1]+cmb(i-1,W-1,mod)*p[i])%mod
    WD.append(t)

for i in range(1,B+W+1):
    ans=(1-BD[i-1]-WD[i-1])*p[1]+WD[i-1]
    ans%=mod
    write(str(ans)+"\n")
# Original solution
B,W = list(map(int, input().split()))
N = B+W

factorial = [1]
for i in range(N+1):
    factorial.append( factorial[-1] * (i+1))
# print(factorial)

mod = 10**9+7

de_factorial = [0] * (N+1)
de_factorial[N] = pow(  factorial[N] , mod-2, mod  )

for i in range( N, 0, -1):
    de_factorial[i-1] = de_factorial[i] * i % mod
    
def comb(n,r):
    if n < r: return 0
    if n == r: return 1
    return (factorial[n] * de_factorial[r] * de_factorial[n-r]) % mod


p = [0] * (N+1) # Bを食べきった確率
q = [0] * (N+1) # Wを食べきった確率

de2 = de_factorial[2]
for i in range(1, N+1):
    p[i] = p[i-1] + comb(i-1 ,B-1) * de2 % mod 
    q[i] = q[i-1] + comb(i-1 ,W-1) * de2  % mod 
    de2 = de2 * de_factorial[2] % mod

    tmp = ( q[i-1] + 1-p[i-1] ) * de_factorial[2] % mod
    
    print(tmp)

# Optimized solution
B,W = list(map(int, input().split()))
N = B+W
mod = 10**9+7

factorial = [1]
for i in range(N+1):
    factorial.append( factorial[-1] * (i+1) % mod)
# print(factorial)



de_factorial = [0] * (N+1)
de_factorial[N] = pow(  factorial[N] , mod-2, mod  )

for i in range( N, 0, -1):
    de_factorial[i-1] = de_factorial[i] * i % mod
    
def comb(n,r):
    if n < r: return 0
    if n == r: return 1
    return (factorial[n] * de_factorial[r] * de_factorial[n-r]) % mod


p = [0] * (N+1) # Bを食べきった確率
q = [0] * (N+1) # Wを食べきった確率

de2 = de_factorial[2]
for i in range(1, N+1):
    p[i] = p[i-1] + comb(i-1 ,B-1) * de2 % mod 
    q[i] = q[i-1] + comb(i-1 ,W-1) * de2  % mod 
    de2 = de2 * de_factorial[2] % mod

    tmp = ( q[i-1] + 1-p[i-1] ) * de_factorial[2] % mod
    
    print(tmp)
# Original solution
B, W = list(map(int,input().split()))
Mod = 10**9+7
magick = 500000004

inv_t = [0]+[1]
for i in range(2,B+W+1):
   inv_t += [inv_t[Mod % i] * (Mod - int(Mod / i)) % Mod]

consts_B, consts_W = [0]*(B-1)+ [1], [0]*(W-1)+[1]
for i in range(B+W):
  if i >= B: consts_B += [consts_B[-1]*(i)*inv_t[i-B+1]%Mod]
  if i >= W: consts_W += [consts_W[-1]*(i)*inv_t[i-W+1]%Mod]

p, q = 0, 0
inv = 1
for i in range(B+W):
  print(((1-p+q)*magick%Mod))
  inv *= magick%Mod
  p += consts_B[i]*inv
  q += consts_W[i]*inv

# Optimized solution
B, W = list(map(int,input().split()))
Mod = 10**9+7
magick = 500000004

inv_t = [0]+[1]
inv_2 = [0]+[magick]
for i in range(2,B+W+1):
  inv_t += [inv_t[Mod % i] * (Mod - int(Mod / i)) % Mod]
  inv_2 += [inv_2[-1]*magick % Mod]

consts_B, consts_W = [0]*(B-1)+ [1], [0]*(W-1)+[1]
for i in range(B+W):
  if i >= B: consts_B += [consts_B[-1]*(i)*inv_t[i-B+1]%Mod]
  if i >= W: consts_W += [consts_W[-1]*(i)*inv_t[i-W+1]%Mod]

p, q = 0, 0
for i in range(B+W):
  print(((1-p+q)*magick%Mod))
  p += consts_B[i]*inv_2[i+1]
  q += consts_W[i]*inv_2[i+1]
# Original solution
from fractions import Fraction
B, W = list(map(int, input().split()))


def ExtendedEuclidianAlgorithms(a, b):
    """
    返り値: 自然数a, bの最小公倍数d, ax+by=gcd(a, b)を満たす(x, y)が、
    (d, x, y)のtuple
    d = 1ならxはaの逆元(inverse element)
    """
    d, c1 = a, b
    x0, x1 = 1, 0
    y0, y1 = 0, 1
    while c1 != 0:
        m = d % c1
        q = d // c1
        d, c1 = c1, m
        x0, x1 = x1, (x0 - q * x1)
        y0, y1 = y1, (y0 - q * y1)
    return d, x0, y0


def makeTable(N):
    table = [1]
    for i in range(1, N+1):
        table.append(table[-1]*i)
    return table


def binomialCoefficient(N, r, MOD=1):
    if MOD == 1:
        return int(table[N] / (table[N - r] * table[r]))
    else:
        return int(table[N] / (table[N - r] * table[r])) % MOD


table = makeTable(B+W)
mod = 10 ** 9 + 7
P = [Fraction(0, 1)]
Q = [Fraction(0, 1)]


def unknown(x, y, mod=10**9+7):
    g, a, b = ExtendedEuclidianAlgorithms(x, mod)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return a*y % mod


for i in range(B + W):
    if i == 0:
        print((500000004))
        continue
    p = Fraction(P[-1]) + Fraction(binomialCoefficient(i - 1, B - 1, mod), 2 ** i)
    q = Fraction(Q[-1]) + Fraction(binomialCoefficient(i - 1, W - 1, mod), 2 ** i)
    P.append(p)
    Q.append(q)
    ans = Fraction((1 - Fraction(P[-1]) + Fraction(Q[-1])), 2)
    bunshi, bunbo = ans.numerator, ans.denominator
    ans = unknown(bunbo, bunshi)
    print(ans)


# Optimized solution
from fractions import Fraction
B, W = list(map(int, input().split()))


def ExtendedEuclidianAlgorithms(a, b):
    """
    返り値: 自然数a, bの最小公倍数d, ax+by=gcd(a, b)を満たす(x, y)が、
    (d, x, y)のtuple
    d = 1ならxはaの逆元(inverse element)
    """
    d, c1 = a, b
    x0, x1 = 1, 0
    y0, y1 = 0, 1
    while c1 != 0:
        m = d % c1
        q = d // c1
        d, c1 = c1, m
        x0, x1 = x1, (x0 - q * x1)
        y0, y1 = y1, (y0 - q * y1)
    return d, x0, y0


def makeTableMod(N, mod=10**9+7):
    table = [1]
    for i in range(1, N+1):
        table.append((table[-1]*i)%mod)
    return table


def binomialCoefficient(N, r, MOD=1):
    if MOD == 1:
        return int(table[N] / (table[N - r] * table[r]))
    else:
        return int(table[N] / (table[N - r] * table[r])) % MOD


table = makeTableMod(B+W)
mod = 10 ** 9 + 7
P = [Fraction(0, 1)]
Q = [Fraction(0, 1)]


def unknown(x, y, mod=10**9+7):
    g, a, b = ExtendedEuclidianAlgorithms(x, mod)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return a*y % mod


for i in range(B + W):
    if i == 0:
        print((500000004))
        continue
    p = Fraction(P[-1]) + Fraction(binomialCoefficient(i - 1, B - 1, mod), 2 ** i)
    q = Fraction(Q[-1]) + Fraction(binomialCoefficient(i - 1, W - 1, mod), 2 ** i)
    P.append(p)
    Q.append(q)
    ans = Fraction((1 - Fraction(P[-1]) + Fraction(Q[-1])), 2)
    bunshi, bunbo = ans.numerator, ans.denominator
    ans = unknown(bunbo, bunshi)
    print(ans)
# Original solution
b,w=list(map(int,input().split()))
dp=[0]*(b+w)
dp[0]=1/2
mod=pow(10,9)+7

def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,b+w+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)
t1,t2=0,0
for i in range(1,1+b+w):
  t=pow(2,mod-2,mod)
  if i-b>0:
    t1*=2
    t1+=cmb(i-2,b-1,mod)
    tmp=t1*pow(2,mod-1-i,mod)
    tmp%=mod
    t-=tmp
    t%=mod
  if i-w>0:
    t2*=2
    t2+=cmb(i-2,w-1,mod)
    tmp=t2*pow(2,mod-1-i,mod)
    tmp%=mod
    t+=tmp
    t%=mod
  print(t)



# Optimized solution
b,w=list(map(int,input().split()))
dp=[0]*(b+w)
dp[0]=1/2
mod=pow(10,9)+7

def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,b+w+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)
t1,t2=0,0
for i in range(1,1+b+w):
  t=pow(2,mod-2,mod)
  if i-b>0:
    t1*=2
    t1%=mod
    t1+=cmb(i-2,b-1,mod)
    t1%=mod
    tmp=t1*pow(2,mod-1-i,mod)
    tmp%=mod
    t-=tmp
    t%=mod
  if i-w>0:
    t2*=2
    t2%=mod
    t2+=cmb(i-2,w-1,mod)
    t2%=mod
    tmp=t2*pow(2,mod-1-i,mod)
    tmp%=mod
    t+=tmp
    t%=mod
  print(t)
# Original solution
U = 2*10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
two = [1]*(U+1)
two_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
    two[i] = (two[i-1]*2)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
two_inv[U] = pow(two[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
    two_inv[i-1] = (two_inv[i]*2)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
B, W = list(map(int, input().split()))
p = 0
q = 0
for i in range(1, B+W+1):
  ans = 1 - p + q
  ans %= MOD
  ans *= two_inv[1]
  ans %= MOD
  print(ans)
  p += comb(i-1, B-1) * two_inv[i] % MOD
  p %= MOD
  q += comb(i-1, W-1) * two_inv[i] % MOD
  q %= MOD

# Optimized solution
def main():

  U = 2*10**5
  MOD = 10**9+7

  fact = [1]*(U+1)
  fact_inv = [1]*(U+1)
  two = [1]*(U+1)
  two_inv = [1]*(U+1)

  for i in range(1,U+1):
      fact[i] = (fact[i-1]*i)%MOD
      two[i] = (two[i-1]*2)%MOD
  fact_inv[U] = pow(fact[U], MOD-2, MOD)
  two_inv[U] = pow(two[U], MOD-2, MOD)

  for i in range(U,0,-1):
      fact_inv[i-1] = (fact_inv[i]*i)%MOD
      two_inv[i-1] = (two_inv[i]*2)%MOD

  def comb(n, k):
      if k < 0 or k > n:
          return 0
      z = fact[n]
      z *= fact_inv[k]
      z %= MOD
      z *= fact_inv[n-k]
      z %= MOD
      return z

  B, W = list(map(int, input().split()))
  p = 0
  q = 0
  for i in range(1, B+W+1):
    ans = 1 - p + q
    ans %= MOD
    ans *= two_inv[1]
    ans %= MOD
    print(ans)
    p += comb(i-1, B-1) * two_inv[i] % MOD
    p %= MOD
    q += comb(i-1, W-1) * two_inv[i] % MOD
    q %= MOD
    
if __name__ == "__main__":
  main()
# Original solution
B, W = list(map(int, input().split()))

MOD = 10**9+7
facts = [1,1]
invs = [1,1]
invfacts = [1,1]
for ind in range(1, B+W):
    i = ind+1
    facts += [ facts[-1]*i % MOD ]
    invs += [ -(MOD//i)*invs[MOD%i] % MOD ]
    invfacts += [ invfacts[-1]*invs[i] % MOD ]

y_pi = 0 #i回目までにBを食べ尽くした確率piの分子
y_qi = 0 #i回目までにWを食べ尽くした確率qiの分子
pow2 = 1
inv2i = 1
for i in range(B+W):
    y_pi = 0 if i < B else 2*y_pi + ((facts[i-1]*invfacts[i-B] % MOD)*invfacts[B-1] % MOD)
    y_qi = 0 if i < W else 2*y_qi + ((facts[i-1]*invfacts[i-W] % MOD)*invfacts[W-1] % MOD)
    invxi = inv2i * invs[2] % MOD
    yi = (pow2-y_pi+y_qi) % MOD
    z = yi*invxi % MOD
    print(z)
    pow2 = pow2*2 %MOD
    inv2i = invxi

# Optimized solution
B, W = list(map(int, input().split()))

MOD = 10**9+7

facts = [1,1] #階乗
invs = [1,1] #整数の逆元
invfacts = [1,1] #階乗の逆元
for ind in range(1, B+W):
    i = ind+1
    facts.append(facts[-1]*i % MOD)
    invs.append( -(MOD//i)*invs[MOD%i] % MOD )
    invfacts.append( invfacts[-1]*invs[i] % MOD )

def Comb(n, r, MOD=MOD):
    if n < r:
        return 0
    return facts[n]*invfacts[n-r]*invfacts[r] % MOD

y_pi = 0 #i回目までにBを食べ尽くした確率piの分子
y_qi = 0 #i回目までにWを食べ尽くした確率qiの分子
pow2 = 1
invxi = 1
inv2 = invs[2]
for i in range(B+W):
    #y_pi = 0 if i < B else 2*y_pi + ((facts[i-1]*invfacts[i-B] % MOD)*invfacts[B-1] % MOD)
    y_pi = (2*y_pi + Comb(i-1, B-1))%MOD
    #y_qi = 0 if i < W else 2*y_qi + ((facts[i-1]*invfacts[i-W] % MOD)*invfacts[W-1] % MOD)
    y_qi = (2*y_qi + Comb(i-1, W-1))%MOD
    invxi = invxi * inv2 % MOD
    yi = (pow2-y_pi+y_qi) % MOD
    z = yi*invxi % MOD
    print(z)
    pow2 = pow2*2 %MOD
# Original solution
from collections import Counter
from itertools import product

N, W = list(map(int, input().split()))
items = {}
weight = []

for i in range(N):
    w, v = list(map(int, input().split()))
    weight.append(w)
    
    if items.get(w, None) is None:
        items[w] = []
    items[w].append(v)
    items[w] = sorted(items[w], reverse = True)

cnt = Counter(weight)

w_num = [] #各重さの個数。組み合わせのために使う。[range(0,2), range(0,3), range(0,2)]のような出力
w_set = [] # 重さは w0 <= wi <= w0+3の４通りしかない

for w in range(weight[0], weight[0] + 4):
    if cnt[w] == 0:
        continue
    
    w_num.append(list(range(cnt[w] + 1)))
    w_set.append(w)

ans = 0

for i in product(*w_num):
    w = sum([x[0] * x[1] for x in zip(i, w_set)])
    if 1 > w or w > W:
        continue
    v = sum([sum(items[k][:j]) for j, k in zip(i, w_set)])
    if ans < v:
        ans = v

print(ans)

# Optimized solution
N, W = list(map(int, input().split()))
w, v = [], []
for _ in range(N):
    a, b = list(map(int, input().split()))
    w.append(a)
    v.append(b)
    
memo = {}

def nap(i, j):
    if i == N:
        return 0
    
    if (i, j) in memo:
        return memo[i, j]
    elif j < w[i]:
        temp = nap(i+1, j)
    else:
        temp = max(nap(i+1, j), nap(i+1, j-w[i]) + v[i])
    
    memo[i,j] = temp
    
    return memo[i,j]

print((nap(0, W)))
# Original solution
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
for i in range(N):
    w[i],v[i] = list(map(int,input().split()))

dp = [[0 for i in range(W+1)] for j in range(N)]


for i in range(N):
    if N < w[i]:
        pass
    else:
        dp[i][w[i]] = v[i]
    for j in range(W+1):
        if i-1 >= 0:
            dp[i][j] = max(dp[i][j],dp[i-1][j])
        if j-w[i] >= 0:
            dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i])

print((max(dp[-1])))


# Optimized solution
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
for i in range(N):
    w[i],v[i] = list(map(int,input().split()))

w_sum = [0 for i in range(N+1)]
v_sum = [0 for i in range(N+1)]

w.insert(0,0)
v.insert(0,0)

for i in range(N):
    w_sum[i+1] = w_sum[i]+w[i+1]
    v_sum[i+1] = v_sum[i]+v[i+1]


nap_memo = {}

def nap(i,W2):#i:count_pieces,W2:rest_weight
    key = str(i)+":"+str(W2)
    if key in nap_memo:
        return nap_memo[key]
    elif i == 0:#品物０個の時は価値０
        r = 0
    elif W2 < w[0]:
        r = 0
    elif W2 < w[i]:#i番目の荷物が残量を超えるなら入らない
        r = nap(i-1,W2)
    elif w_sum[i] <= W2:
        r = v_sum[i]
    else:
        r = max(nap(i-1,W2-w[i])+v[i], nap(i-1,W2))

    nap_memo[key] = r
    return r


print((nap(N,W)))
#
# dp = [[[0 for i in range(W+1)] for j in range(N)]
#
#
# for i in range(N):
#     if N < w[i]:
#         pass
#     else:
#         dp[i][w[i]] = v[i]
#     for j in range(W+1):
#         if i-1 >= 0:
#             dp[i][j] = max(dp[i][j],dp[i-1][j])
#         if j-w[i] >= 0:
#             dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i])
#
# print(max(dp[-1]))
# Original solution
import sys

input = sys.stdin.readline


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


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N, W = read_values()
    dp = [
        [[0 for _ in range(N * 3 + 10)] for __ in range(N + 10)]
        for ___ in range(N + 10)
    ]
    I = [tuple(read_values()) for _ in range(N)]

    w0 = I[0][0]
    if w0 > W:
        print((0))
        return

    for i, (w1, v) in enumerate(I):
        w = w1 - w0
        for k in range(N):
            for j in range(N * 3 + 5):
                dp[i + 1][k][j] = max(dp[i][k][j], dp[i + 1][k][j])
                dp[i + 1][k + 1][j + w] = max(dp[i][k][j] + v, dp[i + 1][k + 1][j + w])

    res = 0
    for k in range(N + 1):
        r = min(W - k * w0, 3 * N + 5)
        if r < 0:
            continue
        for i in range(r + 1):
            res = max(res, dp[N][k][i])
    print(res)


if __name__ == "__main__":
    main()



# Optimized solution
import sys

input = sys.stdin.readline


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


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    import bisect

    N, W = read_values()
    I = [tuple(read_values()) for _ in range(N)]

    init_w = I[0][0]
    D = {i: [] for i in range(4)}
    S = {i: [0] for i in range(4)}
    for w, v in I:
        bisect.insort(D[w - init_w], -v)

    for i, d in list(D.items()):
        for v in d:
            S[i].append(v + S[i][-1])

    res = 0
    for t0 in range(len(D[0]) + 1):
        for t1 in range(len(D[1]) + 1):
            for t2 in range(len(D[2]) + 1):
                for t3 in range(len(D[3]) + 1):
                    if (t0 + t1 + t2 + t3) * init_w + t1 + 2 * t2 + 3 * t3 > W:
                        continue

                    res = min(res, S[0][t0] + S[1][t1] + S[2][t2] + S[3][t3])
    print((-res))


if __name__ == "__main__":
    main()
# Original solution
N, W = list(map(int, input().split()))
w, v = [], []
for _ in range(N):
    x, y = list(map(int, input().split()))
    w.append(x)
    v.append(y)
from collections import defaultdict
dp = defaultdict(lambda: 0)
dp[0,0] = 0

for i in range(N):
    for weight in range(W+1):
        if weight >= w[i]:
            dp[i+1,weight] = max(dp[i,weight], dp[i,weight-w[i]]+v[i])
        else:
            dp[i+1,weight] = dp[i,weight]
print((dp[N,W]))


# Optimized solution
N, W = list(map(int, input().split()))
Items = [tuple(map(int, input().split())) for _ in range(N)]
from collections import defaultdict as dd
Bag = dd(lambda:0)
Bag[0] = 0
for w,v in Items:
    temp = [(key+w,Bag[key]+v) for key in Bag if key + w <= W]
    for key,value in temp:
        Bag[key] = max(Bag[key],value)
ans = max(Bag.values())
print(ans)
# Original solution
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for i in range(N)]
v = [[] for i in range(4)]
standard = wv[0][0]

for wi, vi in wv:
    plus = wi - standard
    v[plus].append(vi)

for i in range(4):
    v[i].sort(reverse=True)
    for j in range(len(v[i])-1):
        v[i][j+1] = v[i][j] + v[i][j+1]
    v[i].insert(0, 0)

ans = 0
for a in range(len(v[0])):
    for b in range(len(v[1])):
        for c in range(len(v[2])):
            for d in range(len(v[3])):
                if standard*a + (standard+1)*b + (standard+2)*c + (standard+3)*d > W:
                    continue
                else:
                    ans = max(ans, v[0][a]+v[1][b]+v[2][c]+v[3][d])
print(ans)


# Optimized solution
from itertools import accumulate
N, W = list(map(int, input().split()))
w0, w1, w2, w3 = [], [], [], []
base_w = -1
for i in range(N):
    w, v = list(map(int, input().split()))
    if base_w < 0:
        base_w = w

    # 重みごとの箱にいれる
    w -= base_w
    if w == 0:
        w0.append(v)
    elif w == 1:
        w1.append(v)
    elif w == 2:
        w2.append(v)
    else:
        w3.append(v)

# 降順ソート
w0.sort(reverse=True)
w1.sort(reverse=True)
w2.sort(reverse=True)
w3.sort(reverse=True)

# 累積和
w0 = [0] + list(accumulate(w0))
w1 = [0] + list(accumulate(w1))
w2 = [0] + list(accumulate(w2))
w3 = [0] + list(accumulate(w3))

ans = 0
for i0 in range(len(w0)):
    for i1 in range(len(w1)):
        for i2 in range(len(w2)):
            for i3 in range(len(w3)):
                if base_w * i0 + (base_w + 1) * i1 + (base_w + 2) * i2 + (base_w + 3) * i3 > W:
                    continue
                ans = max(ans, w0[i0] + w1[i1] + w2[i2] + w3[i3])

print(ans)
# Original solution
# ABC060D - Simple Knapsack (ARC073D)
# exhaustive search
from itertools import accumulate


def main():
    N, W, *A = list(map(int, open(0).read().split()))
    V, x = [[] for _ in range(4)], A[0]  # x: w1 (W1 ≤ wi ≤ w1 + 3)
    for i in range(0, 2 * N, 2):  # group by weight
        w, v = A[i : i + 2]
        V[w - x] += [v]
    for i in range(4):  # V[i][j] := max value of picking up j items from group i
        V[i] = tuple(accumulate([0] + sorted(V[i], reverse=1)))
    L = [len(v) for v in V]
    ans = 0
    for i in range(L[0]):
        for j in range(L[1]):
            for k in range(L[2]):
                w = i * x + j * (x + 1) + k * (x + 2)
                if w > W:
                    break
                l = min(L[3] - 1, (W - w) // (x + 3))
                v = V[0][i] + V[1][j] + V[2][k] + V[3][l]
                ans = max(ans, v)
    print(ans)


if __name__ == "__main__":
    main()

# Optimized solution
# ABC060D - Simple Knapsack (ARC073D)
from itertools import accumulate as acc


def main():
    N, W, *A = list(map(int, open(0).read().split()))
    V, x = [[] for _ in range(4)], A[0]  # x: w1 (W1 ≤ wi ≤ w1 + 3)
    for w, v in zip(*[iter(A)] * 2):  # group by weight
        V[w - x].append(v)
    for i in range(4):  # V[i][j] := max value of picking up j items from group i
        V[i] = tuple(acc([0] + sorted(V[i], reverse=1)))
    L = [len(v) for v in V]
    ans = 0
    for i in range(L[0]):
        for j in range(L[1]):
            for k in range(L[2]):
                w = i * x + j * (x + 1) + k * (x + 2)
                if w > W:
                    break
                l = min(L[3] - 1, (W - w) // (x + 3))
                v = V[0][i] + V[1][j] + V[2][k] + V[3][l]
                ans = max(ans, v)
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
def resolve():
    N, W = list(map(int, input().split()))
    WV = [[0, 0]]+[list(map(int, input().split())) for _ in range(N)]
    dp = [[0 for _ in range(W+1)] for ___ in range(N+1)]
    
    for i in range(1, N+1):
        for j in range(W+1):
            w, v = WV[i]
            if j >= w:
                dp[i][j] = max(dp[i-1][j-w] + v, dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
    print((dp[N][W]))


if __name__ == '__main__':
    resolve()

# Optimized solution
def resolve():
    N, W = list(map(int, input().split()))
    WV = [list(map(int, input().split())) for _ in range(N)]
    wbase = WV[0][0]
    d = {
        wbase: [0],
        wbase+1: [0],
        wbase+2: [0],
        wbase+3: [0],
    }
    for w, v in WV:
        d[w].append(v)
    for v in list(d.values()):
        v.sort(reverse=True)
    
    accs = {}
    for i in range(4):
        accs[wbase+i] = [0]
        for j in range(len(d[wbase+i])):
            accs[wbase+i].append(accs[wbase+i][j]+d[wbase+i][j])
    
    res = 0
    for i in range(len(d[wbase])):
        for j in range(len(d[wbase+1])):
            for k in range(len(d[wbase+2])):
                for l in range(len(d[wbase+3])):
                    if i*wbase+j*(wbase+1)+k*(wbase+2)+l*(wbase+3) <= W:
                        res = max(res, accs[wbase][i]+accs[wbase+1][j]+accs[wbase+2][k]+accs[wbase+3][l])
    print(res)


if __name__ == '__main__':
    resolve()