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

def main():
    s = input()
    l = [s[0]]
    lap = l.append
    for i in range(1,len(s)):
        if s[i] == s[i-1]:
            l[-1] = l[-1] + s[i]
        else:
            lap(s[i])
    dlist = []
    plist = []
    dap = dlist.append
    pap = plist.append
    if l[0][0] == "<":
        dap(0)
    for i in l:
        if i[0] == "<":
            pap(len(i))
        else:
            dap(len(i))
    if l[-1][0] == ">":
        pap(0)
    dm = max(dlist)
    pm = max(plist)
    sm = [i for i in range(0,max(dm,pm)+1)]
    for i in range(1,len(sm)):
        sm[i] = sm[i-1]+sm[i]
    for i in range(1,len(dlist)):
        x = dlist[i]
        y = plist[i-1]
        if y <= x:
            dlist[i] = sm[x]
            plist[i-1] = sm[max([0,y-1])]
        else:
          dlist[i] = sm[max([0,x-1])]
          plist[i-1] = sm[y]
    dlist[0] = sm[dlist[0]]
    plist[-1] = sm[plist[-1]]
    print(sum(dlist)+sum(plist))
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = input()
    f1 = False
    f2 = False
    l = [1]
    if s[0] == "<":
        f1 = True
        l.insert(0,0)
    if s[-1] == ">":
        f2 = True
    sm = [i for i in range(0,len(s)+1)]
    for i in range(1,len(sm)):
        sm[i] = sm[i-1]+sm[i]
    lap = l.append
    for i in range(1,len(s)):
        if s[i] == s[i-1]:
            l[-1] += 1
        else:
            lap(1)
    dlist = []
    plist = []
    dap = dlist.append
    pap = plist.append
    if f2:
        l.append(0)
    for i in range(len(l)//2):
        dap(l[2*i])
        pap(l[2*i+1])   
    for i in range(1,len(dlist)):
        x = dlist[i]
        y = plist[i-1]
        if y <= x:
            dlist[i] = sm[x]
            plist[i-1] = sm[max([0,y-1])]
        else:
          dlist[i] = sm[max([0,x-1])]
          plist[i-1] = sm[y]
    dlist[0] = sm[dlist[0]]
    plist[-1] = sm[plist[-1]]
    print(sum(dlist)+sum(plist))
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

from collections import defaultdict
dp = defaultdict(lambda: 0)
dp[0] = 1
B = 10000
for a in A:
    for k,v in list(dp.items()):
        if k%B + a > S: continue
        dp[k+a+B] += v

ans = 0
for k,v in dp.items():
    if k%B!=S: continue
    i = k//B
    ans += pow(2,N-i,MOD) * v
print(ans%MOD)

### FIXED CODE ###

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

dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1

for i,a in enumerate(A):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j]*2
        dp[i+1][j] %= MOD
        if j+a <= S:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= MOD
print(dp[-1][-1])
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
bc = [tuple(map(int, input().split())) for i in range(Q)]
A = np.asarray(A)
for b, c in bc:
    A = np.where(A == b, c, A)
    print(sum(A))


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
ans = sum(A)
A = Counter(A)
bc = [tuple(map(int, input().split())) for i in range(Q)]
for b, c in bc:
    v = A.pop(b, None)
    if v:
        A[c] += v
        ans = ans+((c-b)*v)
    print(ans)
### BUGGY CODE ###

import sys
f = sys.stdin


def memoize(f):
  memo = {}
  def inner(v1,v2,v3,v4):
      if not (v1,v2,v3,v4) in memo:
        memo[v1,v2,v3,v4] = f(v1,v2,v3,v4)
      return memo[v1,v2,v3,v4]
  return inner

