Problem:
 Score : 100 points    Problem Statement There are N flowers arranged in a row.
For each i ( 1 \leq i \leq N ), the height and the beauty of the i -th flower from the left is h_i and a_i , respectively.
Here, h_1, h_2, \ldots, h_N are all distinct.  Taro is pulling out some flowers so that the following condition is met:   The heights of the remaining flowers are monotonically increasing from left to right.   Find the maximum possible sum of the beauties of the remaining flowers.      Constraints  All values in input are integers.  1 \leq N \leq 2 × 10^5  1 \leq h_i \leq N  h_1, h_2, \ldots, h_N are all distinct.  1 \leq a_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  h_1  h_2  \ldots  h_N  a_1  a_2  \ldots  a_N       Output Print the maximum possible sum of the beauties of the remaining flowers.        Sample Input 1 4
3 1 4 2
10 20 30 40      Sample Output 1 60  We should keep the second and fourth flowers from the left.
Then, the heights would be 1, 2 from left to right, which is monotonically increasing, and the sum of the beauties would be 20 + 40 = 60 .       Sample Input 2 1
1
10      Sample Output 2 10  The condition is met already at the beginning.       Sample Input 3 5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000      Sample Output 3 5000000000  The answer may not fit into a 32-bit integer type.       Sample Input 4 9
4 2 5 8 3 6 1 7 9
6 8 8 4 6 3 5 7 5      Sample Output 4 31  We should keep the second, third, sixth, eighth and ninth flowers from the left.

Solution (Python):
mod = 10**9+7
class RMQ:
    def __init__(self, N):
        self.N0 = 2**(N-1).bit_length()
        self.INF = float('inf')
        self.data = [self.INF]*(2*self.N0)
    def update(self, k, x):
        k+=self.N0-1
        self.data[k] = x
        while k>=0:
            k = (k-1)//2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])
    def query(self, l, r):
        L = l+self.N0; R = r+self.N0
        s = self.INF
        while L<R:
            if R&1:
                R-=1
                s = min(s, self.data[R-1])
            if L&1:
                s = min(s, self.data[L-1])
                L+=1

            L >>= 1; R>>=1
        return s
N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
R = RMQ(N+1)
dp = [0]*N
dp[0] = a[0]
R.update(h[0], -dp[0])
for i in range(1, N):
    m = -R.query(0, h[i])
    if m == -float('inf'):
        m = 0
    dp[i] = m+a[i]
    R.update(h[i], -dp[i])
print(max(dp))

Solution (Python):
def solve():
    import sys

    input = sys.stdin.readline

    
    
    
    
    def SegmentTreeClosure(init_val, segfunc, ide_ele) -> 'update,query':
        size = 1 << (len(init_val) - 1).bit_length()

        
        tree = [ide_ele] * (size * 2 - 1)
        for idx, val in enumerate(init_val, size - 1):  
            
            tree[idx] = val
        for idx in range(size - 2, -1, -1):  
            tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

        
        def update(idx: int, val) -> None:
            nonlocal size
            nonlocal tree
            nonlocal segfunc

            idx += size - 1
            
            tree[idx] = val
            while idx > 0:
                idx = (idx - 1) // 2
                tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

        
        def query(left: int, right: int) -> 'result':
            nonlocal size
            nonlocal tree
            nonlocal segfunc

            left += size
            right += size
            ret = ide_ele  
            while left < right:  
                if left % 2:  
                    ret = segfunc(ret, tree[left - 1])
                    left += 1
                if right % 2:  
                    right -= 1
                    ret = segfunc(ret, tree[right - 1])
                left //= 2
                right //= 2

            return ret

        return update, query

    n = int(input())
    h = tuple(map(int, input().split()))
    a = tuple(map(int, input().split()))

    dp = [0] * (n + 1)
    

    update, query = SegmentTreeClosure(init_val=dp, segfunc=max, ide_ele=0)
    for h_, a_ in zip(h, a):
        
        max_ = query(0, h_) + a_
        update(h_, max_)
    print(query(0, n + 1))


solve()

Solution (Python):

