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

def main():
    t = input()
    n = len(t)
    dp = [0, 0]
    DP = ["", ""]
    for i in range(n):
        dp2 = [0, 0]
        DP2 = ["", ""]
        if t[i] == "P":
            if dp[0] > dp[1]:
                dp2[0] = dp[0]
                DP2[0] = DP[0]+"P"
            else:
                dp2[0] = dp[1]
                DP2[0] = DP[1]+"P"
        elif t[i] == "D":
            if dp[0]+2 >= dp[1]+1:
                dp2[1] = dp[0]+2
                DP2[1] = DP[0]+"D"
            else:
                dp2[1] = dp[1]+1
                DP2[1] = DP[1]+"D"
        else:
            if dp[0] > dp[1]:
                dp2[0] = dp[0]
                DP2[0] = DP[0]+"P"
            else:
                dp2[0] = dp[1]
                DP2[0] = DP[1]+"P"
            if dp[0]+2 >= dp[1]+1:
                dp2[1] = dp[0]+2
                DP2[1] = DP[0]+"D"
            else:
                dp2[1] = dp[1]+1
                DP2[1] = DP[1]+"D"
        dp = dp2
        DP = DP2
    if dp[0] >= dp[1]:
        print(DP[0])
    else:
        print(DP[1])


main()

### FIXED CODE ###

def main():
    t = input()
    n = len(t)
    ans = ""
    for i in range(n):
        if t[i] == "?":
            ans += "D"
        else:
            ans += t[i]
    print(ans)


main()
### BUGGY CODE ###

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

ans=[]

for i in range(1,N+1):
    ans.append(int(1+A.index(i)))


print(*ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=[0]*N
for i in range(0,N):
  ans[A[i]-1]=i+1
print(*ans)
### BUGGY CODE ###

[l,r] = [int(i) for i in input().split()]

ans = []
if l+1 == r:
	print(l*r%2019)

else:
	for i in range(l,r):
		for j in range(1,r-i+1):
			rem = i*(i+j)%2019
			ans.append(rem)

	print(min(ans))	

### FIXED CODE ###

L, R = list(map(int, input().split(' ')))
#print(L, R)
 
min = 2019
for i in range(L, R):
    for j in range(i + 1, R + 1):
        mod_ij = (i * j) % 2019
        if min > mod_ij:
            min = mod_ij
            if min == 0:
                break
    if min == 0:
        break
print(min)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6+32)
mod=10**9+7
input=sys.stdin.buffer.readline
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[ [0 for _ in range(m)] for _ in range(n)]
for i in range(0,n):
    for j in range(0,m):
        ret=0
        if i-1>=0:
            ret+=dp[i-1][j]
        if j-1>=0:
            ret+=dp[i][j-1]
        if i-1>=0 and j-1>=0:
            ret-=dp[i-1][j-1]
        if s[i]==t[j]:
            ret+=1
            if i-1>=0 and j-1>=0:
                ret+=dp[i-1][j-1]
        ret%=mod
        if ret<0:
            ret+=mod
        dp[i][j]=ret
print((dp[n-1][m-1]+1)%mod)



### FIXED CODE ###

import sys
mod=10**9+7
input=sys.stdin.buffer.readline
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[ [0 for _ in range(m)] for _ in range(n)]
for i in range(0,n):
    for j in range(0,m):
        ret=0
        if i-1>=0:
            ret+=dp[i-1][j]
        if j-1>=0:
            ret+=dp[i][j-1]
        if i-1>=0 and j-1>=0:
            ret-=dp[i-1][j-1]
        if s[i]==t[j]:
            ret+=1
            if i-1>=0 and j-1>=0:
                ret+=dp[i-1][j-1]
        if ret>=mod:
            ret%=mod
        if ret<0:
            ret+=mod
        dp[i][j]=ret
print((dp[n-1][m-1]+1))
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = map(int, input().split())
uf = UnionFind(n)

for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

ans = 0
for l in list(uf.all_group_members().values()):
    ans = max(ans, len(l))

print(ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n=0):
        self.d = [-1]*n
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.d[self.find(x)]


n, m = map(int, input().split())
uf = UnionFind(n)

for _ in range(m):
    a, b = map(int, input().split())
    uf.unite(a-1, b-1)

ans = 0
for i in range(n):
    ans = max(ans, uf.size(i))

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

