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

def recur(n,w):
    if n==0 or w==0:
        return 0
    elif (n,w) in dp:
        return dp[(n,w)]
    elif l[n-1][0]<=w:
        k=max(recur(n-1,w-l[n-1][0])+l[n-1][1],recur(n-1,w))
        dp[(n,w)]=k
        return k
    else:
        k=recur(n-1,w)
        dp[(n,w)]=k
        return k
n,w=map(int,input().split())
l=[]
for _ in range(n):
    a,b=map(int,input().split())
    l.append((a,b))
dp=dict()
print(recur(n,w))
    

### FIXED CODE ###

n,w=map(int,input().split())
l=[]
weight=[0]
value=[0]

for _ in range(n):
    a,b=map(int,input().split())
    value.append(b)
    weight.append(a)
maxvalue=sum(value)
dp=[[10**10 for i in range(maxvalue+1)]for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(1,n+1):
    for j in range(1,maxvalue+1):
        if value[i]<=j:
            
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-value[i]]+weight[i])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(maxvalue+1):
    if dp[-1][i]<=w:
        ans=i
print(ans)
### BUGGY CODE ###

a, b = map(int, input().split())
y = []
p = 0

for i in range(1, 1000):
    p += i
    y.append(p)

for x in range(1, 499501):
    for i in range(1, 999):
        if y[i] == b + x and y[i - 1] == a + x:
            print(x)
            break
    else:  # 内側のforのelse節は内側ループが全部まわり切ったら実行される、つまり前の行のbreakで抜けた場合ここは実行されない
        continue  # 外側のforに対応するcontinue文、ここが実行されたら次の行のbreakには処理がいかず、外側のforの次のループにジャンプする
    break  # 外側のforを抜ける"

### FIXED CODE ###

a, b = map(int, input().split())
y = []
p = 0

for i in range(1, 1000):
    p += i
    y.append(p)
    
c = b - a
for i in range(1, 999):
    if y[i] - y[i - 1] == c:
        print(y[i] - b)
        break
### BUGGY CODE ###


S = input()
Q = int(input())

for i in range(Q):
    q = list(input().split())

    if (len(q) == 1):
        S = S[::-1]
    else:
        judge = q[1]
        cha = q[2]
        
        if (int(judge) == 1):
            S = cha + S
        else:
            S = S + cha

print(S)



### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())
reverse = 1


for i in range(Q):
    
    q = input()
    
    if (q == '1'):
        reverse *= -1
    else:
        integer, judge, cha = q.split()
        
        if (judge == '1'):
            if (reverse == 1):
                S.appendleft(cha)
            else:
                S.append(cha)
        
        elif (judge == '2'):
            if (reverse == 1):
                S.append(cha)
            else:
                S.appendleft(cha)

if (reverse == -1):
    S.reverse()

print(''.join(list(S)))
### BUGGY CODE ###

#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7


def main():
    N = II()
    target = LI()

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans += (target[i] % MOD) * (target[j] % MOD) % MOD
            ans = ans % MOD
    print(ans)


main()


### FIXED CODE ###

#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7


def main():
    N = II()
    target = LI()

    ans = 0
    sums = [0] * N
    sum_all = target[0]
    sums[0] = target[0]
    for i in range(1, N):
        sum_all += target[i] % MOD
        sums[i] = sums[i-1] + target[i]

    for i in range(N):
        ans += target[i] * (sum_all - sums[i])
        ans = ans % MOD

    print(ans)


main()
### BUGGY CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
H, W = map(int, input().split())
A, B = [None] * H, [None] * H
for i in range(H):
    A[i] = list(map(int, input().split()))
for i in range(H):
    B[i] = list(map(int, input().split()))
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
M = 80*(80+80)
dp = [[defaultdict(lambda :False) for j in range(W+1)] for i in range(H+1)]
dp[0][1][0] = True
dp[1][0][0] = True
for i in range(1, H+1):
    for j in range(1, W+1):
        d = C[i-1][j-1]
        for k in range((i+j-1)*80):
            if dp[i-1][j][abs(k-d)] or dp[i-1][j][k+d] or dp[i][j-1][abs(k-d)] or dp[i][j-1][k+d]:
                dp[i][j][k] = True