class SegmentTree:
    
    def __init__(self,
                 init_val: 'initial value: iterable',
                 segfunc: 'operation unique in case',
                 ide_ele: 'identity element corresponding init_val' = 0,
                 ):
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.size = 1 << (len(init_val) - 1).bit_length()
        self.tree = self._build(init_val)

    def _build(self, init_val) -> 'tree':
        segfunc = self.segfunc

        tree = [self.ide_ele] * (self.size * 2 - 1)

        for idx, val in enumerate(init_val, self.size - 1):  
            
            tree[idx] = val

        for idx in range(self.size - 2, -1, -1):  
            tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

        return tree

    def update(self, idx: int, val) -> None:
        tree = self.tree
        segfunc = self.segfunc

        idx += self.size - 1
        
        tree[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

    def query(self, left: int, right: int) -> 'result':
        left += self.size
        right += self.size
        ret = self.ide_ele  
        segfunc = self.segfunc
        tree = self.tree
        while left < right:
            if left & 1:  
                ret = segfunc(ret, tree[left - 1])
                left += 1
            if right & 1:  
                right -= 1
                ret = segfunc(ret, tree[right - 1])
            left >>= 1
            right >>= 1
        return ret


n = int(input())
h = tuple(map(int, input().split()))
a = tuple(map(int, input().split()))

dp = [0] * (n + 1)


seg = SegmentTree(init_val=dp, segfunc=max, ide_ele=0)

for h_, a_ in zip(h, a):
    
    max_ = seg.query(0, h_) + a_
    seg.update(h_, max_)
print(seg.query(0, n + 1))

Solution (Python):
class SegmentTree:
    def __init__(self, a: list, e: 'default' = 0, f: 'function' = max):
        size = len(a)
        n = 1 << (size - 1).bit_length()
        seg = [e] * (n * 2 - 1)
        for i, a_ in enumerate(a, n - 1):
            seg[i] = a_
        for i in range(n - 2, -1, -1):
            seg[i] = f(seg[i * 2 + 1], seg[i * 2 + 2])
        self.size = size
        self.n = n
        self.seg = seg
        self.a = a
        self.e = e
        self.f = f

    def update(self, k, x):
        n = self.n
        seg = self.seg
        f = self.f

        k += n - 1
        seg[k] = x
        while k > 0:
            k = (k - 1) // 2
            seg[k] = f(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(self, a, b, k=0, l=0, r=-1):
        if r < 0:
            r = self.n
        if r <= a or b <= l:
            return self.e
        if a <= l and r <= b:
            return self.seg[k]
        m = (l + r) // 2
        vl = self.query(a, b, k * 2 + 1, l, m)
        vr = self.query(a, b, k * 2 + 2, m, r)
        return self.f(vl, vr)


n = int(input())
h = tuple(map(int, input().split()))
a = tuple(map(int, input().split()))

dp = [0] * (n + 1)


seg = SegmentTree(a=dp, e=0, f=max)

for h_, a_ in zip(h, a):
    
    max_ = seg.query(0, h_) + a_
    seg.update(h_, max_)
print(seg.query(0, n + 1))

Solution (Python):
class SegmentTree:
    def __init__(self, a: list, e: 'default', f: 'function'):
        n = len(a)
        size = 1 << (n - 1).bit_length()  
        v = [e] * (size * 2 - 1)
        for i in range(n):
            
            v[size - 1 + i] = a[i]
        for i in range(size - 2, -1, -1):
            v[i] = f(v[i * 2 + 1], v[i * 2 + 2])

        self.n = n  
        self.size = size  
        self.v = v  
        self.e = e  
        self.f = f  

    def update(self, k: 'index', x: 'val'):
        k += self.size - 1  
        self.v[k] = x  
        while k > 0:
            k = (k - 1) // 2  
            self.v[k] = self.f(self.v[k * 2 + 1], self.v[k * 2 + 2])

    def get(self, a, b, k=0, l=0, r=-1):
        
        
        if r < 0:
            r = self.size

        if r <= a or b <= l:
            return self.e
        

        if a <= l and r <= b:
            return self.v[k]
        

        m = (l + r) // 2
        return self.f(self.get(a, b, k * 2 + 1, l, m), self.get(a, b, k * 2 + 2, m, r))
        


def solve(n, h, a):
    seg = SegmentTree([0] * (n + 1), 0, max)
    for i in range(n):
        seg.update(h[i], seg.get(0, h[i]) + a[i])
        
        
    return seg.get(0, n + 1)


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

    n = int(input())
    h = tuple(map(int, input().split()))
    a = tuple(map(int, input().split()))
    print(solve(n, h, a))

Solution (Python):
def solve(n, h, a):
    size = 1 << ((n + 1) - 1).bit_length()  
    
    seg = [0] * (size * 2 - 1)

    def update(seg, k, x):
        k += size - 1
        seg[k] = x  
        while k > 0:
            k = (k - 1) // 2  
            seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2])

    def get(seg, a, b, k=0, l=0, r=-1):
        
        
        if r < 0:
            r = size

        if r <= a or b <= l:
            return 0
        

        if a <= l and r <= b:
            return seg[k]
        

        m = (l + r) // 2
        return max(get(seg, a, b, k * 2 + 1, l, m), get(seg, a, b, k * 2 + 2, m, r))
        

    for h_, a_ in zip(h, a):
        update(seg, h_, get(seg, 0, h_) + a_)
        
        
    return get(seg, 0, n + 1)


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

    n = int(input())
    h = tuple(map(int, input().split()))
    a = tuple(map(int, input().split()))
    print(solve(n, h, a))

