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

# 2019-11-21 01:26:03(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r, insort_left as in_l
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 

def is_palindrome_in(s):
    s = s.replace('x', '')
    if list(s) == list(reversed(s)):
        return True
    return False

def main():
    s = sys.stdin.readline().rstrip()
    
    if not is_palindrome_in(s):
        print(-1)
        sys.exit()
    
    s = list(s)
    # deque で insertが使えるのがver3.5以降のようです(AtCoder はver3.4)
    # 初めdequeでやっててなぜRuntime Errorになるのか全くわからなかった
    # でもこれだとTLEになってしまうかもしれません

    count = 0
    i, j = 0, 0
    while i < len(s) - 1 - j:
        if s[i] == 'x':
            if s[-1-j] != 'x':
                s.insert(len(s)-j, 'x')
                count += 1
        elif s[-1-j] == 'x':
            s.insert(i, 'x')
            count += 1
        
        i += 1
        j += 1

    print(count)
    

if __name__ == "__main__":
    main()


### FIXED CODE ###

# 2019-11-21 01:26:03(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r, insort_left as in_l
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 

def is_palindrome_in(s):
    s = s.replace('x', '')
    if list(s) == list(reversed(s)):
        return True
    return False

def main():
    s = sys.stdin.readline().rstrip()
    
    if not is_palindrome_in(s):
        print(-1)
        sys.exit()
    
    s = collections.deque(s)
    
    count = 0
    while len(s) > 1:
        if s[0] == 'x':
            if s[-1] == 'x':
                s.popleft(); s.pop()
            else:
                s.popleft()
                count += 1
        else:
            if s[-1] != 'x':
                s.popleft(); s.pop()
            else:
                s.pop()
                count += 1

    print(count)

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

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

for x in range(len(a)):
    if x==a.index(max(a)):
            print(sorted(a)[-2])
    else:
            print(max(a))


### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
Max=max(a)
Second=sorted(a)[-2]
Index=a.index(Second)
[print(Max) if i!=Max else print(Second) for i in a]
### BUGGY CODE ###