import networkx as nx
room, route_count = map(int,input().split())
route = [list(map(int,input().split())) for _ in range(route_count)]

G = nx.Graph()
G.add_nodes_from(range(1,room+1))
G.add_edges_from(route)
shortest_path_dict = nx.single_target_shortest_path(G, target=1)
if len(shortest_path_dict)<room:
  print('No')
else:
  print('Yes')
  for i in range(2,room+1):
    print(shortest_path_dict[i][1])


### FIXED CODE ###

import networkx as nx
room, route_count = map(int,input().split())
route = [list(map(int,input().split())) for _ in range(route_count)]

G = nx.Graph()
G.add_nodes_from(range(1,room+1))
G.add_edges_from(route)
pre = nx.predecessor(G, 1)

print('Yes')
for i in range(2,room+1):
  print(pre[i][0])
### BUGGY CODE ###

from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,k = readInts()
a = readInts()

base = 1
for i in range(k):
	base*=a[i]
t = base
#print(t)
base = base//a[0]

for i in range(k,n):
	base*=a[i]
	#print(base)
	if t>=base:
		print("No")
	else:
		print("Yes")
	t = base
	base=base//a[i-k+1]


### FIXED CODE ###

from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,k = readInts()
a = readInts()


t = a[0]

for i in range(k,n):
	be = a[i-k]
	af = a[i]
	#print(base)
	if be>=af:
		print("No")
	else:
		print("Yes")
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
for a in A:
  ans*=a
if ans > 10**18:
  ans=-1
print(ans)

### FIXED CODE ###

def main():
  N=int(input())
  A=list(map(int,input().split()))
  A.sort(reverse=True)
  ans=1
  if A[-1]!=0:
    for a in A:
      ans*=a
      if ans > 10**18:
        ans=-1
        break
  else:ans=0
  print(ans)
if __name__ == '__main__':
  main()
### BUGGY CODE ###

N = int(input())
X = list(map(int,input().split()))
sX = sorted(X)
tsX = sX[:]
k = int(N/2-1)
for i in range(N):
    tsX.remove(X[i])
    print(tsX[k])
    tsX = sX[:]


### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
sX = sorted(X)
m1 = sX[int(N/2-1)]
m2 = sX[int(N/2)]
for i in X:
    if i<=m1:
        print(m2)
    else:
        print(m1)
### BUGGY CODE ###

from collections import deque
N, M, P = map(int, input().split())
G = [[] for i in range(N)]
RG = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, P-c))
    RG[b-1].append((a-1, P-c))

def chk(s, G):
    P = [0]*N
    que = deque([s])
    used = [0]*N
    used[s] = 1
    while que:
        v = que.popleft()
        P[v] = 1
        for w, c in G[v]:
            if used[w]:
                continue
            que.append(w)
            used[w] = 1
    return P
P0 = chk(0, G); P1 = chk(N-1, RG)
I = []
for i in range(N):
    if P0[i] == P1[i] == 1:
        I.append(i)

dist = [10**18]*N
dist[0] = 0
L = len(I)
for i in range(L+1):
    update = 0
    for v in I:
        d = dist[v]
        for w, c in G[v]:
            if d + c < dist[w]:
                dist[w] = d + c
                update = 1
    if not update:
        break
else:
    print("-1")
    exit(0)

print(max(-dist[N-1], 0))

### FIXED CODE ###

from collections import deque
N, M, P = map(int, input().split())
G = [[] for i in range(N)]
RG = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, P-c))
    RG[b-1].append((a-1, P-c))

def chk(s, G):
    P = [0]*N
    que = deque([s])
    used = [0]*N
    used[s] = 1
    while que:
        v = que.popleft()
        P[v] = 1
        for w, c in G[v]:
            if used[w]:
                continue
            que.append(w)
            used[w] = 1
    return P
P0 = chk(0, G); P1 = chk(N-1, RG)
I = [i for i in range(N) if P0[i] == P1[i] == 1]

dist = [10**18]*N
dist[0] = 0
L = len(I)
for i in range(L+1):
    update = 0
    for v in I:
        d = dist[v]
        for w, c in G[v]:
            if d + c < dist[w]:
                dist[w] = d + c
                update = 1
    if not update:
        break
else:
    print("-1")
    exit(0)

print(max(-dist[N-1], 0))
### BUGGY CODE ###