Solution (Python):
class SegmentTree:
    def __init__(self, a: list, e: 'default', f: 'function'):
        n = len(a)
        size = 1 << (n - 1).bit_length()  
        v = [e] * (size * 2 - 1)
        for i in range(n):
            
            v[size - 1 + i] = a[i]
        for i in range(size - 2, -1, -1):
            v[i] = f(v[i * 2 + 1], v[i * 2 + 2])

        self.n = n  
        self.size = size  
        self.v = v  
        self.e = e  
        self.f = f  

    def update(self, k: 'index', x: 'val'):
        k += self.size - 1  
        self.v[k] = x  
        while k > 0:
            k = (k - 1) // 2  
            self.v[k] = self.f(self.v[k * 2 + 1], self.v[k * 2 + 2])

    def get(self, a, b, k=0, l=0, r=-1):
        
        
        if r < 0:
            r = self.size

        if r <= a or b <= l:
            return self.e
        

        if a <= l and r <= b:
            return self.v[k]
        

        m = (l + r) // 2
        vl = self.get(a, b, k * 2 + 1, l, m)
        vr = self.get(a, b, k * 2 + 2, m, r)
        return self.f(vl, vr)
        


def solve(n, h, a):
    seg = SegmentTree([0] * (n + 1), 0, max)
    for i in range(n):
        tmp = seg.get(0, h[i])
        seg.update(h[i], tmp + a[i])
        
        
    return seg.get(0, n + 1)


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

    n = int(input())
    h = tuple(map(int, input().rstrip().split()))
    a = tuple(map(int, input().rstrip().split()))
    print(solve(n, h, a))

Solution (Python):
class SegmentTree:
    def __init__(self, a: list, e: 'default', f: 'function'):
        n = len(a)
        size = 1 << (n - 1).bit_length()  
        v = [e] * (size * 2 - 1)
        for i in range(n):
            
            v[size - 1 + i] = a[i]
        for i in range(size - 2, -1, -1):
            v[i] = f(v[i * 2 + 1], v[i * 2 + 2])

        self.n = n  
        self.size = size  
        self.v = v  
        self.e = e  
        self.f = f  

    def update(self, k: 'index', x: 'val'):
        k += self.size - 1  
        self.v[k] = x  
        while k > 0:
            k = (k - 1) // 2  
            self.v[k] = self.f(self.v[k * 2 + 1], self.v[k * 2 + 2])

    def get(self, a, b, k=0, l=0, r=-1):
        
        
        if r < 0:
            r = self.size

        if r <= a or b <= l:
            return self.e
        

        if a <= l and r <= b:
            return self.v[k]
        

        m = (l + r) // 2
        vl = self.get(a, b, k * 2 + 1, l, m)
        vr = self.get(a, b, k * 2 + 2, m, r)
        return self.f(vl, vr)
        


def solve(n, h, a):
    seg = SegmentTree([0] * (n + 1), 0, max)
    for i in range(n):
        tmp = seg.get(0, h[i])
        seg.update(h[i], tmp + a[i])
        
        
    return seg.get(0, n + 1)


if __name__ == '__main__':
    n = int(input())
    h = tuple(map(int, input().split()))
    a = tuple(map(int, input().split()))
    print(solve(n, h, a))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
H = list(map(int,readline().split()))
A = list(map(int,readline().split()))

"""
・最後の高さ -> 価値の総和
・BITでmaxを管理
"""