@memoize
def q(t,s,e,func):
    if s == e:
        return t[s]
    else:
        return func(q(t,s,(s+e)//2,func),q(t,(s+e)//2 + 1,e,func))

_, d = map(int, f.readline().split())

b = []
for line in f:
    xi, yi, bi = map(int, line.split())
    b.append((bi,xi,yi))
b = sorted(b)
x = tuple(xi for _,xi,_ in b)
y = tuple(yi for _,_,yi in b)

max_size = i = j = 0
while j < len(b) - 1:
    for k in range(j,-1,-1):
        if b[k][0] + d < b[j][0]:
            break
        i = k
    for k in range(i,len(b)):
        if b[i][0] + d < b[k][0]:
            break
        j = k

    max_size = max(max_size,(q(x,i,j,max) - q(x,i,j,min)) * (q(y,i,j,max) - q(y,i,j,min)))
    j+=1
    
print(max_size)

### FIXED CODE ###

import math
def segmentTree(dat, f, sentinel):
        pad = 2 ** math.ceil(math.log(len(dat),2))
        dat = [0] * pad + dat + [sentinel] * (pad - len(dat))
        for i in range(pad - 1, 0, -1):
            dat[i] = f(dat[i * 2],dat[i * 2 + 1])
        return dat

def get_lr(b,d):
    l = r = 0
    while r < len(b):
        while b[l] + d < b[r]:
            l += 1
        for r in range(r,len(b)):
            if b[l] + d < b[r]:
                r -= 1
                break
        r += 1
        yield l,r
        l += 1
    
import sys
f = sys.stdin

_, d = map(int, f.readline().split())

xyb = []
for line in f:
    xyb.append(tuple(map(int, line.split())))
from operator import itemgetter
xyb.sort(key=itemgetter(2))

x = [xybi[0] for xybi in xyb]
y = [xybi[1] for xybi in xyb]
b = [xybi[2] for xybi in xyb]

xmax = segmentTree(x,max,sentinel = 0)
xmin = segmentTree(x,min,sentinel = 2000000)
ymax = segmentTree(y,max,sentinel = 0)
ymin = segmentTree(y,min,sentinel = 2000000)


pad = len(xmax) // 2
max_size = 0
def create_index(l,r):
    index = []
    ia = index.append
    while l < r:
        if r & 1:
            r -= 1
            ia(r)
        if l & 1:
            ia(l)
            l += 1
        l >>= 1
        r >>= 1
    return index

for l,r in get_lr(b,d):
    l += pad 
    r += pad
    index = create_index(l,r)

    now_xmax = max(xmax[i] for i in index)
    now_ymax = max(ymax[i] for i in index)
    if max_size < now_xmax * now_ymax:
        max_size = max(max_size,((now_xmax - min(xmin[i] for i in index)) * (now_ymax - min(ymin[i] for i in index))))
print(max_size)
### BUGGY CODE ###

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

dices =[]
dicesSum=[]
for i in range(N-K+1):
    l= ps[i:i+K]
    dices.append(l)
    dicesSum.append(sum(l))

max_value = max(dicesSum)
max_index = dicesSum.index(max_value)

exp=0
for p in dices[max_index]:
    exp += 0.5*p +0.5
print(exp)


### FIXED CODE ###

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

dicesSum=[]
l1=ps[0:K]
dicesSum.append(sum(l1))

if K==N:
    exp= (K+ dicesSum[0])/2
    print(exp)
else:
    for i in range(1,N-K+1):
        dicesSum.append(dicesSum[i-1]-ps[i-1]+ps[i+K-1])
    max_value = max(dicesSum)
    exp= (K+ max_value)/2
    print(exp)
### BUGGY CODE ###

ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]


n = int(input())
a = ai()
MOD = 10**9+7

from collections import Counter
dup = list(Counter(sorted(a)).values()).index(2)+1
ant = a.index(dup)
post = a[::-1].index(dup)


def nCb(n, r):
    fac = [1, 1] + [0] * n
    finv = [1, 1] + [0] * n
    inv = [0, 1] + [0] * n
    for i in range(2, n + 2):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = -inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
        
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD


for k in range(1,n+2):
    if k == 1:
        print(n)
    else:
        ans = nCb(n+1,k)
        if ant+post+1 >= k:
            ans -= nCb(ant+post,k-1)
        print(ans)


### FIXED CODE ###

ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]