import re
n, q = [int(i) for i in input().split()]
S = input()
for _ in range(q):
    l, r = [int(i) for i in input().split()]
    s = S[l-1:r]
    ans = sum(True for _ in re.findall('AC', s))
    print(ans)

### FIXED CODE ###

n, q = [int(i) for i in input().split()]
S = input()
counter = [0] * len(S)
for i in range(len(S)):
    if i == 0:
        counter[i] == 0
    elif S[i-1:i+1] == 'AC':
        counter[i] = counter[i-1] + 1
    else:
        counter[i] = counter[i-1]

counter = [0] + counter
# print(counter)


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

import bisect

Q = int(input())

a = []
a_new = []
b_sum = 0
minima = 0
argmin = 10**10
shift = 0
for i in range(Q):
    ipt = list(map(int, input().split()))
    if len(ipt) == 3:
        if len(a) == 0:
            a.append(ipt[1])
        else:
            a.insert(bisect.bisect_left(a, ipt[1]), ipt[1])
        argmin_new = a[(len(a) - 1) // 2]
        if argmin == 10**10:
            argmin = argmin_new
        minima += abs(ipt[1] - argmin_new) + (abs(argmin - argmin_new)) * ((len(a) + 1) % 2)
        b_sum += ipt[2]
        argmin = argmin_new
    else:
        print(argmin, minima + b_sum)

### FIXED CODE ###

def main():
    import sys
    from heapq import heappop, heappush, heappushpop
    input = sys.stdin.readline

    Q = int(input())
    R = [10**9+1]
    L = [10**9+1]
    Rsum = 0
    Lsum = 0
    NL = 0
    NR = 0
    B = 0
    for _ in range(Q):
        query = input().rstrip('\n')
        if query == '2':
            Lmax = -L[0]
            print(Lmax, Lmax * NL - Lsum + Rsum - Lmax * NR + B)
        else:
            _, a, b = query.split()
            a = int(a)
            b = int(b)
            B += b
            if NL != NR:
                Lmax = -L[0]
                Rmin = R[0]
                if a >= Lmax:
                    heappush(R, a)
                    Rsum += a
                    NR += 1
                else:
                    newR = -heappushpop(L, -a)
                    heappush(R, newR)
                    Rsum += newR
                    Lsum += a - newR
                    NR += 1
                    Lmax = -L[0]
            else:
                Rmin = R[0]
                if a <= Rmin:
                    heappush(L, -a)
                    Lsum += a
                    NL += 1
                else:
                    newL = heappushpop(R, a)
                    heappush(L, -newL)
                    Lsum += newL
                    Rsum += a - newL
                    NL += 1


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

# 2019/08/16

s=list(input())
t=list(input())

c1={}
c2={}
for ss,tt in zip(s,t):
    c1[ss]=c1.get(ss,'')+tt
    c2[tt]=c2.get(tt,'')+ss
    if len(set(c1[ss]))>1 or len(set(c2[tt]))>1:
        print('No')
        exit()

print('Yes')

### FIXED CODE ###

# 2019/08/16

s=list(input())
t=list(input())

c1={}
c2={}
for ss,tt in zip(s,t):
    if c1.get(ss) is None:
        c1[ss]=tt
    if c2.get(tt) is None:
        c2[tt]=ss
    if c1[ss]==tt and c2[tt]==ss:continue
    else:
        print('No')
        exit()

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

n=int(input())
d={}
for k in range(2,10**6):
  while n%k<1: n//k; d[k]=d.get(k,0)+1
a=0
for i in d.values():
  t=c=0
  while t+c<i: c+=1; t+=c
  a+=c
print(a+(n>1))

### FIXED CODE ###

n=int(input())
d={}
for k in range(2,10**6):
  while n%k<1: n//=k; d[k]=d.get(k,0)+1
a=0
for i in d.values():
  t=c=0
  while t+c<i: c+=1; t+=c
  a+=c
print(a+(n>1))
### BUGGY CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

Qs = 3 if S[0] == '?' else 1
A = [0] * N
AB = [0] * N
ABC = [0] * N
if S[0] in 'A?':
    A[0] = 1
for i in range(1, N):
    s = S[i]
    if s == '?':
        A[i] = A[i - 1] * 3 + Qs
        AB[i] = AB[i - 1] * 3 + A[i - 1]
        ABC[i] = ABC[i - 1] * 3 + AB[i - 1]
        Qs *= 3
    elif s == 'A':
        A[i] = A[i - 1] + Qs
        AB[i] = AB[i - 1]
        ABC[i] = ABC[i - 1]
    elif s == 'B':
        A[i] = A[i - 1]
        AB[i] = AB[i - 1] + A[i - 1]
        ABC[i] = ABC[i - 1]
    elif s == 'C':
        A[i] = A[i - 1]
        AB[i] = AB[i - 1]
        ABC[i] = ABC[i - 1] + AB[i - 1]

ans = ABC[-1] % MOD
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0, 0, 0, 0]
dp[0] = 1