class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_max(self,i):
        s = 0
        while i:
            t = self.tree[i]
            if s<t:
                s=t
            i -= i & -i
        return s
 
    def update(self, i, x):
        while i < self.size:
            if self.tree[i] >= x:
                return
            self.tree[i] = x
            i += i & -i

bit = BIT(N)

for i,(a,h) in enumerate(zip(A,H),1):
    x = bit.get_max(h)
    bit.update(h,x+a)

answer = bit.get_max(N)
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
H = list(map(int,readline().split()))
A = list(map(int,readline().split()))

"""
・最後の高さ -> 価値の総和
・BITでmaxを管理
"""

class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_max(self,i):
        s = 0
        while i:
            t = self.tree[i]
            if s<t:
                s=t
            i -= i & -i
        return s
 
    def update(self, i, x):
        while i < self.size:
            if self.tree[i] < x:
                self.tree[i] = x
            i += i & -i

bit = BIT(N)

for i,(a,h) in enumerate(zip(A,H),1):
    x = bit.get_max(h)
    bit.update(h,x+a)

answer = bit.get_max(N)
print(answer)

Solution (Python):
n = int(input())
num = [ int(v) for v in input().split() ]
beauty = [ int(v) for v in input().split() ]
ln = len(bin(n-1))-1
ln2 = 2**(ln-1)
segtree = [ 0 for i in range(2**ln-1) ]


def update(p, q=1):
    p += 2**(ln-1)-2
    r = 0
    while p >= 0:
        if r == 0:
            segtree[p] = q
            r = 1
        else:
            segtree[p] = max(segtree[p], q)
        p = (p-1)//2