n = int(input())
a = ai()

dup = sum(a)-n*(n+1)//2
ant = a.index(dup)
post = a[::-1].index(dup)

mod = 10**9+7
factorial = [1]
for i in range(1,n+2):
    factorial.append(factorial[i-1]*i %mod)

inverse = [0]*(n+2)
inverse[n+2-1] = pow(factorial[n+2-1], mod-2,mod)
for i in range(n+2-2, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod


def nCr(n,r):
    if n<r or n==0 or r==0:
        return 0
    return factorial[n] * inverse[r] * inverse[n-r] % mod


for k in range(1,n+2):
    if k == 1:
        print(n)
    else:
        ans = nCr(n+1,k) - nCr(ant+post,k-1)
        if ans < 0:
            ans += mod
        print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

import heapq
seen = set()
queue = [(0, CH-1, CW-1)]

while queue:
    move, row, col = heapq.heappop(queue)

    # print(row, col, S[row][col], move, queue)
    if row == DH-1 and col == DW-1:
        print(move)
        sys.exit(0)

    if (row, col) in seen:
        continue

    seen.add((row, col))

    for r_offset, c_offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        new_row = row + r_offset
        new_col = col + c_offset
        # print(new_row, new_col)
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.':
            heapq.heappush(queue, (move, new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0:
                continue
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.':
                heapq.heappush(queue, (move+1, new_row, new_col))

print(-1)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

# 1-index -> 0-index
CH -= 1
CW -= 1
DH -= 1
DW -= 1

from collections import deque
seen = set()
queue = deque([(0, CH, CW)])
offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]

while queue:
    move, row, col = queue.popleft()

    # print(row, col, queue)

    if (row, col) in seen:
        continue

    if row == DH and col == DW:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in offsets:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            queue.appendleft((move, new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                queue.append((move+1, new_row, new_col))

print(-1)
### BUGGY CODE ###

n= int(input())
a_list = list(map(int, input().split()))
 
ans=1
for i in a_list:
  ans=ans*i
  if ans==0:
    break
  
if ans>1000000000000000000:
  ans=-1

print(ans)

### FIXED CODE ###

n= int(input())
a_list = list(map(int, input().split()))
 
a_list = [n for n in a_list if n!=1]  
#print(a_list)
ans=1

if 0 in a_list:
  ans=0
elif len(a_list)>56:
  ans=-1
else:
  for i in a_list:
    ans=ans*i
  if ans>1000000000000000000:
      ans=-1
  
print(ans)
### BUGGY CODE ###

import time
def main():
    N = int(input())
    A = input()
    ans = 1
    inf = 10**18
    t = time.time()

    for a in A.split():
        ans *= int(a)

    if ans > inf:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import time
def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    ans = 1
    inf = 10**18
    t = time.time()

    if 0 in A:
        print(0)
        exit()

    for i in range(len(A)):
        ans *= A[i]
        if ans > inf :
            print(-1)
            exit()

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

import math,itertools,fractions,heapq,bisect,sys,copy,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[list(S()) for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j,0))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      while len(q)>0:
        y,x,c=q.popleft()
        visited[y][x]=c

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if 0<=ny<h and 0<=nx<w:
            if field[ny][nx]=='#':
              continue
            if visited[ny][nx]!=-1:
              continue
            q.append((ny,nx,c+1))
      ans=max(ans,c)
  return ans

# main()
print(main())


### FIXED CODE ###

import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      visited[i][j]=0
      _ans=0
      while q:
        y,x=q.popleft()

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='#':
            continue
          if visited[ny][nx]!=-1:
            continue
          _ans=visited[y][x]+1
          visited[ny][nx]=_ans
          q.append((ny,nx))
      ans=max(ans,_ans)
  return ans

# main()
print(main())
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0

for i in range(1000):
        i = '0' * (3 - len(str(i))) + str(i)
        keep = 0

        for j in range(n):
                if s[j] == i[keep]:
                        keep += 1
                if keep == 3:
                        ans += 1
                        break

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = 0

for i in range(1000):
        i = '0' * (3 - len(str(i))) + str(i)
        keep = 0

        for j in range(n):
                if s[j] == i[keep]:
                        keep += 1
                if keep == 3:
                        ans += 1
                        break

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

import bisect

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

color = [float("inf")]
min_color = color[0]
for i in a:
    if i <= min_color:
        color = [i] + color
        min_color = i
    else:
        insert = bisect.bisect_left(color, i)
        del color[insert - 1]
        bisect.insort(color, i)
        if insert == 1:
            min_color = color[0]
print(len(color) - 1)

### FIXED CODE ###

import bisect, collections

n = int(input())
num = collections.deque([])
for i in range(n):
    a = int(input())
    temp = bisect.bisect_left(num, a)
    if temp == 0:
        num.appendleft(a)
    else:
        num[temp - 1] = a
print(len(num))
### BUGGY CODE ###

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

n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    G[a].append(b)
    G[b].append(a)

def dfs(cur, cost):
    dist[cur] = cost
    for to in G[cur]:
        if dist[to] == -1:
            dfs(to, cost+1)
dist = [-1]*n
dfs(0, 0)
m = max(dist)
for i in range(n):
    if dist[i] == m:
        start = i
        break
dist = [-1]*n
dfs(start, 0)
m = max(dist)

if m%3==1:
    print("Second")
else:
    print("First")

### FIXED CODE ###

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

n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    G[a].append(b)
    G[b].append(a)

def dfs(cur, cost):
    dist[cur] = cost
    for to in G[cur]:
        if dist[to] == -1:
            dfs(to, cost+1)
dist = [-1]*n
dfs(0, 0)
m = max(dist)
for i in range(n):
    if dist[i] == m:
        start = i
        break
dist = [-1]*n
dfs(start, 0)
m = max(dist)

if m%3==1:
    print("Second")
else:
    print("First")
### BUGGY CODE ###

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

DP = [0]*(10**6+1)

A.sort()
Sum = 0

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1,10**6):
            if A[i]*j <= 10**6:
                DP[A[i]*j] = 1
            else:
                break
                
        if A.count(A[i]) == 1:
            Sum += 1

print(Sum)

### FIXED CODE ###

from collections import defaultdict

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

DP = [0] * (10 ** 6 + 1)

A.sort()
Sum = 0

d = defaultdict(int)
for key in A:
    d[key] += 1

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1, 10 ** 6):
            if A[i] * j <= 10 ** 6:
                DP[A[i] * j] = 1
            else:
                break

        if d[A[i]] == 1:
            Sum += 1
print(Sum)
### BUGGY CODE ###

s = input()

flag = 0
cnt = 0
n = int(input())

for i in range(n):
    que = input()
    if(len(que) == 1):
        cnt += 1
    else:
        que = que.split()
        if(que[1]=="1" and cnt%2 == 0):
            s = que[2] + s
        if(que[1]=="1" and cnt%2 == 1):
            s = s + que[2]
        if(que[1]=="2" and cnt%2 == 0):
            s = s +que[2] 
        if(que[1]=="2" and cnt%2 == 1):
            s = que[2] + s

if(cnt%2 == 0):
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

s = input()

flag = 0
cnt = 0
n = int(input())

que_ar = [input() for _ in range(n)]

f_x = ["" for _ in range(n)]
b_x = ["" for _ in range(n)]


f = n-1
b = 0

for i in range(n):
    que = que_ar[i]
    if(len(que) == 1):
        cnt += 1
    else:
        que = que.split()
        if(cnt%2 == 0):
            if(que[1]=="1"):
                f_x[f] = que[2]
                f -= 1
            else:
                b_x[b] = que[2]
                b += 1
        else:
            if(que[1]=="1"):
                b_x[b] = que[2]
                b += 1
            else:
                f_x[f] = que[2]
                f -= 1

s = "".join(f_x)+s+"".join(b_x)             
                
if(cnt%2 == 0):
    print(s)
else:
    print(s[::-1])
### BUGGY CODE ###

from collections import Counter
S = list(input())
T = list(input())

for w in S:
    if w in T:
        idxs = [i for i, x in enumerate(S) if x == w]
        idxt = [i for i, x in enumerate(T) if x == w]
        for num in idxs[::-1]:
            del S[num]
        for num in idxt[::-1]:
            del T[num]

s_count = Counter(S)
del_s = []
t_count = Counter(T)
del_t = []

for ks, vs in list(s_count.items()):
    for kt, vt in list(t_count.items()):
        if vs == vt:
            del_s.append(ks)
            del_t.append(kt)
            del s_count[ks]
            del t_count[kt]
            break

if len(set(S)) == len(del_s) and len(set(T)) == len(del_t):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

from collections import defaultdict
S = list(input())
T = list(input())
l = len(S)
ds = defaultdict(str)
dt = defaultdict(str)
for i in range(l):
    if ds[S[i]] == "":
        ds[S[i]] = T[i]
    elif ds[S[i]] == T[i]:
        pass
    else:
        print('No')
        exit()
    if dt[T[i]] == "":
        dt[T[i]] = S[i]
    elif dt[T[i]] == S[i]:
        pass
    else:
        print('No')
        exit()

print('Yes')
### BUGGY CODE ###

N=int(input())
M=int(N**0.5)+1

for i in range(1,1+N):
    ans=0
    for x in range(1,M):
        for y in range(1,x+1):
            if x**2+y**2+x*y<N:
                for z in range(1,y+1):
                    if x**2+y**2+z**2+x*y+y*z+z*x==i:
                        if x==y==z:
                            ans+=1
                        elif x!=y and y!=z and z!=x:
                            ans+=6
                        else:
                            ans+=3
    print(ans)

### FIXED CODE ###

N=int(input())

for i in range(1,1+N):
    ans=0
    M=int(i**0.5)+1
    for x in range(1,M):
        if x**2<i:
            for y in range(1,x+1):
                if x**2+y**2+x*y<i:
                    for z in range(1,y+1):
                        if x**2+y**2+z**2+x*y+y*z+z*x==i:
                            if x==y==z:
                                ans+=1
                            elif x!=y and y!=z and z!=x:
                                ans+=6
                            else:
                                ans+=3
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def main():
    n, w = map(int, input().split())
    weight_list = []
    value_list = []
    wv_list = []
    for i in range(n):
        weight, value = map(int, input().split())
        weight_list.append(weight)
        value_list.append(value)
    
    dp = [[0] * (w+1) for i in range(n)]
    for i in range(w+1):
        if weight_list[0] <= i:
            dp[0][i] = value_list[0]
    for i in range(1, n):
        for j in range(0, w+1):
            if weight_list[i] <= j:
                # print(dp[i-1][j-weight_list[i]]+value_list[i])
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight_list[i]] + value_list[i])
            else:
                dp[i][j] = dp[i - 1][j]
    print(dp[-1][-1])
if __name__ == "__main__":
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
def main():
    n, w = map(int, input().split())
    weight_list = []
    value_list = []
    wv_list = []
    for i in range(n):
        weight, value = map(int, input().split())
        weight_list.append(weight)
        value_list.append(value)
    
    dp = [[0] * (w+1) for i in range(n)]
    for i in range(w+1):
        if weight_list[0] <= i:
            dp[0][i] = value_list[0]
    for i in range(1, n):
        for j in range(0, w+1):
            if weight_list[i] <= j:
                # print(dp[i-1][j-weight_list[i]]+value_list[i])
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight_list[i]] + value_list[i])
            else:
                dp[i][j] = dp[i - 1][j]
    print(dp[-1][-1])
if __name__ == "__main__":
    main()