for i in range(M):
    if i in dp[H][W]:
        print(i)
        break


### FIXED CODE ###

import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A, B = [None] * H, [None] * H
for i in range(H):
    A[i] = list(map(int, input().split()))
for i in range(H):
    B[i] = list(map(int, input().split()))
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
M = 80*(80+80)
dp = [[0 for j in range(W+1)] for i in range(H+1)]
dp[0][1] = 1
dp[1][0] = 1
for i in range(1, H+1):
    for j in range(1, W+1):
        d = C[i-1][j-1]
        if d != 0:
            x = int(bin((dp[i-1][j]&(2**d-1))+2**d)[::-1][:d], 2)<<1
            y = int(bin((dp[i][j-1]&(2**d-1))+2**d)[::-1][:d], 2)<<1
        else:
            x=y=0
        #print(bin(dp[i-1][j]), bin(dp[i-1][j]+(2**10)))
        dp[i][j] = (dp[i-1][j] >> d) | (dp[i-1][j] << d) | (dp[i][j-1] >> d) | (dp[i][j-1] << d) | x | y
        #print(i, j, d, bin(dp[i][j]))

for i, v in enumerate(bin(dp[H][W])[::-1]):
    if v == '1':
        print(i)
        break
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [i for i in range(N)]
C = []
for i in range(N):
    C.append([A[i],B[i]])