def main():
    x,y = map(int,input().split())
    tmp = []
    for i in range(2,max(2,min(int(x // 2), int(y // 2 )))):
        if x % i ==0 and y % i == 0:
            tmp.append(i)
            while True:
                if x % i == 0:
                    x = x//i
                else:
                    break
            while True:
                if y % i == 0:
                    y = y//i
                else:
                    break


    print(len(tmp) + 1)
    # print(tmp)
    # for i,a in enumerate(tmp):
    #     if a < 4:
    #         tmp[i] = 1
    #         continue
    #     j = 2
    #     for j in range(2,int(a**0.5)+1):
    #         if a % j == 0:
    #             tmp[i] = 0
    #             break
    #     if tmp[i] != 0:
    #         tmp[i] = 1
    # print(sum(tmp))
    # print(tmp)

    # cnt = 0
    # # print(tmp)
    # flg = 0
    # for i,a in enumerate(tmp):
    #     # print('out' + str(i) + ' ' + str(a))
    #     if a == 1:
    #         continue
    #     leng = len(tmp)
    #     for j in range(i+1,leng):
    #         # print(j)
    #         # print(tmp)
    #         # print(leng)
    #         if flg == 1:
    #             j -=1
    #         flg = 0
    #         if j >= leng:
    #             break
    #         # print(str(j) + ' ' + str(leng) + ' ' + str(tmp[j]))
    #         if tmp[j] % a == 0:
    #             tmp.pop(j)
    #             leng -=1
    #             j -= 1
    #             # print(tmp)
    #             # print(j)
    #             flg = 1
    #
    #                 # print(j)
    #                 # print(a)
    #

    # print(len(tmp))
    # print(tmp)
if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    x,y = map(int,input().split())
    tmp = [1]
    i = 2
    ans = 0
    # if x == y:
    #     ans += 1
    # a = factorization(x)
    # print(a)
    tempx = x

    for i in range(2, int(-(-x**0.5//1))+1):
        if tempx % i == 0:
            tmp.append(i)
            while tempx % i == 0:

                tempx //= i
    if tempx!=1:
        tmp.append(tempx)
    # print(tmp)

    for i,a in enumerate(tmp):
        if y % a == 0:
            tmp[i] = 1
        else:
            tmp[i] = 0
    print(sum(tmp))


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

#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc123_d
import itertools
import math

# input
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
# getans
arr = itertools.product(A, B)
arr = map(sum, arr)
arr = sorted(arr, reverse=True)[:K]
arr = itertools.product(arr, C)
arr = map(sum, arr)
arr = sorted(arr, reverse=True)[:K]
# output
for a in arr:
    print(a)



### FIXED CODE ###

#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc123_d
import itertools
import math

# input
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
# A = range(1000)
# B = range(1000)
# C = range(1000)
# getans
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
arr = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k+1) > K:
                break
            arr.append(A[i]+B[j]+C[k])
#print(len(arr))
arr.sort(reverse=True)
# output
ans = '\n'.join(map(str, arr[:K]))
print(ans)
### BUGGY CODE ###

n=int(input())
commands=[input().split() for i in range(n)]
    
List=[]
def command(list_command):
    global List
    if 'insert' in list_command:
        List.insert(0,list_command[1])
    elif 'delete' in list_command:
        try:
            t=List.index(list_command[1])
            del List[t]
        except:
            pass
    elif 'deleteFirst' in list_command:
        del List[0]
    elif 'deleteLast' in list_command:
        del List[-1]
    return True
    
for i in commands:
    command(i)
print(*List)

### FIXED CODE ###

from collections import deque
n=int(input())
commands=[input().split() for i in range(n)]
    
List=deque()
for list_command in commands:
    if 'insert' in list_command:
        List.appendleft(list_command[1])
    elif 'delete' in list_command:
        try:
            List.remove(list_command[1])
        except:
            pass
    elif 'deleteFirst' in list_command:
        List.popleft()
    elif 'deleteLast' in list_command:
        List.pop()
  
print(*List)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
 
def divisor(N):
    from math import sqrt
    D = []
    for i in range(1, int(sqrt(N)) + 1):
        if N % i == 0:
          D.append(i)
          D.append(N // i)
 
    return list(set(D))
 
 
count = 0
A_set = set(A)
A_dict = {a: 0 for a in A}
for a in A:
    A_dict[a] += 1
    
for a in A:
    a_div = set(divisor(a)) - {a}
    if len(a_div - A_set) == len(a_div):
        if A_dict[a] == 1:
            count += 1
 
print(count)

### FIXED CODE ###

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

A_max = max(A)
dp = [True] * (A_max + 1)
count = 0
A_f = {a: 0 for a in A}
for a in A:
    A_f[a] += 1

for a in A:
    if dp[a]:
        for i in range(1, A_max + 1):
            if a * i > A_max:
                break
            dp[a * i] = False
        if A_f[a] == 1:
            count += 1

print(count)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list([int(input()) for i in range(M)])

current_step, prev_step, two_prev_step = 0, 1, 0
for i in reversed(range(N)):
    if i in A:
        prev_step, two_prev_step = 0, prev_step
        continue

    current_step = prev_step + two_prev_step
    prev_step, two_prev_step = current_step, prev_step

print(current_step % 1000000007)

### FIXED CODE ###

import sys
max_num = 1000000007
input = sys.stdin.readline
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

stairs = [1] * (N+1)
for i in A:
    stairs[i] = 0

for i in range(1, N):
    if stairs[i+1] != 0:
        stairs[i+1] = stairs[i] + stairs[i-1]
print(stairs[N] % max_num)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    i = str(i).zfill(3)
    c = 0
    for j in range(N):
        if S[j] == i[c]:
            c += 1
        
        if c == 3:
            ans += 1
            break

print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    i = str(i).zfill(3)
    c = 0
    for j in range(N):
        if S[j] == i[c]:
            c += 1
        
        if c == 3:
            ans += 1
            break

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

N,D,A = map(int,input().split())
import numpy as np
import math
XH = [list(map(int,input().split())) for _ in range(N)]
XH = sorted(XH)
ans = 0
l=[0]*N
x = XH[0][0]
left = 0
right = N
while left+1!=right:
  mid = (right+left)//2
  if XH[mid][0]<=x+2*D:
    left = mid
  else:
    right = mid
l[0]=left
for i in range(1,N):
  x = XH[i][0]
  right = N
  left = l[i-1]
  while left+1!=right:
    mid = (right+left)//2
    if XH[mid][0]<=x+2*D:
      left = mid
    else:
      right = mid
  l[i]=left
H = np.array([xh[1] for xh in XH])
for i,a in enumerate(l):
  h = H[i]
  if h<=0:
    continue
  else:
    b = math.ceil(h/A)
    ans += b
    H[i:a+1:]-=b*A
print(ans)

### FIXED CODE ###

def main():
  N,D,A = map(int,input().split())
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  S = [0]*(N+1)
  x = XH[0][0]
  h = XH[0][1]
  j = 0
  b = (h+A-1)//A
  ans += b
  y = b*A
  while True:
    if j+1>=N:
      break
    if XH[j+1][0]<=x+2*D:
      j+=1
    else:
      break
  S[0]+=y
  S[j+1]-=y
  S[1]+=S[0]
  for i in range(1,N):
    xh = XH[i]
    h = xh[1]
    s = S[i]
    rec = h-s
    if rec<=0:
      S[i+1]+=s
      continue
    else:
      x = xh[0]
      j = max(j,i)
      while True:
        if j+1>=N:
          break
        if XH[j+1][0]<=x+2*D:
          j+=1
        else:
          break
      b = (rec+A-1)//A
      ans += b
      y = b*A
      S[i]+=y
      S[j+1]-=y
      S[i+1]+=s+y
  print(ans)
main()
### BUGGY CODE ###

import numpy as np
from sys import stdin

N, S = map(int, stdin.readline().split())
A = list(map(int, stdin.readline().split()))
M = 998244353
V = max(max(A), S)

ans = 0
cs = np.zeros(V + 1, dtype=np.int64)
for i, a in enumerate(A):
    dp = np.zeros(V + 1, dtype=np.int64)
    dp[a] = i + 1
    for s in range(a + 1, S + 1):
        dp[s] = cs[s - a]
    cs = (cs + dp) % M
    ans = (ans + (N - i) * dp[S]) % M
print(ans)

### FIXED CODE ###

from sys import stdin

N, S = map(int, stdin.readline().split())
A = list(map(int,stdin.readline().split()))
M = 998244353
V = max(max(A), S)

ans = 0
cs = [0 for _ in range(V + 1)]
for i, a in enumerate(A):
    dp = [0 for _ in range(V + 1)]
    dp[a] = i + 1
    for s in range(a + 1, S + 1):
        dp[s] = cs[s - a]
    cs = [(a + b) % M for a, b in zip(cs, dp)]
    ans = (ans + (N - i) * dp[S]) % M
print(ans)
### BUGGY CODE ###

def search(l, n):
    l = l.copy()
    l.append(n)
    i = 0
    while l[i] != n:
        i += 1

    if i == len(l) - 1:
        print("NOT FOUND")
    else:
        print("FOUND")


n = int(input())
s = [int(i) for i in input().split()]
q = int(input())
t = [int(i) for i in input().split()]

ans = 0
for ti in t:
    if ti in s:
        ans += 1

print(ans)


### FIXED CODE ###

def search(l, n):
    left = 0
    right = len(l) - 1
    while right - left > 1:
        m = (left + right) // 2
        if n == l[m]:
            return True
        elif n < l[m]:
            right = m
        else:
            left = m

    # print(left, right)
    if l[left] == n or l[right] == n:
        return True
    else:
        return False


n = int(input())
s = [int(i) for i in input().split()]
q = int(input())
t = [int(i) for i in input().split()]

ans = 0
for ti in t:
    if search(s, ti):
        ans += 1

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

from collections import deque

s=input()
q=int(input())

R=True
ans=deque(list(s))
count=0

for i in range(q):
    l=list(map(str,input().split()))
    if int(l[0])==1:
        if R:
            R=False
        else:
            R=True
        count+=1
    else:
        f,c=int(l[1]),l[2]
        if f==1 and R:
            ans.appendleft(c)
        elif f==2 and R:
            ans.append(c)
        elif f==1 and (not R):
            ans.append(c)
        elif f==2 and (not R):
            ans.appendleft(c)

string=""
if count%2==0:
    for i in range(len(ans)):
        string+=ans[i]
else:
    for i in range(len(ans))[::-1]:
        string+=ans[i]
print(string)

### FIXED CODE ###

from collections import deque

s=input()
q=int(input())

R=True
ans=deque(list(s))
count=0
for i in range(q):
    l=list(map(str,input().split()))
    if int(l[0])==1:
        if R:
            R=False
        else:
            R=True
        count+=1
    else:
        f,c=int(l[1]),l[2]
        if f==1 and R:
            ans.appendleft(c)
        elif f==2 and R:
            ans.append(c)
        elif f==1 and (not R):
            ans.append(c)
        elif f==2 and (not R):
            ans.appendleft(c)

if count%2==0:
    print(''.join(ans))
else:
    print(''.join(reversed(ans)))
### BUGGY CODE ###

N = int(input())

def num_divisors_table(n):
    table = [0] * (n + 1)   
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
        table[i] *= i   
    return table

ans = num_divisors_table(N)
#print(ans)
print(sum(ans))

### FIXED CODE ###

n = int(input())

def div(n):
    a = 0
    for i in range(1, n+1):
        y = int(n/i)
        a += y* (y+1)*i/2
    return int(a)
    
print(div(n))
### BUGGY CODE ###


N = int(input())
TA = [list(map(int,input().split())) for _ in range(N)]

lcms = TA[0]

for t,a in TA[1:]:
    tmp = [t,a]
    
    while tmp[0] < lcms[0]:
        tmp[0] += t
        tmp[1] += a
    while tmp[1] < lcms[1]:
        tmp[0] += t
        tmp[1] += a
    lcms = tmp

print(sum(lcms))


### FIXED CODE ###


N = int(input())
TA = [list(map(int,input().split())) for _ in range(N)]

lcms = TA[0]

for t,a in TA[1:]:
    tmp = [t,a]

    
    m1 = (lcms[0]+tmp[0]-1)//tmp[0]
    m2 = (lcms[1]+tmp[1]-1)//tmp[1]
    
    m = max(m1,m2)
    if m != 0:
        tmp[0] *= m
        tmp[1] *= m
    lcms = tmp

print(sum(lcms))
### BUGGY CODE ###

def road(n):
  for _ in range(n):
    A,B = map(int,input().split())
    yield A,B
  
def main():
  N,M = map(int,input().split())
  h = list(map(int,input().split()))
  num = list(range(1,N+1))
  X = list(road(M))
  for A,B in X:
    if A in num and B in num:
      if h[A-1] > h[B-1] and B in num:
        num.remove(B)
      elif h[A-1] < h[B-1] and A in num:
        num.remove(A)
      elif h[A-1] == h[B-1]:
        if A in num and B in num:
          num.remove(A)
          num.remove(B)
    elif A in num:
      if h[A-1] < h[B-1]:
        num.remove(A)
      elif h[A-1] == h[B-1]:
          num.remove(A)
    elif B in num:
      if h[A-1] > h[B-1]:
        num.remove(B)
      elif h[A-1] == h[B-1]:
          num.remove(B)
  return len(num)

print(main())

### FIXED CODE ###

n,m = map(int,input().split())
h = list(map(int,input().split()))
cnt = [0]*n
chk = [0]*n
ans = 0

for i in range(m):
  a,b = map(int, input().split())
  if h[a-1] > h[b-1]:
    cnt[a-1] += 1
  elif h[a-1] < h[b-1]:
    cnt[b-1] += 1
  chk[a-1] += 1
  chk[b-1] += 1
  
for i in range(n):
  if cnt[i] == chk[i]:
    ans += 1
    
print(ans)
### BUGGY CODE ###

import numpy as np

n =	int(input())
nums = [int(input()) for i in range(n)]

for idx, el in enumerate(nums):
	del nums[idx]
	print(np.max(nums))
	nums.insert(idx, el)



### FIXED CODE ###

import numpy as np

n =	int(input())
nums = [int(input()) for i in range(n)]

num_max = np.max(nums)
next_max = sorted(nums)[-2]


for idx, el in enumerate(nums):
	if num_max == el:
		print(next_max)		
	else:
		print(num_max)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
ans=1
p=[a[0]]
import bisect
for i in range(1,n):
    index = bisect.bisect_left(p,a[i]) 
    if index==0:
        ans+=1
        p.insert(index,a[i])
    else:
        p.insert(index,a[i])
        del p[index-1]
print(ans)

### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(-int(input()))
dp=[10**10 for i in range(n+1)]
import bisect
for i in a:
    idx=bisect.bisect_right(dp,i)
    dp[idx]=i

ans=bisect.bisect_left(dp,10**10)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

H,W=map(int,input().split())
c=[input() for _ in range(H)]
H-=1
W-=1

def permutations(L):
    
    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutations(data):
                ret.append([i] + j)

        return ret
        
junretsu = permutations([0]*W+[1]*H)

ans=10**10
for i in junretsu:
    h=0
    w=0
    now=0
    for g in i:
        if g==0:
            w+=1
            if c[h][w]=="#":
                now+=1
        if g==1:
            h+=1
            if c[h][w]=="#":
                now+=1
    ans=min(ans,now)

if c[0][0]=="#":
    ans+=1

print(ans)

### FIXED CODE ###

from collections import defaultdict
import queue

H, W = map(int, input().split())
c = [list(input()) for _ in range(H)]

inf = float("inf")
dp = [[inf]*W for _ in range(H)]
if c[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

n = dp[0][0]
for i in range(H-1):
    if c[i][0] == "." and c[i+1][0] == "#":
        n += 1
    dp[i+1][0] = n

m = dp[0][0]
for i in range(W-1):
    if c[0][i] == "." and c[0][i+1] == "#":
        m += 1
    dp[0][i+1] = m

for i in range(1, H):
    for g in range(1, W):
        if c[i-1][g] == "." and c[i][g] == "#":
            dp[i][g] = min(dp[i-1][g]+1, dp[i][g])
        else:
            dp[i][g] = min(dp[i-1][g], dp[i][g])

        if c[i][g-1] == "." and c[i][g] == "#":
            dp[i][g] = min(dp[i][g-1]+1, dp[i][g])
        else:
            dp[i][g] = min(dp[i][g-1], dp[i][g])

print(dp[H-1][W-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
output = []

for i in range(1, n + 1):
    output.append(a.index(i) + 1)

print(*output)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
output = [0] * n
for i, a in enumerate(a):
  output[a - 1] = i + 1
  
print(*output)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
list = [0]*q

for i in range(q):
    start,end = map(int, input().split())
    list[i] = s.count("AC", start-1, end)

for i in list:
    print(i)



### FIXED CODE ###

n, q = map(int, input().split())
s = input()
x = [0]*(n+1)

for i in range(n):
    x[i+1] = x[i] + (1 if s[i:i+2] == "AC" else 0)

for i in range(q):
    l, r = map(int, input().split())
    print(x[r-1] - x[l-1])
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0
while S:
    Z = [0] * N
    i = 1
    j = 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1

        Z[i] = j

        if j == 0:
            i += 1
        else:
            k = 1
            while k < j and k + Z[k] < j:
                Z[i + k] = Z[k]
                k += 1
            i += k
            j -= k    

    ans = max(ans, max(min(i, z) for i, z in enumerate(Z)))

    S = S[1:]
    N -= 1

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

ans = 0
while S:
    Z = [0] * N
    i = 1
    j = 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1

        Z[i] = j

        if j == 0:
            i += 1
        else:
            k = 1
            while k < j and k + Z[k] < j:
                Z[i + k] = Z[k]
                k += 1
            i += k
            j -= k    

    ans = max(ans, max(min(i, z) for i, z in enumerate(Z)))

    S = S[1:]
    N -= 1

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

n=int(input())

ans=0
arr=[]

for i in range(n):

    a=int(input())

    if a in arr:
        
        ans-=1
        arr.remove(a)

    else:

        ans+=1
        arr.append(a)


print(ans)

### FIXED CODE ###

import collections

n=int(input())

arr=[]

for i in range(n):

    a=int(input())
    arr.append(a)

c = collections.Counter(arr)

ans=0

for j in c.values():
    if j % 2 != 0:
        ans += 1

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

N = int(input())
List = tuple(map(int,input().split()))
counter=0
for i in range(N):
  if min(List[0:i+1])==List[i]:
    counter=counter+1
      
print(counter)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
cnt=0
min_num=p[0]
for i in p:
    if i<=min_num:
        min_num=i
        cnt+=1
print(cnt)
### BUGGY CODE ###

# D - Knapsack 1
N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)

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

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

### FIXED CODE ###

# D - Knapsack 1 Educational DP Contest / DP
import numpy as np

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

dp = np.zeros(W+1, dtype=np.int64)
for _ in range(N):
    w,v = map(int,input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])

ans = dp.max()
print(ans)