CodeEff/ECCO huggingface dataset:
# Original solution
N, K = list(map(int, input().split()))
ans = 0
for b in range(1, N + 1):
    p, r = divmod(N, b)
    ans += p * max(0, b - K) + max(0, r - K + 1)
if K == 0:
    ans -= N
print(ans)

# Optimized solution
N, K = list(map(int, input().split()))
if K == 0:
    print((N * N))
    exit()
cnt = 0
for b in range(K + 1, N + 1):
    p, r = divmod(N, b)
    cnt += p * (b - K)
    if r >= K:
        cnt += r - K + 1
print(cnt)
# Original solution
import itertools
N, K = list(map(int, input().split()))
count = 0
for i in range(K, N+1):
    count += N - i
for i in range(K+1, N+1):
    for j in range(1, i):
        if i % j >= K:
            count += 1
print(count)

# Optimized solution
N, K = list(map(int, input().split()))
count = 0
if K == 0:
    print((N*N))
    exit()
for i in range(1, N+1):
    count += int(N/i) * max(i-K, 0) + max(N - int(N/i)*i + 1 - K, 0)
print(count)
# Original solution
n, k = [int(i) for i in input().split()]
ans = 0
for a in range(k,n+1):
    ans += n - a
    for b in range(1,a):
        if a % b >= k:
            ans += 1

print(ans)

# Optimized solution
def max(a,b):
    if a > b:
        return a
    else:
        return b
n, k = [int(i) for i in input().split()]
ans = 0


for b in range(1,n+1):
    p = n // b
    r = n % b
    ans += p * max(0,b-k)+max(0,r-k+1)
if k == 0:
    ans -= n
    
print(ans)
# Original solution
import sys
def input():
    return sys.stdin.readline()[:-1]
n,k=list(map(int,input().split()))
tmp=0
ans=0
if k==0:
    print((n*n))
    quit()
for i in range(k,n):
    tmp=n//(i+1)
    ans+=(i+1-k)*tmp
    if n%(i+1)-k+1>0:
        ans+=n%(i+1)-k+1
print(ans)

# Optimized solution
import sys
def input():
    return sys.stdin.readline()[:-1]
n,k=list(map(int,input().split()))
tmp=0
ans=0
# if k==0:
#     print(n*n)
#     quit()
for i in range(k,n):
    tmp=n//(i+1)
    ans+=(i+1-k)*tmp
    tmp=max(1,k)
    if n%(i+1)-tmp+1>0:
        ans+=n%(i+1)-tmp+1
print(ans)
# Original solution
def  main():
    N,K = list(map(int,input().split()))
    ans = 0
    for k in range(K,N):
        for b in range(k+1,N+1):
            cnt = (N-k)//b
            if k!=0:
                cnt += 1
            ans += cnt
    print(ans)    


if __name__ == '__main__':
    main()

# Optimized solution
n,k = list(map(int,input().split()))
count = 0
if k==0:
    print((n ** 2))
    exit()

