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

import sys
from itertools import groupby

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def len_count(S):
    H, W = len(S), len(S[0])
    L = [[0] * W for _ in range(H)]
    for row_S, row_L in zip(S, L):
        idx = 0
        for k, g in groupby(list(row_S)):
            n = len(list(g))
            if k == '.':
                row_L[idx : idx + n] = [n] * n
            idx += n
    return L


def main():
    H, W = map(int, readline().split())
    S = [readline().strip() for _ in range(H)]

    L1 = len_count(S)
    L2 = list(zip(*len_count(list(zip(*S)))))

    ans = 0
    for row1, row2 in zip(L1, L2):
        for j in range(W):
            if ans < row1[j] + row2[j] - 1:
                ans = row1[j] + row2[j] - 1

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from itertools import groupby

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def len_count(S):
    H, W = len(S), len(S[0])
    L = [[0] * W for _ in range(H)]
    for row_S, row_L in zip(S, L):
        vec = [1]
        for i in range(1, W):
            if row_S[i - 1] == row_S[i]:
                vec[-1] += 1
            else:
                vec.append(1)

        idx = 0
        valid = row_S[0] == '.'
        for n in vec:
            if valid:
                for i in range(idx, idx + n):
                    row_L[i] = n
            idx += n
            valid = not valid

    return L


def main():
    H, W = map(int, readline().split())
    S = [readline().strip() for _ in range(H)]

    L1 = len_count(S)
    L2 = len_count(list(zip(*S)))

    ans = 0
    for i in range(H):
        for j in range(W):
            if ans < L1[i][j] + L2[j][i] - 1:
                ans = L1[i][j] + L2[j][i] - 1

    print(ans)
    return


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