C = sorted(C,reverse=True)
dp = [[0] * (N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    dp[i][0] = dp[i-1][0] + C[i-1][0]*(-C[i-1][1]+N-i)
    dp[0][i] = dp[0][i-1] + C[i-1][0]*(C[i-1][1]-i+1)
for i in range(1,N+1):
    for j in range(1,N+1):
        if i+j <= N:
            c = C[i+j-1][0]
            d = C[i+j-1][1]
            dp[i][j] = max(dp[i-1][j]+c*(N-i-d),dp[i-1][j]+c*(d+i-N),dp[i][j-1]+c*(j-d-1),dp[i][j-1]+c*(d-j+1))
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
print(dp[N][N])

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [i for i in range(N)]
C = []
for i in range(N):
    C.append([A[i],B[i]])
C = sorted(C,reverse=True)
dp = [[0] * (N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    dp[i][0] = dp[i-1][0] + C[i-1][0]*(-C[i-1][1]+N-i)
    dp[0][i] = dp[0][i-1] + C[i-1][0]*(C[i-1][1]-i+1)
for i in range(1,N+1):
    for j in range(1,N+1):
        if i+j <= N:
            c = C[i+j-1][0]
            d = C[i+j-1][1]
            dp[i][j] = max(dp[i-1][j]+c*abs(N-i-d),dp[i][j-1]+c*abs(j-d-1))
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
print(dp[N][N])
### BUGGY CODE ###

import copy
from datetime import datetime

#print(datetime.now())
n,k = map(int ,input().split())
p = [[0] * (2*k) for i in range(2*k)]
ans = 0
for i in range(n):
  x,y,c = input().split()
  x = int(x)
  y = int(y)
  if c == 'B':
    x += k
  p[x%(2*k)][y%(2*k)] += 1
#[print(p[i]) for i in range(2*k)]
#print()
#print(datetime.now())

csum1 = copy.deepcopy(p)
for i in range(2*k):
    for j in range(1, k):
        csum1[i][0] += p[i][j]
    for j in range(1, 2*k):
        csum1[i][j] = csum1[i][j-1] - p[i][j-1] + p[i][(j+k-1)%(2*k)]
#print(datetime.now())
#[print(csum1[i]) for i in range(2*k)]
#print()

csum2 = copy.deepcopy(csum1)
#print(datetime.now())
for j in range(2*k):
    for i in range(1, k):
        csum2[0][j] += csum1[i][j]
    for i in range(1, 2*k):
        csum2[i][j] = csum2[i-1][j] - csum1[i-1][j] + csum1[(i+k-1)%(2*k)][j]

#[print(csum2[i]) for i in range(2*k)]
#print(datetime.now())
for i in range(2*k):
    for j in range(2*k):
        ans = max(ans, csum2[i][j] + csum2[(i+k)%(2*k)][(j+k)%(2*k)])

print(ans)

### FIXED CODE ###

import copy
from datetime import datetime

#print(datetime.now())
n,k = map(int ,input().split())
p = [[0] * (2*k) for i in range(2*k)]
ans = 0
for i in range(n):
  x,y,c = input().split()
  x = int(x)
  y = int(y)
  if c == 'B':
    x += k
  p[x%(2*k)][y%(2*k)] += 1
#[print(p[i]) for i in range(2*k)]
#print()
#print(datetime.now())

csum1 = [[0]*(2*k) for i in range(2*k)]
#csum1 = copy.deepcopy(p)
for i in range(2*k):
    for j in range(0, k):
        csum1[i][0] += p[i][j]
    for j in range(1, 2*k):
        csum1[i][j] = csum1[i][j-1] - p[i][j-1] + p[i][(j+k-1)%(2*k)]
#print(datetime.now())
#[print(csum1[i]) for i in range(2*k)]
#print()

csum2 = [[0]*(2*k) for i in range(2*k)]
#csum2 = copy.deepcopy(csum1)
#print(datetime.now())
for j in range(2*k):
    for i in range(0, k):
        csum2[0][j] += csum1[i][j]
    for i in range(1, 2*k):
        csum2[i][j] = csum2[i-1][j] - csum1[i-1][j] + csum1[(i+k-1)%(2*k)][j]

#[print(csum2[i]) for i in range(2*k)]
#print(datetime.now())
for i in range(2*k):
    for j in range(2*k):
        ans = max(ans, csum2[i][j] + csum2[(i+k)%(2*k)][(j+k)%(2*k)])

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

n, c, k = map(int, input().split())
l = sorted([int(input()) for i in range(n)])
count = 0
while len(l) > 0:
    check = l[0] + k
    pas = 0
    for i in range(len(l)):
        if (l[i] <= check) and (pas < c):
            pas += 1
    l = l[pas:]
    count += 1
print(count)

### FIXED CODE ###

n, c, k = map(int, input().split())
l = sorted([int(input()) for i in range(n)])
count = 1
pas = 0
now = l[0]
for i in range(len(l)):
    check = now + k
    if pas < c and l[i] <= check:
        pas += 1
    else:
        now = l[i]
        pas = 1
        count += 1
print(count)
### BUGGY CODE ###

n,m=map(int,input().split())
l=sorted([list(map(int,input().split())) for _ in range(n)])
c=[]
for a,b in l:
    for _ in range(b):
        c.append(a)
print(sum(c[:m]))


### FIXED CODE ###

n,m=map(int,input().split())
l=sorted([list(map(int,input().split())) for _ in range(n)])
ans=0
for a,b in l:
    if b<m:
        ans+=(a*b)
        m-=b
    else:
        ans+=(a*m)
        break
print(ans)
### BUGGY CODE ###

N = int(input())
s = [input() for i in range(N)]
count = 0

for i in range(N):
    for k in range(i + 1, N):
        if sorted(s[i]) == sorted(s[k]):
            count += 1
print(count)

### FIXED CODE ###

import collections

N = int(input())
s = [''.join(sorted(input())) for i in range(N)]

count = collections.Counter(s)
ans = 0

for i in count.values():
    ans += i * (i - 1) / 2

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

n=int(input())
a=input().split()
ans=1
for i in range(n):
  ans*=int(a[i])
if ans>1e18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
if 0 in a:
  print(0)
  exit()
ans=1
for i in range(n):
  ans*=a[i]
  if ans>10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
pp = range(1, M // N + 2)
P = max(p for p in pp if M % p == 0 and M // p >= N)
print(P)

### FIXED CODE ###

N, M = map(int, input().split())
candidates = []
for p in range(1, max(int(M ** 0.5) + 1, N + 1)):
    if M % p == 0:
        if M // p >= N:
            # p * (M // p = a1+a2+.. >= N) = M
            candidates.append(p)
        if p >= N:
            # (M // p) * (p = a1+a2+.. >= N) = M
            candidates.append(M // p)
print(max(candidates))
### BUGGY CODE ###

def resolve():
    X = int(input())
    ans = X
    while True:
        count = 0
        for i in range(2, X+1):
            if X%i == 0:
                count += 1
        if count == 0:
            print(ans)
            exit()
        else:
            ans += 1
resolve()

### FIXED CODE ###

def resolve():
    import math
    X = int(input())
    while True:
        count = 0
        for i in range(2, int(math.sqrt(X))):
            if X%i == 0:
                count += 1
                break
        if count == 0:
            print(X)
            exit()
        else:
            X += 1
resolve()
### BUGGY CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
import fractions
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

n = I()
A = LI()

cnt = [0] * n

for i in range(n-1):
    cnt[A[i]-1] = A.count(A[i])

for c in cnt:
  print(c)


### FIXED CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
import fractions
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

n = I()
A = LI()

cnt = [0] * n

sa = set(A)
csa = Counter(A)

for v in sa:
    if cnt[v-1] != 0:
        continue
    cnt[v-1] = csa[v]

for c in cnt:
  print(c)
### BUGGY CODE ###

H,W,M=map(int, input().split())
nrow=[0]*H
ncol=[0]*W
xycoord=[]

for _ in range(M):
	h,w=map(int, input().split())
	nrow[h-1]+=1
	ncol[w-1]+=1
	xycoord+=[[w-1,h-1]]

#ncol=collections.Counter(xcoord)
#nrow=collections.Counter(ycoord)

row_cand=set([i for i, x in enumerate(nrow) if x == max(nrow)])
col_cand=set([i for i, x in enumerate(ncol) if x == max(ncol)])


flag=0
for i in xycoord:
	if (i[0] in col_cand) and (i[1] in row_cand):
		flag+=1

if flag<(len(col_cand)*len(row_cand)):
	print(max(nrow)+max(ncol))
else:
	print(max(nrow)+max(ncol)-1)



# 2darray [[0] * 4 for i in range(3)]
# import itertools

### FIXED CODE ###

H,W,M=map(int, input().split())
nrow=[0]*H
ncol=[0]*W
xycoord=[]

for _ in range(M):
	h,w=map(int, input().split())
	nrow[h-1]+=1
	ncol[w-1]+=1
	xycoord+=[[w-1,h-1]]

#ncol=collections.Counter(xcoord)
#nrow=collections.Counter(ycoord)

a=max(nrow)
b=max(ncol)
row_cand=set([i for i, x in enumerate(nrow) if x == a])
col_cand=set([i for i, x in enumerate(ncol) if x == b])


flag=0
for i in xycoord:
	if (i[0] in col_cand) and (i[1] in row_cand):
		flag+=1

if flag<(len(col_cand)*len(row_cand)):
	print(max(nrow)+max(ncol))
else:
	print(max(nrow)+max(ncol)-1)



# 2darray [[0] * 4 for i in range(3)]
# import itertools
### BUGGY CODE ###

#!/usr/bin/env python3
N, K = map(int, input().split())
A = list(map(int, input().split()))

if K > 41:
    K = 41

for k in range(K):
    D = [0]*N

    for i in range(N):
        left = max(i - A[i], 0)
        right = min(i + A[i], N-1)
        D[left] += 1
        if right + 1 < N: D[right+1] -= 1
    

    for i in range(1, N):
        D[i] += D[i-1]
    A = D


print(' '.join(map(str,A)))

    


### FIXED CODE ###

#!/usr/bin/env python3
N, K = map(int, input().split())
A = list(map(int, input().split()))

if K > 41:
    K = 41

for k in range(K):
    D = [0]*N

    for i in range(N):
        left = max(i - A[i], 0)
        right = min(i + A[i], N-1)
        D[left] += 1
        if right + 1 < N: D[right+1] -= 1
    

    for i in range(1, N):
        D[i] += D[i-1]
    A = D


print(' '.join(map(str,A)))
### BUGGY CODE ###

N, K = list(map(int, input().split()))
if N % K == 0:
	print(0)
else:
	while True:
		N = abs(N - K)
		if abs(N - K) >= N:
			break
	print(N)

### FIXED CODE ###

N, K = list(map(int, input().split()))
ans = min(N % K, K - (N % K))
print(ans)
### BUGGY CODE ###

N = int(input())
g = [[] for _ in range(0,N+1)]
for i in range(0,N-1):
    a,b,c = map(int,input().split())
    g[a].append((b,c))
    g[b].append((a,c))
Q,K = map(int,input().split())
xy = []
for i in range(0,Q):
    x,y = map(int,input().split())
    xy.append((x,y))

#dijkstra
d = [float("inf") for _ in range(0,N+1)]
d[K] = 0
queue = []
queue.append((K,g[K],-1))
while queue:
    start,edge,parent = queue.pop(0)
    for to,cost in edge:
        if to == parent:
            continue
        if d[to] > d[start] + cost:
            d[to] = d[start] + cost
            queue.append((to,g[to],start))

for x,y in xy:
    print(d[x] + d[y])


### FIXED CODE ###

from collections import deque

N = int(input())
g = [[] for _ in range(0,N+1)]
for i in range(0,N-1):
    a,b,c = map(int,input().split())
    g[a].append((b,c))
    g[b].append((a,c))
Q,K = map(int,input().split())
xy = []
for i in range(0,Q):
    x,y = map(int,input().split())
    xy.append((x,y))

d = [-1 for _ in range(0,N+1)]
d[K] = 0
queue = deque([[K,g[K]]])
while queue:
    start,edge = queue.popleft()
    for to,cost in edge:
        if d[to] != -1:
            continue
        d[to] = d[start] + cost
        queue.append((to,g[to]))

for x,y in xy:
    print(d[x] + d[y])
### BUGGY CODE ###

import sys
import itertools

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))

a = ri()
li = rl()
cnt = 0
for lis in list(itertools.combinations(li, 3)):
    max_ = max(lis)
    sum_ = sum(lis)
    if max_ < sum_-max_:
        cnt += 1
print(cnt)

### FIXED CODE ###

import sys

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))

a = ri()
li = sorted(rl(), reverse=True)
cnt = 0
for i in range(a-2):
    for j in range(i+1, a-1):
        left = j+1
        right = a
        lii = li[i]
        lij = li[j]
        if lii >= lij + li[j+1]:
            continue
        while right-left > 1:
            t = (left + right)//2
            lit = li[t]
            if lii < lij + lit:
                left = t
            else:
                right = t
        cnt += left-j
print(cnt)
### BUGGY CODE ###


class Node:
    def __init__(self, key=-1):
        self.key = key
        self.parent = -1
        self.left = -1
        self.right = -1
    
    def setKey(self, key):
        self.key = key


def insert(T, z): #(T, Node)
    y = -1
    x = T[0] #Node()
    while x != -1 :
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y == -1:
        T[0] = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z


def preParse(T):
    if T == -1 and T == -1:
        return
    print T.key,
    preParse(T.left)
    preParse(T.right)

def inParse(T):
    if T == -1 and T == -1:
        return
    inParse(T.left) #Node() or -1
    print T.key,
    inParse(T.right)


T = [-1]

def main():
    com = []
    m = int(raw_input())
    for i in xrange(m):
        com.append(raw_input())
    for i in xrange(m):
        if com[i][0] == 'i':
            insert(T,Node(key=int(com[i][7:])))
        else:
            print '',
            inParse(T[0])
            print
            print '',
            preParse(T[0])
            print 
    return 0

main()
            

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
  
  
class Node(object):
    def __init__(self, key=None):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
  
  
def tree_insert(top, z):
    y = None
    x = top
    while isinstance(x, Node):
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        top = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
    return top
  
  
def inorder_walk(node):
    if node.left:
        inorder_walk(node.left)
    print('', node.key, end='')
    if node.right:
        inorder_walk(node.right)
  
  
def preorder_walk(node):
    print('', node.key, end='')
    if node.left:
        preorder_walk(node.left)
    if node.right:
        preorder_walk(node.right)
  
  
n = int(stdin.readline())
  
top = None
for _ in range(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        key = int(cmd[7:])
        #assert -2000000000 <= key <= 2000000000
        top = tree_insert(top, Node(key))
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()
### BUGGY CODE ###

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

m = {'R': 0, 'G': 0, 'B': 0}

for i, c in enumerate(s):
  if c == 'R':
    m['R'] += 1
  elif c == 'G':
    m['G'] += 1
  else:
    m['B'] += 1

result = m['R'] * m['G'] * m['B']

for i in range(1, n - 1):
  for j in range(i + 1, n):
    k = 2 * j - i

    if k > n or not (s[i - 1] != s[j - 1] and s[j - 1] != s[k - 1] and s[k - 1] != s[i - 1]):
      continue
    result -= 1

print(result)

### FIXED CODE ###

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

m = {'R': 0, 'G': 0, 'B': 0}

for i, c in enumerate(s):
  if c == 'R':
    m['R'] += 1
  elif c == 'G':
    m['G'] += 1
  else:
    m['B'] += 1

result = m['R'] * m['G'] * m['B']

for i in range(1, n - 1):
  for j in range(i + 1, n):
    k = 2 * j - i

    if k > n or not (s[i - 1] != s[j - 1] and s[j - 1] != s[k - 1] and s[k - 1] != s[i - 1]):
      continue
    result -= 1

print(result)
### BUGGY CODE ###

def solve():
    INF = 10**12

    def max2(x, y): return x if x >= y else y
    def min2(x, y): return x if x <= y else y

    N, K = map(int, input().split())
    Hs = [0] + list(map(int, input().split()))

    dp = [[INF]*(N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(1, N+1):
        H = Hs[i]
        diffs = []
        for iPrev in range(i):
            diff = max2(0, H-Hs[iPrev])
            diffs.append(diff)
        dp[i][0] = 0
        dp[i][1] = H
        for j in range(2, min(i, N-K)+1):
            for iPrev in range(i):
                dp[i][j] = min2(dp[i][j], dp[iPrev][j-1]+diffs[iPrev])

    ans = min(dpi[N-K] for dpi in dp)
    print(ans)


solve()


### FIXED CODE ###

def solve():
    INF = float('inf')

    def max2(x, y): return x if x >= y else y

    N, K = map(int, input().split())
    Hs = [0] + list(map(int, input().split()))

    if N == K:
        return 0

    dp = [INF] * (N+1)
    dp[0] = 0
    for j in range(1, N-K+1):
        dp2 = [INF] * (N+1)
        for i, H in enumerate(Hs[j:], j):
            for k in range(j-1, i):
                dp2[i] = min(dp2[i], dp[k] + max2(0, H-Hs[k]))
        dp = dp2

    return min(dp)

ans = solve()
print(ans)
### BUGGY CODE ###

def solve(n, hhh, aaa):
    n2 = 1 << n.bit_length()
    offset = n2 - 1
    data = [0] * ((n2 << 1) - 1)

    def update(k, x):
        i = k + offset
        data[i] = max(data[i], x)
        while i:
            i = (i - 1) // 2
            data[i] = max(data[i], x)

    def get_max(a, b, i=0, l=0, r=n2):
        if b <= l or r <= a:
            return 0

        if a <= l and r <= b:
            return data[i]

        m = (l + r) // 2
        li = (i << 1) + 1
        return max(get_max(a, b, li, l, m), get_max(a, b, li + 1, m, r))

    srt = sorted((h, i) for i, h in enumerate(hhh))
    for h, i in srt:
        update(i, get_max(0, i) + aaa[i])

    return get_max(0, n2)


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
print(solve(n, hhh, aaa))


### FIXED CODE ###

def solve(n, hhh, aaa):
    n2 = 1 << n.bit_length()
    offset = n2 - 1
    data = [0] * ((n2 << 1) - 1)

    def update(k, x):
        i = k + offset
        data[i] = max(data[i], x)
        while i:
            i = (i - 1) // 2
            data[i] = max(data[i], x)

    def get_max(k):
        i = k + offset
        ret = data[i]
        while i:
            if i % 2 == 0:
                ret = max(ret, data[i - 1])
            i = (i - 1) // 2
        return ret

    srt = sorted((h, i) for i, h in enumerate(hhh))
    for h, i in srt:
        update(i, get_max(i) + aaa[i])

    return data[0]


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
print(solve(n, hhh, aaa))