for s in S:
    factor = 3 if s == '?' else 1
    for j, c in zip([2, 1, 0], 'CBA'):
        dp[j + 1] = dp[j + 1] * factor % MOD
        if s == c or s == '?':
            dp[j + 1] += dp[j]
    if s == '?':
        dp[0] = (dp[0] * 3) % MOD

ans = dp[-1] % MOD

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

h, w = map(int, input().split())
visited = [[False] * w for _ in range(h)]
pts = []
for i in range(h):
    s = input().rstrip()
    for j in range(w):
        if s[j] == '#':
            visited[i][j] = True
            pts.append((i, j))
res = 0
ds = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while True:
    new_pts = []
    for i, j in pts:
        for dx, dy in ds:
            new_i = i + dy
            new_j = j + dx
            if 0 <= new_i < h and 0 <= new_j < w and not visited[new_i][new_j]:
                visited[new_i][new_j] = True
                new_pts.append((new_i, new_j))
    if len(new_pts) > 0:
        res += 1
        pts = new_pts
    else:
        break
print(res)

### FIXED CODE ###

h, w = map(int, input().split())
visited = [[False] * w for _ in range(h)]
pts = []
for i in range(h):
    s = input().rstrip()
    for j in range(w):
        if s[j] == '#':
            visited[i][j] = True
            pts.append((i, j))
res = 0
ds = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while True:
    new_pts = []
    for i, j in pts:
        for dx, dy in ds:
            new_i = i + dy
            new_j = j + dx
            if 0 <= new_i < h and 0 <= new_j < w and not visited[new_i][new_j]:
                visited[new_i][new_j] = True
                new_pts.append((new_i, new_j))
    if len(new_pts) > 0:
        res += 1
        pts = new_pts
    else:
        break
print(res)
### BUGGY CODE ###

s=input()
while True:
  if s.count("ST")==0:break
  s=s.replace("ST","")
print(len(s))


### FIXED CODE ###

ans=0
stack=[]
for s in input():
    if len(stack)>0 and s=="T":
        if stack[-1]=="S":
            del stack[-1]
        else:
            stack.append(s)
    else:
        stack.append(s)
print(len(stack))
### BUGGY CODE ###

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

ba = B - A 
if A % 2 == 0:
	ja = "j0"
else:
	ja = "j1"

if B % 2 == 0:
	jb = "j0"
else:
	jb = "j1"

a = A
b = B
a2 = ""
b2 = ""

if a == 0:
	a2 = "0"