def getmax(a,b,k=0,l=0,r=ln2):
    if r <= a or b <= l:
        return 0
    elif l == r:
        return 0
    elif a == l and b == r:
        return segtree[k]
    elif l + 1 == r:
        return segtree[k]
    else:
        return max( getmax(a,min(b,(l+r)//2),2*k+1,l,(l+r)//2), getmax(max(a,(l+r)//2),b,2*k+2,(l+r)//2,r) )

for i in range(n):
    a, b = num[i], beauty[i]
    c = getmax(0,a-1)
    update(a,b+c)
print(getmax(0,n))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class BIT(object):
    def __init__(self,A,dot,e,inv=None):
        n=len(A)
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__inv=inv
        self.__node=['$']+A 
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res
def resolve():
    n=int(input())
    H=list(map(lambda x:int(x)-1,input().split()))
    A=list(map(int,input().split()))
    bit=BIT([0]*n,max,0)
    for i in range(n):
        bit.add(H[i],bit.sum(H[i])+A[i])
    print(bit.sum(n))
resolve()

Solution (Python):
N = int(input())
h = [int(x) - 1 for x in input().split()]
a = [int(x) for x in input().split()]

l2N = 0
n = N
while n > 1:
    n = -(-n//2)
    l2N += 1
N = 2**l2N

seg = [0] * (2 * 2**l2N - 1)

def update(H, x):
    H += 2**l2N - 1
    seg[H] = x
    while H > 0:
        H = (H - 1) // 2
        seg[H] = max(seg[H*2+1], seg[H*2+2])

def maxSrch(a, b, k, l, r):
    if r <= a or b <= l:
        return 0
    if a <= l and r <= b:
        return seg[k]
    else:
        vl = maxSrch(a, b, k*2+1, l, (l+r)//2)
        vr = maxSrch(a, b, k*2+2, (l+r)//2, r)
        return max(vl, vr)

for H,A in zip(h,a):
    update(H, maxSrch(0,H,0,0,N) + A)
print(seg[0])

Solution (Python):
n=int(input())
def f(x):
    s=0
    while x>0:
        s=max(s,t[x])
        x-=x&-x
    return s
def g(x,y):
    while x<n+1:
        t[x]=max(y,t[x])
        x+=x&-x
t=[0]*(n+1)
h=list(map(int,input().split()))
a=list(map(int,input().split()))
for i in range(n):
    g(h[i],f(h[i]-1)+a[i])
print(max(t))

Solution (Python):

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
        while i>=0:
            if data[i]<x:
                data[i]=x
            else:
                break
            i=(i-1)//2

    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=[int(i) for i in input().split()]
aaa=[int(i) for i in input().split()]
print(solve(n,hhh,aaa))

Solution (Python):
N = int(input())
h = [0] + list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
dp = [0] * (N + 1)

ide_ele = 0


num = 2 ** (N).bit_length()
seg = [ide_ele] * 2 * num

def segfunc(x, y):
  return max(x, y) 

def init(init_val):
  
  for i in range(N):
    seg[i + num - 1] = init_val[i]    
  
  for i in range(num - 2, -1, -1) :
    seg[i]=segfunc(seg[2 * i + 1], seg[2 * i + 2]) 
    
def update(k, x):
  k += num - 1
  seg[k] = x
  while k + 1:
    k = (k - 1) // 2
    seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])
    
def query(p, q):
  if q <= p:
    return ide_ele
  p += num - 1
  q += num - 2
  res = ide_ele
  while q - p > 1:
    if p & 1 == 0:
      res = segfunc(res, seg[p])
    if q & 1 == 1:
      res = segfunc(res, seg[q])
      q -= 1
    p = p // 2
    q = (q - 1) // 2
  if p == q:
    res = segfunc(res, seg[p])
  else:
    res = segfunc(segfunc(res, seg[p]), seg[q])
  return res


for i in range(N):
  temp = query(0, h[i + 1]) + a[i + 1]
  update(h[i + 1], temp)
print(query(0, N + 2))

Solution (Python):
INF = 10**30

class Rmax():
	def __init__(self, size):
		
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0 for _ in range(2*self.n-1)]

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = max(self.node[2*x+1], self.node[2*x+2])
		return

	
	def Get(self, a, b, k=0, l=0, r=-1):
		if r < 0:
			r = self.n

		if a >= r or b <= l:
			return 0
		elif a <= l and b >= r:
			return self.node[k]
		else:
			vl = self.Get(a, b, 2*k+1, l, (l+r)//2)
			vr = self.Get(a, b, 2*k+2, (l+r)//2, r)
			return max(vl, vr)

n = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = Rmax(n)
for h, a in zip(H, A):
	h -= 1
	opt = dp.Get(0, h) + a
	if opt > dp.Access(h):
		dp.Update(h, opt)


print(dp.Get(0, n))

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007



def A():
    n,k = LI()
    a = LI()
    dp = [0 for i in range(k+1)]
    f = [0 for i in range(k+1)]
    for i in range(k+1):
        if not f[i]:
            for j in a:
                if i-j >= 0:
                    dp[i] = 1-dp[i-j]
                    if dp[i] == 0:
                        break
            else:
                dp[i] = 1
    print(["First","Second"][dp[k]])

def B():
    n = I()
    a = LI()
    ma = n*(n+1)//2
    su = sum(a)
    s = [1 for i in range(n+1)]
    for i in range(1,n):
        s[i+1] = s[i]+n-i+1
    d = [None for i in range(ma+1)]
    d[0] = 0
    k = 1
    for i in range(1,n+1):
        for j in range(n+1-i):
            d[k+j] = i
        k += n+1-i
    k = n%2
    dp = [su if (d[i]+k)%2 else -su for i in range(ma+1)]
    dp[0] = 0
    if k:
        for i in range(n):
            dp[i+1] = a[n-1-i]
    else:
        for i in range(n):
            dp[i+1] = -a[n-1-i]
    for i in range(1,ma):
        r = n-1-(i-s[d[i]])
        l = r+1-d[i]
        j = i+(n-d[i])
        j2 = j+1
        if (d[i]+k)%2:
            if r < n-1:
                if a[r+1]+dp[i] > dp[j]:
                    dp[j] = a[r+1]+dp[i]
            if l > 0:
                if a[l-1]+dp[i] > dp[j2]:
                    dp[j2] = a[l-1]+dp[i]
        else:
            if r < n-1:
                if -a[r+1]+dp[i] < dp[j]:
                    dp[j] = -a[r+1]+dp[i]
            if l > 0:
                if -a[l-1]+dp[i] < dp[j2]:
                    dp[j2] = -a[l-1]+dp[i]
    print(dp[ma])
    return


def C():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod

    n,k = LI()
    a = LI()
    """
    fact = [1]
    for i in range(n+k):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(n+k+1)
    inv[n+k] = pow(fact[n+k],mod-2,mod)
    for i in range(n+k)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    f = [comb(i+n-1,n-1) for i in range(k+1)]
    for i in a:
        for j in range(k-i)[::-1]:
            f[j+i+1] -= f[j]
            f[j+i+1] %= mod
    print(f[k])
    """
    dp = [[0]*(k+1) for i in range(n+1)]
    for i in range(k+1):
        dp[0][i] = 1
    for i in range(n):
        ni = i+1
        ai = a[i]
        for j in range(k+1):
            if j >= ai+1:
                dp[ni][j] = (dp[i][j]-dp[i][j-ai-1])%mod
            else:
                dp[ni][j] = dp[i][j]
        if i < n-1:
            for j in range(k):
                dp[ni][j+1] += dp[ni][j]
                dp[ni][j+1] %= mod
    print(dp[n][k]%mod)
    return


def D():
    n = I()
    a = LI()
    a.insert(0,0)
    for i in range(n):
        a[i+1] += a[i]
    dp = [[0]*(n+1) for i in range(n)]
    for le in range(1,n):
        for l in range(n-le):
            r = l+le+1
            res = float("inf")
            for i in range(l+1,r):
                m = dp[l][i]+dp[i][r]
                if m < res:
                    res = m
            res += a[r]-a[l]
            dp[l][r] = res
    print(dp[0][n])
    return


def E():

    n = I()
    a = LIR(n)
    m = 1<<n
    dp = [0]*m
    dp[0] = 1
    a = [[j for j in range(n) if a[i][j]] for i in range(n)]
    bit_count = [-1]
    for i in range(n):
        for j in range(len(bit_count)):
            bit_count.append(bit_count[j]+1)
    for k in range(1,m):
        i = bit_count[k]
        for j in a[i]:
            bj = 1<<j
            if bj > k:
                break
            if not k&bj:
                continue
            nk = k^bj
            dp[k] += dp[nk]
    print(dp[m-1]%mod)

def F():

    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        x,y = LI()
        x -= 1
        y -= 1
        v[x].append(y)
        v[y].append(x)
    f = [1]*n
    g = [1]*n
    bfs = [1]*n
    bfs[0] = 0
    q = deque([0])
    par = [None]*n
    d = [[0,i] for i in range(n)]
    while q:
        x = q.popleft()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                par[y] = x
                d[y][0] = d[x][0]+1
                q.append(y)
    d.sort(key = lambda x:-x[0])
    for _,x in d[:-1]:
        px = par[x]
        fx,gx = f[x],g[x]
        f[px] *= fx+gx
        if f[px] >= mod:
            f[px] %= mod
        g[px] *= fx
        if g[px] >= mod:
            g[px] %= mod
    print((f[0]+g[0])%mod)
    return


def G():
    class SegmentTree:
        def __init__(self, size, default, op = max):
            self.size = 2**size.bit_length()
            self.dat = [default]*(self.size*2)
            self.op = op

        def update(self, i, x):
            i += self.size
            self.dat[i] = x
            while i > 0:
                i >>= 1
                self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

        def add(self, i, x):
            i += self.size
            self.dat[i] = self.op(self.dat[i], x)
            while i > 0:
                i >>= 1
                self.dat[i] = self.op(self.dat[i], x)

        def get(self, a, b = None):
            if b is None:
                b = a + 1
            l, r = a + self.size, b + self.size
            res = None
            while l < r:
                if l & 1:
                    if res is None:
                        res = self.dat[l]
                    else:
                        res = self.op(res, self.dat[l])
                    l += 1

                if r & 1:
                    r -= 1
                    if res is None:
                        res = self.dat[r]
                    else:
                        res = self.op(res, self.dat[r])
                l >>= 1
                r >>= 1
            return res
    n = I()
    h = LI()
    a = LI()
    dp = SegmentTree(n+1, 0)
    for i in range(n):
        hi,ai = h[i],a[i]
        ma = dp.get(0,hi)
        dp.update(hi,ma+ai)
    print(dp.get(0,n+1))
    return


def H():
    return


if __name__ == "__main__":
    G()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
H = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]


def BIT_update(tree,h,x):
    while h <= N and tree[h] < x:
        tree[h] = x
        h += h&(-h)

def BIT_max(tree,h):
    x = 0
    while h:
        y = tree[h]
        x = x if x > y else y
        h -= h&(-h)
    return x

tree = [0] * (N+1)
for h,a in zip(H,A):
    x = BIT_max(tree,h)
    BIT_update(tree,h,x+a)

answer = max(tree)
print(answer)

Solution (Python):
def update(fen, pos, value):
    size = len(fen)
    while pos < size:
        fen[pos] = max(fen[pos], value)
        pos = pos + (pos & -pos)

def query(fen, pos):
    ret  = 0
    while pos > 0:
        ret = max(ret, fen[pos])
        pos = pos - (pos & -pos)
    return ret

def main():
    N = int(input())
    H = list(map(int, input().split()))
    B = list(map(int, input().split()))
    fen = list(0 for i in range(0,N + 2))
    ans = 0
    for i in range( 0, N ):
        ret = query(fen, H[i] - 1) + B[i]
        ans = max(ans, ret)
        update(fen, H[i], ret)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def build(t,arr,v,tl,tr):
    if tl == tr:
        t[v] = arr[tl]
    else:
        tm = (tl+tr)//2
        build(t,arr,2*v,tl,tm)
        build(t,arr,2*v+1,tm+1,tr)
        t[v] = max(t[2*v],t[2*v+1])

def maxQuery(t,v,tl,tr,l,r):
    if l > r:
        return 0
    if l == tl and r == tr:
        return t[v]
    tm = (tl+tr)//2
    return max(maxQuery(t,2*v,tl,tm,l,min(r,tm)),maxQuery(t,2*v+1,tm+1,tr,max(l,tm+1),r))

def update(t,v,tl,tr,pos,new_val):
    if tl == tr:
        t[v] = new_val
    else:
        tm = (tl+tr)//2
        if pos <= tm:
            update(t,2*v,tl,tm,pos,new_val)
        else:
            update(t,2*v+1,tm+1,tr,pos,new_val)
        t[v] = max(t[2*v],t[2*v+1])

def create(n,arr):
    t = [0]*4*n
    build(t,arr,1,0,n-1)

    return t
    

def main():
    n = int(raw_input())
    hts = list(map(int,raw_input().split()))
    beauties = list(map(int,raw_input().split()))
    flowers = {}
    for i in range(n):
        flowers[hts[i]] = beauties[i]

    dp = [0]*n
    t = create(n,dp)
    for i in range(n-1,-1,-1):
        curr = hts[i]
        max_val = maxQuery(t,1,0,n-1,curr-1,n-1)
        dp[curr-1] += flowers[curr]+max_val
        update(t,1,0,n-1,curr-1,dp[curr-1])
        

    print(max(t))


main()

Solution (Python):


import sys

class QFlowers:
    def solve(self):
        n = int(input())
        h = [int(_) for _ in input().split()]
        a = [int(_) for _ in input().split()]

        
        

        def update(i, x):
            while i < n + 1:
                if x > dp[i]:
                    dp[i] = x
                i += i & -i

        def get(i):
            mx = 0
            while i > 0:
                if dp[i] > mx:
                    mx = dp[i]
                i -= i & -i
            return mx

        dp = [0] * (n + 1)
        for i, he in enumerate(h):
            update(he, get(he - 1) + a[i])

        
        print(max(dp))

solver = QFlowers()
input = sys.stdin.readline

solver.solve()

Solution (Python):
class segTree:
  inf = 0
  def __init__(self, num):
    self.N = 1
    while self.N < num:
      self.N *= 2
    self.T = [self.inf] * (2 * self.N - 1)
  def do(self, l, r):
    
    return max(l, r)
  def set(self, L):
    for i in range(len(L)):
      self.update(i, L[i])
  def update(self, x, v):
    k = x + self.N - 1
    self.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      self.T[k] = self.do(self.T[2*k+1], self.T[2*k+2])
  def getV(self, l, r):
    return self.getVs(l, r, 0, 0, self.N - 1)
  def getVs(self, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return self.T[k]
    t = (kl + kr) // 2
    if l > t:
      return self.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return self.getVs(l, r , 2 * k + 1, kl, t)
    return self.do(self.getVs(l, r , 2 * k + 1, kl,t),
              self.getVs(l, r , 2 * k + 2, t + 1, kr))

import copy
N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

D = segTree(N)
x = copy.deepcopy(h)
x.sort()
R = {}
for i in range(N):
  R[x[i]] = i

DP = [0] * N
for i in range(N):
  DP[i] = D.getV(0, R[h[i]]) + a[i]
  D.update(R[h[i]], DP[i])

print(max(DP))