for i in range(1,n+1):
    if i <= k:
        continue
    count += max(0, (n%i) - k + 1)
    count += (n // i) * (i - k)
print(count)
# Original solution
n,k = list(map(int,input().split()))
cnt = 0
for b in range(1,n+1):
    p = n//b
    r = n%b
    cnt += max(0, b-k)*p + max(0, r-k+1)
else:
    if k==0:
        cnt -= n
print(cnt)

# Optimized solution
n,k = list(map(int,input().split()))
if k==0:
    print((n**2))
else:
    ans = 0
    for b in range(k,n+1):
        ans += (n//b)*(b-k)
        if n%b>=k:
            ans += n%b-(k-1)
    print(ans)
# Original solution
N,K = list(map(int,input().split()))

if K == 0:
  print((N**2))
  exit()

ans = 0
for b in range(1,N+1):
  if b <= K: continue
  else: ans += N//b*(b-K) + max(0,(N-(N//b)*b)-K+1)

print(ans)

# Optimized solution
N, K = list(map(int, input().split()))

if K == 0:
    print((N ** 2))
    exit()

ans = 0
for b in range(K + 1, N + 1):
    val1 = N // b * (b - K)
    if N % b == 0:
        val2 = 0
    else:
        val2 = max(0, N - (N // b) * b - K + 1)
    ans += val1 + val2
print(ans)
# Original solution
def f(n, k):
    return 0.5*(n-k)*(n-k+1)

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

cnt = 0
for a in range(K, N+1):
    for b in range(K, a+1):
        if a <= 1 or b <= 1:
            continue
        if ((a%b) >= K):
            cnt += 1

cnt += f(N, K)
print((int(cnt)))


# Optimized solution
N, K = list(map(int, input().split()))

cnt = 0
for b in range(1, N+1):
    p = N // b
    q = N % b
    cnt += max(b-K,0)*p + max(q+1-K,0)
if K == 0:
    cnt -= N
print((int(cnt)))
# Original solution
N,K=list(map(int,input().split()))

t=0
for b in range(K+1,N+1):
  t+=(N//b)*(b-K)+((N%b-K+(1 if K>0 else 0) if N%b>=K else 0)if N%b else 0)
print(t)


# Optimized solution
N,K=list(map(int,input().split()))

t=0
for b in range(K+1,N+1):
  t+=(-~N//b)*(b-K)+max(-~N%b-K,0)
print((t-(0 if K else N-K)))
# Original solution
def ans(N, M):
    if M == 0: return(N * N)
    ans = 0
    for i in range(1,N+1):
        p, q = divmod(N,i)
        ans += p * max(i-M,0) + max((q-M)+1,0)
    return(ans)

N, M = list(map(int, input().split()))
print((ans(N, M)))

# Optimized solution
def ans(N, M):
    if M == 0: return(N * N)
    cnt = 0
    for i in range(1,N+1):
        p, q = divmod(N,i)
        cnt += p * max(i-M,0) + max((q-M)+1,0)
    return(cnt)

N, M = list(map(int, input().split()))
print((ans(N, M)))
# Original solution
n,k = list(map(int,input().split()))
ans = 0
if k==0:
    ans = n**2
else:
    for i in range(1,n+1):
        loop = n//i
        rem = n%i
        ans += loop*max(i-k,0) + max(rem-k+1,0)
print(ans)

# Optimized solution
n,k = list(map(int,input().split()))
ans = 0
for i in range(1,n+1):
    loop = n//i
    rem = n%i
    ans += max(0,i-k) * loop + max(rem+1-k,0)
if k==0:
    ans -= n
print(ans)
# Original solution
n,k=list(map(int, input().split()))

if k==0:
    print((n**2))
    quit()

cnt=0
for a in range(k,n+1):
    b=list(range(k,n+1))
    cnt+=len(list([x for x in b if a%x>=k]))

print(cnt)


# Optimized solution
n, k = list(map(int, input().split()))

s = 0
for b in range(1, n+1):
    s += max(0, b-k)*(n//b) + max(0, n%b-k+1)

if k == 0:
    s = n*n
print(s)
# Original solution
def rep(b,r,N):
    return (N-r)//b+1 if r>0 else N//b

N,K=list(map(int,input().split(' ')))
count = 0
for b in range(K+1,N+1):
    for r in range(K,b):
        count += rep(b,r,N)
print(count)

# Optimized solution

N,K=list(map(int,input().split(' ')))
count = 0
for b in range(K+1,N+1):
    l, h, n = K, b-1, b-K
    while l <= N:
        if h <= N:
            count += n
            if l==0:
                count -=1
        else:
            count += N-l+1
            if l==0:
                count -=1
            break
        l+=b
        h+=b
print(count)
# Original solution
n,k=list(map(int,input().split()))
if k==0:
    print((n**2));exit()
ans=0
for i in range(k+1,n+1):
    p=n//i
    q=n%i
    ans +=p*max(0,i-k)+max(0,q-k+1)
print(ans)

# Optimized solution
n,k=list(map(int,input().split()))
if k==0:print((n**2));exit()
ans=0
for i in range(k+1,n+1):
    ans +=n//i*max(0,i-k)+max(0,n%i-k+1)
print(ans)
# Original solution
N,K=list(map(int,input().split()))

if K==0:
  print((N*N))
else:
  ans=0
  for i in range(K,N+1):
    ans+=(N//i*max(0,i-K)+max((N%i)+1-K,0))
  print(ans)


# Optimized solution
N,K=list(map(int,input().split()))

if K==0:
  print((N*N))
else:
    ans=0
    for i in range(K+1,N+1):
        ans+=N//i*max(0,i-K)+max(0,N%i-K+1)
    print(ans)
# Original solution
n, k = list(map(int, input().split()))

ans = 0
if k == 0:
    ans = n ** 2
else:
    for b in range(k + 1, n + 1):
        for a in range(k, b):
            ans += ((n - a) // b) + 1

print(ans)


# Optimized solution
n, k = list(map(int, input().split()))

ans = 0
if k == 0:
    ans = n ** 2
else:
    for b in range(k + 1, n + 1):
        ans += (b - k) * (n // b)
        last_count = n % b - k + 1
        ans += last_count if last_count > 0 else 0

print(ans)
# Original solution
#coding=utf-8

def solve(A, B):
    count = 0
    for b in range(B + 1, A + 1):
        for a in range(1, A + 1):
            if a % b >= B:
                count += 1
    return count

def main():
    A, B = input().split(' ')
    print((solve(int(A), int(B))))


if __name__ == '__main__':
    main()



# Optimized solution
#coding=utf-8

def solve(N, K):
    count = 0
    if K == 0:
        return N * N
    for b in range(K + 1, N + 1):
        p = N // b
        r = N % b
        count += p * (b - K)
        if r >= K:
            count += r - K + 1
    return count

def main():
    A, B = input().split(' ')
    print((solve(int(A), int(B))))


if __name__ == '__main__':
    main()
# Original solution
n, k = list(map(int, input().split()))
count = 0

if k == 0:
    count += n * n

else:
    for b in range(k + 1, n + 1):
        q, r = n // b, n % b
        count += q * (b - k) + max((r + 1 - k), 0)
        
print(count)

# Optimized solution
n, k = list(map(int, input().split()))
ans = 0

if k == 0:
    ans = n ** 2
else:
    for b in range(k + 1, n + 1):
        q, r = n // b, n % b
        ans += (b - k) * q + max(r + 1 - k, 0)
    
print(ans)
# Original solution
import sys

s = sys.stdin.readline().strip()

n = len(s)

if s[0] == s[n-1]:
    move = 1
else:
    move = 0

move = (n - move) % 2

if move == 1:
    print('First')
else:
    print('Second')


# Optimized solution
import sys

s = str(sys.stdin.readline().strip())

n = len(s)

if s[0] == s[n-1]:
    move = 1
else:
    move = 0

move = (n - move) % 2

if move == 1:
    print('First')
else:
    print('Second')
# Original solution
N, W = list(map(int, input().split()))
w = [0]*N
v = [0]*N
for i in range(N):
    w[i], v[i] = list(map(int, input().split()))


dp = [[0]*(W+1) for _ in range(N+1)]
#dp[ i ][ sum_w ] : 
#i-1 番目までの品物から重さが sum_w 以下となるように選んだときの、
#価値の総和の最大値
for i in range(N):
    for j in range(W+1):
        if j - w[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]] + v[i])
        
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])

print((dp[N][W]))


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


dp = [[0]*(W+1) for _ in range(N+1)]
#dp[ i ][ sum_w ] : 
#i-1 番目までの品物から重さが sum_w 以下となるように選んだときの、
#価値の総和の最大値
for i in range(N):
    for j in range(W+1):
        if j - w[i] >= 0:
            #dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]] + v[i])
            dp[i+1][j] = dp[i][j - w[i]] + v[i]

        dp[i+1][j] = max(dp[i][j], dp[i+1][j])

print((dp[N][W]))
# Original solution
import sys
input = sys.stdin.readline

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

dp = [0] * (w + 1)

for _ in range(n):
    wi, vi = list(map(int, input().split()))

    for wj in range(w, wi - 1, -1):
        nv = dp[wj - wi] + vi
        if dp[wj] < nv:
            dp[wj] = nv

print((max(dp)))


# Optimized solution
import sys
input = sys.stdin.readline

def main():
    n, w = list(map(int, input().split()))

    dp = [0] * (w + 1)

    for _ in range(n):
        wi, vi = list(map(int, input().split()))

        for wj in range(w, wi - 1, -1):
            nv = dp[wj - wi] + vi
            if dp[wj] < nv:
                dp[wj] = nv

    print((max(dp)))

main()
# Original solution
n, w = list(map(int, input().split()))
wt, v = [], []
for i in range(n):
    a, b = list(map(int, input().split()))
    wt.append(a)
    v.append(b)
dp = [[0 for i in range(w + 1)] for j in range(n + 1)]
for i in range(1, len(wt)+1):
    for j in range(w + 1):
        if j >= wt[i-1]:
            dp[i][j] = max(dp[i-1][j], v[i - 1] + dp[i - 1][j - wt[i - 1]])
        else:
            dp[i][j] = dp[i-1][j]
print((dp[-1][-1]))


# Optimized solution
n, w = list(map(int, input().split()))
wt, v = [], []
for i in range(n):
    a, b = list(map(int, input().split()))
    wt.append(a)
    v.append(b)
dp = [0 for i in range(w + 1)]
for i in range(len(wt)):
    for j in range(w, wt[i]-1, -1):
        dp[j] = max(dp[j], v[i] + dp[j - wt[i]])
print((dp[-1]))
# Original solution

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


#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合S

weight=[0]*110
value=[0]*110

S = [[0 for j in range(3)] for i in range(100010)]
DP= [[0 for j in range(100100)] for i in range(110)]

for i in range(N):
    A,B=list(map(int,input().split()))
    weight[i]=A
    value[i]=B
    
for i in range(N):
    for w in range(W+1):
        if w>=weight[i]:
            DP[i+1][w]=max(DP[i][w-weight[i]]+value[i],DP[i][w])
        else:
            DP[i+1][w]=DP[i][w]

print((DP[N][W]))

# Optimized solution
N,W=list(map(int,input().split()))
S = [[0 for j in range(2)] for i in range(N+1)]

DP= [[0 for j in range(100010)] for i in range(110)]
def chmax(a,b):
    if a>b:
        return a
    else:
        return b


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


for i in range(N):
    for j in range(W+1):
        if j-S[i][0]>=0:
            
            DP[i+1][j]=chmax(DP[i][j],DP[i][j-S[i][0]]+S[i][1])
        
        else:
            DP[i+1][j]=DP[i][j]
        
print((DP[N][W]))
# Original solution
n,W = list(map(int, input().split(' ')))
WV = (list(map(int, input().split(' '))) for _ in range(n))
dp = [0] * (W+1)
 
for w, v in WV:
  for j in range(W, w-1, -1):
    DP = dp[j-w] + v
    if dp[j] < DP:
      dp[j] = DP
print((max(dp)))


# Optimized solution
def DP():
    n,W = list(map(int, input().split(' ')))
    WV = (list(map(int, input().split(' '))) for _ in range(n))
    dp = [0] * (W+1)

    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print((DP()))
# Original solution
def DP():
  
  n,m=list(map(int,input().split()))
  dp=[0]*(m+2)

  for i in range(n):  #商品を一つずつ見ていく。
    w,v=(list(map(int,input().split())))
    for j in range(m+1,w,-1): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
      if (dp[j-w]+v)>dp[j]:
        dp[j]=dp[j-w]+v
      else:
        dp[j]=dp[j]
  return max(dp) 
print((DP()))




# Optimized solution
def DP():
  n,m=list(map(int,input().split()))
  dp=[0]*(m+2)
 
  for i in range(n):  #商品を一つずつ見ていく。
    w,v=(list(map(int,input().split())))
    for j in range(m+1,w,-1): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
      dp[j]=max(dp[j-w]+v,dp[j])
  return max(dp)
print((DP()))
# Original solution
N, W = list(map(int, input().split()))
Bs = []
for i in range(N):
    Bs.append(tuple(map(int, input().split())))

dp = [[0 for _ in range(W + 1)] for _ in range(N)]
for i in range(Bs[N - 1][0], W + 1):
    dp[N - 1][i] = Bs[N - 1][1]
for i in range(N - 2, -1, -1):
    for j in range(W + 1):
        dp[i][j] = max(dp[i + 1][j], (dp[i + 1][j - Bs[i][0]] + Bs[i][1]) if j >= Bs[i][0] else 0)

print((dp[0][W]))

# Optimized solution
N, W = list(map(int, input().split()))
Bs = []
for i in range(N):
    Bs.append(tuple(map(int, input().split())))

dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
for i in range(N - 1, -1, -1):
    for j in range(W + 1):
        dp[i][j] = max(dp[i + 1][j], (dp[i + 1][j - Bs[i][0]] + Bs[i][1]) if j >= Bs[i][0] else 0)

print((dp[0][W]))
# Original solution
N, W = list(map(int, input().split()))
Bs = []
for i in range(N):
    Bs.append(tuple(map(int, input().split())))

dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
for i in range(N - 1, -1, -1):
    for j in range(W + 1):
        dp[i][j] = max(dp[i + 1][j], (dp[i + 1][j - Bs[i][0]] + Bs[i][1]) if j >= Bs[i][0] else 0)

print((dp[0][W]))

# Optimized solution
N, W = list(map(int, input().split()))
Bs = [tuple(map(int, input().split())) for _ in range(N)]

dp = [0] * (W + 1)
for w, v in Bs:
    for i in range(W, w - 1, -1):
        dp[i] = max(dp[i], dp[i - w] + v)

print((dp[W]))
# Original solution
def main():
    goods, weight_limit = list(map(int, input().split()))
    good_info = [tuple(map(int, input().split())) for _ in range(goods)]
    dp = [[0 for _ in range(weight_limit + 1)] for _ in range(goods + 1)]
    for i in range(goods):
        for j in range(weight_limit + 1):
            if j >= good_info[i][0]:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - good_info[i][0]] + good_info[i][1])
            else:
                dp[i + 1][j] = dp[i][j]
    print((dp[goods][weight_limit]))


if __name__ == '__main__':
    main()



# Optimized solution
def main():
    goods, weight_limit = list(map(int, input().split()))
    weight = []
    value = []
    for _ in range(goods):
        w, v = list(map(int, input().split()))
        weight.append(w)
        value.append(v)
    dp = [[0 for _ in range(weight_limit + 1)] for _ in range(goods + 1)]
    for i in range(goods):
        for j in range(weight_limit + 1):
            if j >= weight[i]:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])
            else:
                dp[i + 1][j] = dp[i][j]
    print((dp[-1][-1]))


if __name__ == '__main__':
    main()
# Original solution
from pprint import pprint
import sys

N, W = list(map(int, sys.stdin.readline().strip().split(" ")))

w = []
for _ in range(N):
    w_i, v_i = list(map(int, sys.stdin.readline().strip().split(" ")))
    w.append((w_i, v_i))

dp = []
for _ in range(N+1):
    dp.append([0] * (W+1))


for i in range(N):
    for j in range(W+1):
        if j - w[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j - w[i][0]] + w[i][1], dp[i+1][j])
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
# pprint(dp)
print((dp[N][W])) 

# Optimized solution
from pprint import pprint
import sys

N, W = list(map(int, sys.stdin.readline().strip().split(" ")))

w = []
for _ in range(N):
    w_i, v_i = list(map(int, sys.stdin.readline().strip().split(" ")))
    w.append((w_i, v_i))

dp = []
for _ in range(N+1):
    dp.append([0] * (W+1))


for i in range(N):
    for j in range(W+1):
        if j - w[i][0] >= 0:
            # dp[i+1][j] = max(dp[i][j - w[i][0]] + w[i][1], dp[i+1][j])
            dp[i+1][j] = dp[i][j - w[i][0]] + w[i][1]
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
# pprint(dp)
print((dp[N][W]))
# Original solution
# https://atcoder.jp/contests/dp/submissions/13960132

def MAX(a, b):
    d = a + ms - b
    return b + ((((d & ms) >> (K - 1)) * tt) & d)

def tolist(n):
    sx = bin(n)[2:] + "_"
    return [int(sx[-(i+1) * K - 1:-i * K - 1], 2) for i in range((len(sx)+K-2) // K)]

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

ms = int(("1" + "0" * (K - 1)) * (W + 1), 2)
tt = (1 << K - 1) - 1
one = int(("0" * (K - 1) + "1") * (W + 1), 2)

s = 1 << K - 2 + (W * K)
for _ in range(N):
    w, v = list(map(int, input().split()))
    s = MAX(s, (s >> w * K) + one * v)

print((max(tolist(s)) - (1 << K - 2)))

# Optimized solution
# https://atcoder.jp/contests/dp/submissions/13960132

def MAX(a, b):
    d = a + ms - b
    return b + ((ms - ((d & ms) >> (K - 1))) & mask & d)

def tolist(n):
    sx = bin(n)[2:] + "_"
    return [int(sx[-(i+1) * K - 1:-i * K - 1], 2) for i in range((len(sx)+K-2) // K)]

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

ms = int(("1" + "0" * (K - 1)) * (W + 1), 2)
mask = int(("0" + "1" * (K - 1)) * (W + 1), 2)
tt = (1 << K - 1) - 1
one = int(("0" * (K - 1) + "1") * (W + 1), 2)

s = 1 << K - 2 + (W * K)
for _ in range(N):
    w, v = list(map(int, input().split()))
    s = MAX(s, (s >> w * K) + one * v)

print((max(tolist(s)) - (1 << K - 2)))
# Original solution
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  w, v = wv[i]
  for j in range(W+1):
    if j<w:
      dp[i][j] = dp[i-1][j]
      continue
    dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
print((max(dp[N-1])))

# Optimized solution
N, W = list(map(int, input().split()))
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  w, v = list(map(int, input().split()))
  for j in range(W+1):
    if j<w:
      dp[i][j] = dp[i-1][j]
      continue
    dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
print((max(dp[N-1])))
# Original solution
n,w_lim = list(map(int,input().split()))
dp = [[0 for i in range(w_lim+1)] for i in range(n+1)]

w,v = [],[]
for i in range(n):
    ww,vv = list(map(int,input().split()))
    w.append(ww)
    v.append(vv)

#初期条件
for ww in range(w_lim+1): dp[0][ww] = v[0] if ww>=w[0] else 0

#漸化式
for i in range(n-1):
    for ww in range(w_lim+1):
        dp[i+1][ww] = dp[i][ww] if w[i+1]>ww else max(dp[i][ww], dp[i][ww-w[i+1]]+v[i+1])

ans = dp[n-1][w_lim]
print(ans)


# Optimized solution
n,w_lim = list(map(int,input().split()))
dp = [[0 for i in range(w_lim+1)] for i in range(n)]

w,v = [],[]
for i in range(n):
    ww,vv = list(map(int,input().split()))
    w.append(ww)
    v.append(vv)

#初期条件
for ww in range(w_lim+1): dp[0][ww] = v[0] if ww>=w[0] else 0

#漸化式
for i in range(n-1):
    for ww in range(w_lim+1):
        dp[i+1][ww] = dp[i][ww] if w[i+1]>ww else max(dp[i][ww], dp[i][ww-w[i+1]]+v[i+1])

ans = dp[n-1][w_lim]
print(ans)
# Original solution
n,w=list(map(int,input().split()))
weight,value=[0]*110,[0]*110
dp = [[0 for _ in range(100100)] for _ in range(110)]
for i in range(n):
    weight[i],value[i] = list(map(int,input().split()))
for i in range(n):
    for  sum_w in range(w+1):
        #i番目の品物を選ぶ
        if(sum_w - weight[i] >=0):
            dp[i+1][sum_w] =max(dp[i+1][sum_w], dp[i][sum_w - weight[i]]+ value[i])
        #選ばない場合
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print((dp[n][w]))

# Optimized solution
N,W=list(map(int,input().split()))
w,v=[],[]
for i in range(N):
    weight, value = list(map(int,input().split()))
    w.append(weight)
    v.append(value)
dp = [[0 for _ in range(100100)] for _ in range(N+2)]
for i in range(N):
    for sum_w in range(W+1):
        if sum_w -w[i] >=0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w],dp[i][sum_w-w[i]] + v[i])
        dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w])
print((dp[N][W]))
# Original solution
from sys import stdin, stdout
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: list(map(int, stdin.readline().split()))

INF, NINF = float('inf'), float('-inf')

def main():
	n, W = rli()
	weight = [0 for _ in range(n)]
	val = [0 for _ in range(n)]
	for i in range(n):
		w, v = rli()
		weight[i], val[i] = w, v
	#dp(i, j) = max val using items 1,...,i at 
	#			weight j

	dp = [[NINF for c in range(W+1)] for r in range(n+1)]
	for r in range(n+1):
		dp[r][0] = 0
	for c in range(W+1):
		dp[0][c] = 0
	for r in range(1, n+1):
		w, v = weight[r-1], val[r-1]
		for c in range(1, W+1):
			if c - w < 0:
				dp[r][c] = max(dp[r][c], dp[r-1][c])
			else:
				dp[r][c] = max(dp[r][c], dp[r-1][c], v + dp[r-1][c-w])
	print((dp[-1][-1]))
	stdout.close()

if __name__ == "__main__":
	main()

# Optimized solution
from sys import stdin, stdout
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: list(map(int, stdin.readline().split()))

INF, NINF = float('inf'), float('-inf')

def main():
	n, W = rli()
	weight = [0 for _ in range(n)]
	val = [0 for _ in range(n)]
	for i in range(n):
		w, v = rli()
		weight[i], val[i] = w, v
	#dp(i, j) = max val using items 1,...,i at 
	#			weight j

	dp = [[NINF for c in range(W+1)] for r in range(n+1)]
	for r in range(n+1):
		dp[r][0] = 0
	for c in range(W+1):
		dp[0][c] = 0
	for r in range(1, n+1):
		w, v = weight[r-1], val[r-1]
		for c in range(1, W+1):
			dp[r][c] = dp[r-1][c]
			if c - w >= 0:
				dp[r][c] = max(dp[r][c], dp[r-1][c], v + dp[r-1][c-w])
	print((dp[-1][-1]))
	stdout.close()

if __name__ == "__main__":
	main()
# Original solution
from bisect import bisect_left
def main():
    n, w = list(map(int, input().split()))
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    for i in range(n):
        for j in reversed(list(range(item[i][0], w+1))):
            dp[j] = max(dp[j-item[i][0]]+item[i][1], dp[j])
    print((dp[w]))

if __name__ == "__main__":
    main()


# Optimized solution
from bisect import bisect_left
def main():
    n, w = list(map(int, input().split()))
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for i in range(n):
        for j in reversed(list(range(item[i][0], min(w+1, x+item[i][0]+1)))):
            dp[j] = max(dp[j-item[i][0]]+item[i][1], dp[j])
        x += item[i][0]
    ans = 0
    for i in reversed(list(range(w+1))):
        if dp[i] > ans:
            ans = dp[i]
    print(ans)

if __name__ == "__main__":
    main()