else:
	while True:
		if a % 2 == 0:
			a2 += "0"
		else:
			a2 += "1"
		a = int(a // 2)
		if a == 1:
			a2 += "1"
			break
if b == 0:
	b2 = "0"
else:
	while True:
		if b % 2 == 0:
			b2 += "0"
		else:
			b2 += "1"
		b = int(b // 2)
		if b == 1:
			b2 += "1"
			break

a2 += "0" * (len(b2) - len(a2))
c2 = 0

if a2[0] == "0":
	if ba % 4 == 2 or ba % 4 == 1:
		c2 += 1
	else:
		c2 += 0

if a2[0] == "1":
	if ba % 4 <= 1:
		c2 += 1
	else:
		c2 += 0

for i in range(1, len(a2)):
	n = 0
	if a2[i] == "1":
		if ja == "j1":
			n += 1

	if b2[i] == "1":
		if jb == "j0":
			n += 1

	if n % 2 == 0:
		c2 += 0
	else:
		c2 += 2 ** i

print(c2)


### FIXED CODE ###

a, b = list(map(int, input().split()))
ba = b - a
if a % 2 == 0:
	ja = "j0"
else:
	ja = "j1"

if b % 2 == 0:
	jb = "j0"
else:
	jb = "j1"

a2 = format(a, "b")
b2 = format(b, "b")
a2 = str(a2[::-1])
b2 = str(b2[::-1])

a2 += "0" * (len(b2) - len(a2))
c2 = 0

if a2[0] == "0":
	if ba % 4 == 2 or ba % 4 == 1:
		c2 += 1

if a2[0] == "1":
	if ba % 4 <= 1:
		c2 += 1

for i in range(1, len(a2)):
	n = 0
	if a2[i] == "1":
		if ja == "j1":
			n += 1

	if b2[i] == "1":
		if jb == "j0":
			n += 1

	if n % 2 == 1:
		c2 += 2 ** i

print(c2)
### BUGGY CODE ###

from sys import stdin

r, g, b, n = map(int, stdin.readline().rstrip().split())
count = 0
for i in range(n + 1):
    for j in range(n + 1):
        if i * r + j * g <= n:
            if (n - (i * r + j * g)) % b == 0:
                # print(i, j, int((n - (i * r + j * i)) / b))
                count += 1
print(count)

### FIXED CODE ###

from sys import stdin

r, g, b, n = map(int, stdin.readline().rstrip().split())
count = 0
for i in range(n + 1):
    for j in range(n + 1):
        if i * r + j * g <= n:
            if (n - (i * r + j * g)) % b == 0:
                # print(i, j, int((n - (i * r + j * i)) / b))
                count += 1
print(count)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1,n):
    ans += i
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
if ((n-1)%2==0):
    ans = (n)*((n-1)//2)
else:
    ans = (n)*((n-1)//2) + n//2
print(ans)
### BUGGY CODE ###

from itertools import permutations
import numpy as np
N = int(input())
red = np.array([list(map(int, input().split())) for _ in range(N)])
blue = np.array([list(map(int, input().split())) for _ in range(N)])

def shuffle(l):
    for i in permutations(l):
        yield i

def judge(r, b):
    cnt = 0
    for i, j in zip(r, b):
        if i[0] < j[0] and i[1] < j[1]:
            cnt += 1
    return cnt

print(max([judge(red, b) for b in shuffle(blue)]))

### FIXED CODE ###

N = int(input())
red = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x:x[1], reverse=True)
blue = sorted([list(map(int, input().split())) for _ in range(N)])

cnt = 0
for i in blue:
    for j in red:
        if i[0] > j[0] and i[1] > j[1]:
            cnt += 1
            red.remove(j)
            break

print(cnt)
### BUGGY CODE ###

n, k = map(int, input().split())
lst = list(map(int, input().split()))
for i in range(min(k,41)):
    lit = [0 for _ in range(n)]
    for _ in range(0, n):
        mx = max(0,_ - lst[_])
        mn = min(n, _ + lst[_] +1)
        lit[mx:mn] = map(lambda x:x+1, lit[mx:mn])
    lst = lit
lst = [str(_) for _ in lst]
ans = ' '.join(lst)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
lst = list(map(int, input().split()))

if n**(1/2) <= k:
    lst = [n for _ in range(n)]
    print(*lst)
else:
    for _ in range(k):
        ans = 0
        dp = [0] * (n + 1)
        for _ in range(n):  
            mx = max(0,_ - lst[_])
            mn = min(n, _ + lst[_] +1)
            dp[mx] += 1
            dp[mn] -= 1
        
        for _ in range(n):
            ans = ans + dp[_]
            lst[_] = ans

    print(*lst[:n])
### BUGGY CODE ###

s = input()

betweenLength = []
for i in range(len(s)):
    if s[i] == 'A':
        for j in range(len(s)):
            if i < j and s[j] == 'Z':
                betweenLength.append(len(s[0:j]) + 1 - len(s[0:i]))

print(max(betweenLength))


### FIXED CODE ###

s = input()

## 正答
print(s.rfind('Z') - s.find('A') + 1)

## 下記は正答だが処理時間が長すぎたケース
# betweenLength = []
# for i in range(len(s)):
#     if s[i] == 'A':
#         for j in range(len(s)):
#             if i < j and s[j] == 'Z':
#                 betweenLength.append(len(s[0:j]) + 1 - len(s[0:i]))

# print(max(betweenLength))
### BUGGY CODE ###

class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    
n=int(input())
hi=[int(k) for k in input().split()]
co=[int(k) for k in input().split()]
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(max(dp))  
      

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    

n = int(raw_input())
hi = list(map(int,raw_input().split()))
co= list(map(int,raw_input().split()))
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(segTree.query(0,0,n-1,0,n-1))