def func(n):
    divisors = [] 
    for i in range(1, int(n**0.5)+1):
        if(n%i == 0):
            divisors.append(i)
            if(i != n //i):
                divisors.append(n//i)
    return len(divisors)

N = int(input())

ans = 0
for i in range(1, N+1):
    ans += i*func(i)
print(ans)

### FIXED CODE ###

N = int(input())

ans = 0

for i in range(1, N+1):
    y = N//i
    ans += ((y*(y+1))//2)*i
print(ans)
### BUGGY CODE ###

def C(n,r):
  a=1
  b=1
  c=1
  for i in range(1,n+1):
    a*=i
  for j in range(1,r+1):
    b*=j
  for k in range(1,n-r+1):
    c*=k
  return a//(b*c)

n,k=map(int,input().split())
for i in range(1,k+1):
  print(C(n-k+1,i)*C(k-1,i-1)%(10**9+7))

### FIXED CODE ###

import math
def C(n,r):
  if n<0 or r<0 or n-r<0:
    return 0
  else:
    return math.factorial(n)//(math.factorial(r)*math.factorial(n-r))

n,k=map(int,input().split())
for i in range(1,k+1):
  print(C(n-k+1,i)*C(k-1,i-1)%(10**9+7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
from fractions import gcd

l = a[0]
for i in range(1,n):
  l = l*a[i]//gcd(l,a[i])

b = [0]*n
ans = 0
for i in range(n):
  b[i] = l//a[i]
  ans += b[i]%mod

print(ans%mod)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
from fractions import gcd

l = a[0]
for i in range(1,n):
  l = l*a[i]//gcd(l,a[i])

ans = 0
for i in range(n):
  ans += l//a[i]

print(ans%mod)
### BUGGY CODE ###

s = input()
counter = 0
for left in range(len(s)):
    mod = 0
    for right in range(left, len(s)):
        mod *= 10
        mod += int(s[right])
        mod %= 2019
        if mod == 0:
            counter += 1
print(counter)

### FIXED CODE ###

from collections import Counter
s = input()
ac = [0]

def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p

for i in range(len(s)):
    char = s[i]
    digit = len(s) - i - 1
    ac.append((ac[-1] + (int(char) * power_func(10, digit, 2019))) % 2019)
#print(ac)

C = Counter(ac)
#print(C)
ans = 0
for val in C.values():
    ans += val * (val - 1) // 2
print(ans)
### BUGGY CODE ###

from fractions import gcd
 
def primeNum(n):
  prime=[1]
  if n % 2 == 0:
    prime.append(2)
    while n % 2 == 0:
      n = n // 2
  for k in range(3, n+1, 2):
    if n % k == 0:
      prime.append(k)
      while n % k == 0:
        n = n // k
  return prime
 
a,b = list(map(int, input().split()))
n=gcd(a,b)
print(len(primeNum(n)))

### FIXED CODE ###

from fractions import gcd
 
def primeNum(n):
  ans = 1
  if n == 1:
    return ans
  if n % 2 == 0:
    ans += 1
    while n % 2 == 0:
      n = n // 2
  for k in range(3, int(n**0.5)+1, 2):
    if n % k == 0:
      ans += 1
      while n % k == 0:
        n = n // k
    if n == 1:
      return ans
  if n != 1:
    ans += 1
  return ans
  
a,b = list(map(int, input().split()))
n=gcd(a,b)
print(primeNum(n))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import queue

def main():
     n = int(input())
     s = input()

     r_list = []
     g_list = []
     b_list = []

     ans = 0

     for i in range(n):
          if s[i] == 'R':
               r_list.append(i)
          elif s[i] == 'G':
               g_list.append(i)
          else:
               b_list.append(i)

     for i in range(n):
          if s[i] == 'R':
               spot = r_list.pop(0)
               ans += check(spot, g_list, b_list)

          if s[i] == 'G':
               spot = g_list.pop(0)
               ans += check(spot, r_list, b_list)

          if s[i] == 'B':
               spot = b_list.pop(0)
               ans += check(spot, r_list, g_list)

     print(ans)

def check(spot, first, second):
     ret = 0
     limit_first = first.copy()
     limit_second = second.copy()
     for f in first:
          ignore = f + (f - spot)
          limit_second = [s for s in limit_second if s > f]

          ret += len(limit_second)
          if ignore in limit_second:
               ret += -1

     for s in second:
          ignore = s + (s - spot)
          limit_first = [f for f in limit_first if f > s]

          ret += len(limit_first)
          if ignore in limit_first:
               ret += -1
     
     return ret

if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

import queue

def main():
     n = int(input())
     s = input()

     r_list = []
     g_list = []
     b_list = []

     ans = 0

     for i in range(n):
          if s[i] == 'R':
               r_list.append(i)
          elif s[i] == 'G':
               g_list.append(i)
          else:
               b_list.append(i)

     for i in range(n):
          if s[i] == 'R':
               ans += check(i, g_list, b_list)

          if s[i] == 'G':
               ans += check(i, r_list, b_list)

          if s[i] == 'B':
               ans += check(i, r_list, g_list)

     print(ans)

def check(spot, first, second):
     ret = 0
     small_first = []
     big_first = []
     small_second = []
     big_second = []

     for f in first:
          if f < spot: small_first.append(spot - f)
          else: big_first.append(f - spot)

     for s in second:
          if s < spot: small_second.append(spot - s)
          else: big_second.append(s - spot)

     return len(small_first) * len(big_second) + len(small_second) * len(big_first) - len(set(small_first) & set(big_second)) - len(set(small_second) & set(big_first))
     
if __name__ == "__main__":
    main()
### BUGGY CODE ###

class UnionFind:
    def __init__(self, size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


n, K, L = map(int, input().split())
pq = [tuple(int(x) for x in input().split()) for _ in range(K)]
rs = [tuple(int(x) for x in input().split()) for _ in range(L)]

uk = UnionFind(n)
for p, q in pq:
    rp = uk.find(p - 1)
    rq = uk.find(q - 1)
    if rp != rq:
        uk.union(rp, rq)

ul = UnionFind(n)
for p, q in rs:
    rp = ul.find(p - 1)
    rq = ul.find(q - 1)
    if rp != rq:
        ul.union(rp, rq)

ans = ['' for _ in range(n)]
for i in range(n):
    temp = 0
    for j in range(n):
        if uk.find(i) == uk.find(j) and ul.find(i) == ul.find(j):
            #print(uk.find(i), uk.find(j), ul.find(i), ul.find(j), i, j)
            temp += 1
    ans[i] = str(temp)

print(' '.join(ans))




### FIXED CODE ###

from collections import Counter

class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find_root(self, x):
        if self.p[x] != x:
            self.p[x] = self.find_root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def get_size(self, x):
        return self.size[self.find_root(x)]


n, K, L = map(int, input().split())
pq = [tuple(int(x)-1 for x in input().split()) for _ in range(K)]
rs = [tuple(int(x)-1 for x in input().split()) for _ in range(L)]

uk = UnionFind(n)
for p, q in pq:
    uk.unite(p, q)

ul = UnionFind(n)
for p, q in rs:
    ul.unite(p, q)

res = [uk.find_root(i) * 1000000 +  ul.find_root(i) for i in range(n)]
c = Counter(res)
ans = [0] * n

for i in range(n):
    ans[i] = c[res[i]]

print(*ans, sep=' ')
### BUGGY CODE ###

s = list(input())

i = 0
count = 0
if len(s) >=3:
  while i <= len(s)-2:
    if s[i:i+3] == list("ABC"):
      s[i] = "B"
      s[i+1] = "C"
      s[i+2] = "A"
      count += 1
      if i != 0:
        i -= 1
    else:
      i += 1

print(count)

### FIXED CODE ###

s = list(input())

i = 0
bc = list("BC")

a_cnt = 0
res = 0
i = 0
while i <= len(s)-1:
  if s[i] == "A":
    a_cnt += 1
  elif s[i:i+2] == bc:
    res += a_cnt
    i += 1
  else:
    a_cnt = 0
  i += 1

print(res)
### BUGGY CODE ###

A, B, N = map(int, input().split())
pre_x = list()
ind = B-1
while ind <= N:
    pre_x.append(ind)
    ind += B

if len(pre_x) == 0:
    ans = int(A*N/B) - A*int(N/B)
    print(ans)
else:
    ans = 0
    for x in pre_x:
        ans = max(ans, int(A*x/B) - A*int(x/B))
    
    print(ans)

### FIXED CODE ###

A, B, N = map(int, input().split())
# pre_x = list()
# ind = B-1
# while ind <= N:
#     pre_x.append(ind)
#     ind += B

# if len(pre_x) == 0:
#     ans = int(A*N/B) - A*int(N/B)
#     print(ans)
# else:
#     ans = 0
#     for x in pre_x:
#         ans = max(ans, int(A*x/B) - A*int(x/B))
    
#     print(ans)

# if B > N:
#     print(int(A*N/B) - A*int(N/B))
# else:
#     x_under = max(int())

if B > N:
    print(int(A*N/B) - A*int(N/B))
else:
    x = B - 1
    print(int(A*x/B) - A*int(x/B))
### BUGGY CODE ###

N = int(input())
nos = list(map(int, input().split()))
count = 0
for j in range(N):
  judge = True
  for k in range(j):
    if nos[k] < nos[j]:
      judge = False
  if judge:
    count += 1
print(count)

### FIXED CODE ###

N = int(input())
nos = list(map(int, input().split()))
count = 1
min = nos[0]
for j in range(1,N):
  if nos[j] <= min:
    count += 1
    min = nos[j]
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    P=tuple(map(int1,input().split()))
    c=[[1]*N for _ in range(N)]
    ans=0
    dy,dx=[1,0,-1,0],[0,1,0,-1]
    for p in P:
        que=deque([(p//N,p%N)])
        d=[[INF]*N for _ in range(N)]
        d[p//N][p%N]=0
        f=True
        while que and f:
            y,x=que.popleft()
            for k in range(4):
                ny,nx=(y+dy[k],x+dx[k])
                if 0<=ny<N and 0<=nx<N:
                    if d[ny][nx]==INF:
                        if c[ny][nx]==1:
                            d[ny][nx]=d[y][x]+1
                            que.append((ny,nx))
                        else:
                            d[ny][nx]=d[y][x]
                            que.appendleft((ny,nx))
                else:
                    tmp=d[y][x]
                    f=False
                    break
        ans+=tmp
        c[p//N][p%N]=0
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
M=N**2
P=tuple(map(int1,input().split()))
d=[0]*M
for i in range(N):
    for j in range(N):
        d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
used=[1]*M
ans=0
que=[]
for p in P:
    ans+=d[p]
    used[p]=0
    que.append(p)
    while que:
        x=que.pop()
        for ddx in (-1,1,-N,N):
            nx=x+ddx
            if 0<=nx<M:
                if used[x]==0 and d[nx]-d[x]>=1:
                    d[nx]-=1
                    que.append(nx)
                elif used[x]==1 and d[nx]-d[x]>=2:
                    d[nx]-=1
                    que.append(nx)
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a = list(int(input()) for i in range(m))
#for i in range(m):
#  a.append(int(input()))
b=[0 for x in range(n+1)]
b[0]=1
for i in range(1,n+1):
  if i in a:
    continue
  x=b[i-1]
  if i>1:x+=b[i-2]
  b[i]=x
print(b[n]%(10**9+7))

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
a = set(int(input()) for _ in range(m))
#for i in range(m):
#  a.append(int(input()))
b=[0 for x in range(n+1)]
b[0]=1
for i in range(1,n+1):
  if i in a:
    continue
  x=b[i-1]
  if i>1:x+=b[i-2]
  b[i]=x
print(b[n]%(10**9+7))
### BUGGY CODE ###

import sys
N=int(sys.stdin.readline())
values = []
res = 1
values=(sys.stdin.readline().split())
for v in values:
    res *= int(v)
if res > 1000000000000000000:
  print(-1)
else:
  print(res)


### FIXED CODE ###

import sys
N=int(sys.stdin.readline())
values = []
res = 1
values=sys.stdin.readline().split()
for v in values:
    if int(v) == 0:
        print(0)
        exit(0)

for v in values:
    res *= int(v)
    if res > 1000000000000000000:
        print(-1)
        exit(0)
print(res)
### BUGGY CODE ###

import math

def combinations_count(n, r):
    if n < 2 :
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n = int(input())
a = input().split()

dic = {}
for i in range(len(a)) :
    if a[i] in dic :
        dic[a[i]] = dic[a[i]] + 1
    else :
        dic[a[i]] = 1

#print(dic)
dicSum = {}
total = 0

for key in dic:
    dicSum[key] = combinations_count(dic[key], 2)
    total += dicSum[key]

#print(dicSum, total)

for i in range(n) :
    #print(total, dicSum[a[i]], combinations_count(dic[a[i]]-1, 2))
    print(total - dicSum[a[i]] + combinations_count(dic[a[i]]-1, 2))


### FIXED CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    if n < 2 :
        return 0
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

import math

'''
def combinations_count(n, r):
    if n < 2 :
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
'''

n = int(input())
a = input().split()

dic = {}
for i in range(len(a)) :
    if a[i] in dic :
        dic[a[i]] = dic[a[i]] + 1
    else :
        dic[a[i]] = 1

#print(dic)
dicSum = {}
total = 0

for key in dic:
    dicSum[key] = cmb(dic[key], 2)
    total += dicSum[key]

#print(dicSum, total)

for i in range(n) :
    #print(total, dicSum[a[i]], combinations_count(dic[a[i]]-1, 2))
    print(total - dicSum[a[i]] + cmb(dic[a[i]]-1, 2))
### BUGGY CODE ###

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

N = 13
MOD = 10 ** 9 + 7

s = input()[::-1]

dp = [0 for i in range(N)]
nextdp = [0 for i in range(N)]
zeros = [0 for i in range(N)]
dp[0] = 1

for i, si in enumerate(s):
    nextdp = zeros[:]
    r = 10 ** i % N

    for j in range(10):
        jj = j
        if si == "?":
            pass
            # c = (j * 10 ** i) % N
        elif j == 0:
            jj = int(si)
        else:
            break

        for k in range(N):
            l = (k + r * jj) % N
            nextdp[l] = (nextdp[l] + dp[k]) % MOD

    dp = nextdp[:]

print(dp[5])


### FIXED CODE ###

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

N = 13
MOD = 10 ** 9 + 7

s = input()[::-1]

dp = [0 for i in range(N)]
nextdp = [0 for i in range(N)]
zeros = [0 for i in range(N)]
dp[0] = 1

r = 1
for i, si in enumerate(s):
    nextdp = zeros[:]

    for j in range(10):
        jj = j
        if si == "?":
            pass
            # c = (j * 10 ** i) % N
        elif j == 0:
            jj = int(si)
        else:
            break

        for k in range(N):
            l = (k + r * jj) % N
            nextdp[l] = (nextdp[l] + dp[k]) % MOD

    dp = nextdp
    r = r * 10 % N

print(dp[5])
### BUGGY CODE ###

import numpy as np

def a():
  n, p = list(map(int, input().split()))
  s = input()
  if(p==2 or p==5):
    count=0
    for i in range(1,n+1):
      if(int(s[-i])%p == 0):
        count += n-i+1
    print(count)
    return

  num = np.array([int(s[i:]) for i in range(n)]) % p
  c = sum(num == 0)
  count = c*(c+1)//2
  for i in range(1,p):
    c = sum(num == i)
    count += c*(c-1)//2
  print(count)
  return
a()

### FIXED CODE ###

import numpy as np

def a():
  n, p = list(map(int, input().split()))
  num = [int(s) for s in input()]
  
  if(p==2 or p==5):
    count=0
    for i in range(1,n+1):
      if(num[-i]%p == 0):
        count += n-i+1
    print(count)
    return
  
  counts = np.zeros(p)
  tmp = 0
  tens = 1
  for i in range(1,n+1):
    tmp = (tens*num[-i] + tmp) % p
    counts[tmp] += 1
    tens = (tens*10)%p
  ret = int(counts[0] + sum(counts*(counts-1)//2))
  print(ret)
  return
a()
### BUGGY CODE ###

from collections import deque

N, M, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# print(N, M, K)
# print(A)
# print(B)


answer = 0
for i in range(len(A) + 1):
    consumption_A = sum(A[:i])
    if (consumption_A > K): break

    for j in range(len(B) + 1):
        consumption_B = sum(B[:j])
        consumption = consumption_A + consumption_B
        if (consumption > K): break
    
        num_books = i + j
        answer = max(answer, num_books)

print(answer)


### FIXED CODE ###

from collections import deque

N, M, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# print(N, M, K)
# print(A)
# print(B)


consumptions_A = [0]
for i in range(len(A)):
    consumptions_A.append(consumptions_A[i] + A[i])

consumptions_B = [0]
for i in range(len(B)):
    consumptions_B.append(consumptions_B[i] + B[i])

answer = 0
j = M
for i in range(len(consumptions_A)):
    if (consumptions_A[i] > K): break

    remaining_time = K - consumptions_A[i]
    while consumptions_B[j] > remaining_time:
        j -= 1
    
    num_books = i + j
    answer = max(answer, num_books)

print(answer)
### BUGGY CODE ###

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

count = {}

for a in A:
    count[a] = count.get(a, 0) + 1

sorted_ = sorted(count.items(), key=lambda x: x[1])

total = 0
while K < len(sorted_):
    k, v = sorted_[0]
    sorted_ = sorted_[1:]
    total += v

print(total)

### FIXED CODE ###

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

count = {}

for a in A:
    count[a] = count.get(a, 0) + 1

tmp = []
for k, v in count.items():
    tmp.append(v)

tmp = sorted(tmp)

total = 0
for i in range(len(tmp) - K):
    total += tmp[i]

print(total)
### BUGGY CODE ###

s = input()
n = int(input())

for _ in range(n):
  query = input().split()
  if query == ["1"]:
    s = s[::-1]
  else:
    if query[1] == "1":
      s = query[2] + s
    else:
      s = s + query[2]

print(s)

### FIXED CODE ###

s = input()
n = int(input())

reverse  = False
forward  = ""
backward = ""

for _ in range(n):
  query = input().split()
  if query == ["1"]:
    reverse = not reverse
  else:
    if query[1] == "1":
      if reverse:
        backward += query[2][::-1]
      else:
        forward = query[2] + forward
    else:
      if reverse:
        forward = query[2][::-1] + forward
      else:
        backward += query[2]

if reverse:
  print(backward[::-1] + s[::-1] + forward[::-1])
else:
  print(forward + s + backward)
### BUGGY CODE ###

N,W=map(int,input().split())
dp=[0]*(W+1)
for _ in range(N):
    w,v=map(int,input().split())
    for i in range(W,w-1,-1):
        dp[i]=max(dp[i],dp[i-w]+v)
print(dp[W])

### FIXED CODE ###

def opt(N,W):
    dp=[0]*(W+1)
    for _ in range(N):
        w,v=map(int,input().split())
        for i in range(W,w-1,-1):
            tmp=dp[i-w]+v
            if tmp>dp[i]:
                dp[i]=tmp
    print(dp[W])

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