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

N = int(input())

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

ans = i = j = 0

def binary_search(l, p, low):
    if low:
        if len(l) == 1:
            if l[0] < p:
                return 1
            else:
                return 0
        elif l[len(l)//2] < p:
            return len(l[:len(l)//2:]) + binary_search(l[len(l)//2::], p, low)
        else:
            return binary_search(l[:len(l)//2:], p, low) + binary_search(l[len(l)//2::], p, low)
    else:
        if len(l) == 1:
            if l[0] > p:
                return 1
            else:
                return 0
        elif l[len(l)//2] > p:
            return len(l[len(l)//2::]) + binary_search(l[:len(l)//2:], p, low)
        else:
            return binary_search(l[:len(l)//2:], p, low) + binary_search(l[len(l)//2::], p, low)

for b in B:
    i = binary_search(A,b,True)
    j = binary_search(C,b,False)
    ans += i * j

print(ans)

### FIXED CODE ###

N = int(input())

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

ans = i = j = 0

import bisect

for b in B:
    i = bisect.bisect_left(A,b)
    j = N - bisect.bisect_right(C,b)
    ans += i * j
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
MOD = 10 ** 9 + 7
for i in range(N - 1):
	tmp = sum(A[0: i + 1]) * A[i + 1]
	ans += (tmp % MOD)
print(ans % MOD)


### FIXED CODE ###

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

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=dp[i-2]+dp[i-1]
    if i in a:
        dp[i]=0
print(dp[n]%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
a=set(int(input()) for _ in range(m))
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-2]+dp[i-1])%1000000007
    if i in a:
        dp[i]=0
print(dp[n])
### BUGGY CODE ###

inf = input().split()
N = int(inf[0])
M = int(inf[1])
cards = [int(a) for a in input().split()]
for i in range(M):
  inf = input().split()
  C = int(inf[0])
  B = int(inf[1])
  cards += [B]*C

cards.sort(reverse=True)

print(sum(cards[:N]))


### FIXED CODE ###

from collections import defaultdict
inf = input().split()
N = int(inf[0])
W = int(inf[1])
dic = defaultdict(int)

line = input().split()

for a in line:
    dic[int(a)] += 1

for w in range(W):
    inf = input().split()
    b = int(inf[0])
    c = int(inf[1])
    dic[c] += b
    
keys = list(dic.keys())

keys.sort(reverse=True)

count = 0
ans = 0
for k in keys:
    while dic[k]>0:
        if count == N:
            break
        ans += k
        dic[k] -= 1
        count += 1
    if count == N:
        break

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

import numpy as np

N, K, Q = list(map(int, input().strip().split()))
As = [int(input()) for _ in range(Q)]

points = np.asarray([K for _ in range(N)])
for A in As:
    points -= 1
    points[A - 1] += 1

for p in points:
    if p > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

import numpy as np

N, K, Q = list(map(int, input().strip().split()))
As = [int(input()) for _ in range(Q)]

points = np.asarray([K for _ in range(N)])

points -= Q
for A in As:
    points[A - 1] += 1

for p in points:
    if p > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

def main():
  k = int(input())
  params = [1,1,0]
  count = 0
  
  while params[0] < k or params[1] < k or params[2] < k:
    if params[2] < k:
      params[2] = params[2]+1
    elif params[1] < k:
      params = [params[0],params[1]+1,1]
    elif params[0] < k:
      params = [params[0]+1,1,1]
      
    tmp = gcd(params[0], params[1])
    count += 1 if tmp == 1 else gcd(tmp,params[2])
    
  return count
 
def gcd(val1, val2):
  return val1 if (val2 == 0) else gcd(val2, val1 % val2)
    
print(main())

### FIXED CODE ###

import math

def main():
  k = int(input())
  params = [1,1,0]
  count = 0
  
  while params[0] < k or params[1] < k or params[2] < k:
    if params[2] < k:
      params[2] = params[2]+1
    elif params[1] < k:
      params = [params[0],params[1]+1,1]
    elif params[0] < k:
      params = [params[0]+1,1,1]
      
    tmp = 0
    if 1 in params:
      tmp = 1
    else:
      tmp = math.gcd(params[0],params[1])
      if tmp > 1:
        tmp = math.gcd(tmp, params[2])
    
    count += tmp
    
  return count
 
def gcd(val1, val2):
  val3 = 0
  while True:
    val3 = val1 % val2
    val1 = val2
    if val3 == 0:
      break
    val2 = val3
  return val1

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

N, K = map(int, input().split())
A = [int(c) for c in input().split()]

numbers = {a: A.count(a) for a in A}
numbers = list(numbers.values())
numbers.sort()
if len(numbers) <= K:
    print(0)
else:
    print(sum(numbers[:len(numbers) - K]))


### FIXED CODE ###

from collections import defaultdict

N, K = map(int, input().split())
A = list(map(int, input().split()))
D = defaultdict(lambda: 0)
for a in A:
    D[a] += 1
V = list(D.values())
V.sort(reverse=True)
print(sum(V[K:]))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
from collections import deque
class ctmp():
    def __init__(self,ij,dis):
        self.ij=ij
        self.dis=dis
H,W=map(int,input().split())
ls=["#"*(W+2)]
for i in range(H):
    ls.append("#"+input()+"#")
ls.append("#"*(W+2))
q=deque([])
tmp=ctmp((1,1),0)
q.append(tmp)
df={}
while q:
    tmp=q.popleft()
    df[tmp.ij]=1
    if tmp.ij==(H,W):
        break
    if (tmp.ij[0]-1,tmp.ij[1]) not in df and ls[tmp.ij[0]-1][tmp.ij[1]]==".":
        c_tmp=ctmp((tmp.ij[0]-1,tmp.ij[1]),tmp.dis+1)
        q.append(c_tmp)
    if (tmp.ij[0]+1,tmp.ij[1]) not in df and ls[tmp.ij[0]+1][tmp.ij[1]]==".":
        c_tmp=ctmp((tmp.ij[0]+1,tmp.ij[1]),tmp.dis+1)
        q.append(c_tmp)
    if (tmp.ij[0],tmp.ij[1]-1) not in df and ls[tmp.ij[0]][tmp.ij[1]-1]==".":
        c_tmp=ctmp((tmp.ij[0],tmp.ij[1]-1),tmp.dis+1)
        q.append(c_tmp)
    if (tmp.ij[0],tmp.ij[1]+1) not in df and ls[tmp.ij[0]][tmp.ij[1]+1]==".":
        c_tmp=ctmp((tmp.ij[0],tmp.ij[1]+1),tmp.dis+1)
        q.append(c_tmp)
if tmp.ij==(H,W):
    nw=0
    for i in range(1,H+1):
        #for j in range(1,W+1):
         #   if ls[i][j]==".":
          #      nw+=1
        nw+=ls[i].count(".")
    print(nw-tmp.dis-1)
else:
    print(-1)

### FIXED CODE ###

def main():
    import sys
    input=sys.stdin.readline
    from collections import deque
    #class ctmp():
    #    def __init__(self,ij,dis):
    #        self.ij=ij
    #        self.dis=dis
    H,W=map(int,input().split())
    ls=["#"*(W+2)]#
    for i in range(H):
        ls.append("#"+input()+"#")
    ls.append("#"*(W+2))#
    q=deque([])
    #qd=deque([])
    #tmp=ctmp((1,1),0)
    q.append((1,1))
    #qd.append(0)
    #df={}
    lf=[[float("inf") for _ in range(W+2)] for _ in range(H+2)]#
    #これでfとdの両方の役割をこなす
    lf[1][1]=0
    while q:
        tmpij=q.popleft()
        #tmpd=qd.popleft()
        #df[tmpij]=1
        if tmpij==(H,W):
            break
        lind=[(-1,0),(1,0),(0,-1),(0,1)]#
        for i in range(4):
            #ntmpij=(tmpij[0]+(i<2)*(2*i-1),tmpij[1]+(i>1)*(2*i-5))
            ntmpij=(tmpij[0]+lind[i][0],tmpij[1]+lind[i][1])
            #print(ntmpij)
            #if ntmpij not in df and ls[ntmpij[0]][ntmpij[1]]==".":
            if lf[ntmpij[0]][ntmpij[1]]==float("inf") and ls[ntmpij[0]][ntmpij[1]]==".":
                #c_tmp=ctmp(ntmpij,tmp.dis+1)
                #q.append(c_tmp)
                q.append(ntmpij)
                #qd.append(tmpd+1)
                lf[ntmpij[0]][ntmpij[1]]=lf[tmpij[0]][tmpij[1]]+1
                #dは訪れる前に書き込んでしまう
    if tmpij==(H,W):
        nw=0
        for i in range(1,H+1):
            #for j in range(1,W+1):
             #   if ls[i][j]==".":
              #      nw+=1
            nw+=ls[i].count(".")
        #print(nw-tmpd-1)
        print(nw-lf[H][W]-1)
    else:
        print(-1)

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

import sys

tree={}
VALUE = 0
LEFT = 1
RIGHT = 2
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p][VALUE]
        if tmp == x: return True
        if x < tmp:
            p = tree[p][LEFT]
        else:
            p = tree[p][RIGHT]
    return False

def node(x):
    global np
    np += 1
    tree[np] = [x, None, None]
    return np

def insert(p, x):
    if p == None or np == -1: return node(x)
    tmp = tree[p][VALUE]
    if x== tmp: return p
    elif x<tmp:
        tree[p][LEFT]=insert(tree[p][LEFT],x)
    else:
        tree[p][RIGHT]=insert(tree[p][RIGHT],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][VALUE]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][VALUE]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(home,int(s[7:]))
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1

### FIXED CODE ###

import sys

tree={}
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p]
        if tmp[0] == x: return True
        if x < tmp[0]:
            p = tmp[1]
        else:
            p = tmp[2]
    return False

def node(x):
    global np
    np += 1
    tree[np] = [x, None, None]
    return np

def insert(p, x):
    if p == None or np == -1: return node(x)
    tmp = tree[p]
    if x== tmp[0]: return p
    elif x<tmp[0]:
        tree[p][1]=insert(tmp[1],x)
    else:
        tree[p][2]=insert(tmp[2],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][0]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][0]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(0,int(s[7:]))
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1
### BUGGY CODE ###

n=int(input())

count = 0

for c in range(1,n):
    num=n-c
    for a in range(1,n):
        if num%a==0:
            for b in range(1,n):
                if (a*b)+c == n:
                    count += 1
else:
    print(count)

### FIXED CODE ###

N = int(input())
ans = 0
for a in range(1, N):
    ans += (N-1)//a
print(ans)
### BUGGY CODE ###

# 初期入力
import sys
input = sys.stdin.readline
N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

#どの宝石を選ぶか全探索
v_c_sum=[]
from itertools import combinations
for i in range(N+1):
    for t in combinations(range(N), i):
        v=0
        c=0
        for j in t:
            v +=V[j]
            c +=C[j]
        v_c_sum.append(v-c)
print(max(v_c_sum))
#print(v_c_sum)

### FIXED CODE ###

# 初期入力
import numpy as np
import sys
input = sys.stdin.readline
N = int(input())
V = np.array(list(map(int, input().split())))
C = np.array(list(map(int, input().split())))

#どの宝石を選ぶか全探索
v_c_sum=0
for i in range(N):
    if 0 < V[i] -C[i]:
        v_c_sum +=V[i] - C[i]
print(v_c_sum)
### BUGGY CODE ###

def Fibonacci(n):
	if n==0 or n==1 : return 1
	return Fibonacci(n-1)+Fibonacci(n-2)

print( Fibonacci( int(input()) ) )

### FIXED CODE ###

def Fibonacci(n, a1, a2):
	if n<1 : return a1
	return Fibonacci(n-1,a1+a2,a1)

print( Fibonacci( int(input()), 1, 0 ) )
### BUGGY CODE ###

N,Q = (int(x) for x in input().split())
S = input()

for i in range(Q):
    l,r = (int(x) for x in input().split())
    print(S[l-1:r].count('AC'))


### FIXED CODE ###

N,Q = (int(x) for x in input().split())
S = list(input())
count = [0 for i in range(N)]
c = 0
for i in range(N-1):
    if S[i] == 'A':
        if S[i+1] == 'C':
            count[i] = c
            c += 1
            i += 1
        elif S[i+1] != 'A':
            count[i] = c
            i += 1 
    count[i] = c
if count[-2] > count[-1]:
    count[-1] = count[-2]

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

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()

    m = {}
    def f(l,r):
        k = (l,r)
        if k in m:
            return m[k]
        if l == r:
            m[k] = a[l]
            return a[l]

        b = a[l] - f(l+1,r)
        t = a[r] - f(l,r-1)
        if b < t:
            b = t
        m[k] = b
        return m[k]

    r = f(0,n-1)

    return r


print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()

    t = [[0]*n for _ in range(n)]
    for i in range(n):
        t[i][i] = a[i]

    for i in range(n-2,-1,-1):
        z = t[i]
        y = t[i+1]
        for j in range(i+1,n):
            r = a[j] - z[j-1]
            u = a[i] - y[j]
            if r < u:
                r = u
            z[j] = r

    return t[0][-1]


print(main())
### BUGGY CODE ###

from collections import deque
N, M = [int(x) for x in input().split()]
fst_to = deque([])
sec_from = deque([])
for a, b in [[int(x) for x in input().split()] for _ in range(M)]:
  if a == 1:
    fst_to.append(b)
  elif b == N:
    sec_from.append(a)
ret = 'IMPOSSIBLE'
for a in fst_to:
  if a in sec_from:
    ret = 'POSSIBLE'
    break
print(ret)

### FIXED CODE ###

from collections import deque
N, M = [int(x) for x in input().split()]
fst_to = deque([])
sec_from = deque([])
for a, b in [[int(x) for x in input().split()] for _ in range(M)]:
  if a == 1:
    fst_to.append(b)
  elif b == N:
    sec_from.append(a)
ret = 'IMPOSSIBLE'
if set(fst_to) & set(sec_from):
  ret = 'POSSIBLE'
print(ret)
### BUGGY CODE ###


import sys


def solv(n):
    r = 0
    if n % 2 == 1:
        if (n-2) in primes:
            r = 1
    else:
        for p in primes:
            if n/2 < p:
                break
            q = n - p
#            if q in primes:
            if binary_search(primes, q):
                r += 1
    return r


def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]


def binary_search(lis, x):
    if len(lis) == 0:
        return None
    i = len(lis) / 2
    if lis[i] == x:
        return x
    elif x < lis[i]:
        return binary_search(lis[:i], x)
    else:
        return binary_search(lis[i+1:], x)


primes = []
for p in prime_list(50000):
    primes.append(p)

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit()
    print solv(n)

### FIXED CODE ###


import sys
import itertools


def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]


primes = []
for p in prime_list(50000):
    primes.append(p)
c = [0] * 50001 * 2
for i, j in itertools.combinations(primes, 2):
    c[i+j] += 1
for i in primes:
    c[i+i] += 1
while True:
    n = int(sys.stdin.readline())
    if n == 0:
        exit()
    print c[n]
### BUGGY CODE ###

# B
import numpy as np
np.random.seed(71)
from collections import deque
# input
N, M = map(int, input().split())
G = dict()
for n in range(1, N+1):
    G[n] = []

for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)
    
# find minimum degree
sv = np.array([len(G[k]) for k in range(1, N+1)])
s = np.random.choice(np.arange(N)[sv == min(sv)]) + 1

targets = dict()
for a in G[s]:
    targets[a] = 1


# BFS from st
t = G[s][0]
pt = [s, t]
del targets[t]
while len(targets) > 0:
    ques = deque()
    visited = [0]*(N+1)    
    for a in pt:
        visited[a] = 1
    ques.append([t, pt])
    end = 0
    while len(ques) > 0 and end == 0:
        q = ques.popleft()
        s = q[0]
        pt = q[1]
        for t in G[s]:
            if visited[t] == 1:
                pass
            elif t in targets.keys():
                pt.append(t)
                end = 1
                del targets[t]
                break
            else:
                visited[t] = 1
                ques.append([t, pt+[t]])
            

# BFS from end
visited = [0]*(N+1)
for a in pt:
    visited[a] = 1
sv = np.array([len([l for l in G[k] if visited[l] == 0]) if visited[k] == 0 else N for k in range(1, N+1)])

# need calculation
if len([l for l in G[t] if visited[l] == 0]) != 0:
    endp = np.random.choice(np.arange(N)[sv == min(sv)]) + 1
    targets = dict()
    for a in G[endp]:
        if visited[a] == 0:
            targets[a] = 1
    while len(targets) > 0:
        ques = deque()
        visited = [0]*(N+1)    
        for a in pt:
            visited[a] = 1
        visited[endp] = 1
        ques.append([t, pt])
        end = 0
        while len(ques) > 0 and end == 0:
            q = ques.popleft()
            s = q[0]
            pt = q[1]
            for t in G[s]:
                if visited[t] == 1:
                    pass
                elif t in targets.keys():
                    pt.append(t)
                    end = 1
                    del targets[t]
                    break
                else:
                    visited[t] = 1
                    ques.append([t, pt+[t]])
    pt.append(endp)
        
print(len(pt))
print(" ".join([str(a) for a in pt]))

### FIXED CODE ###

# B
import numpy as np
from collections import deque
# input
N, M = map(int, input().split())
G = dict()
for n in range(1, N+1):
    G[n] = []
    
visited = [0]*(N+1)
for m in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)
    if m == 0:
        pt = [A, B]
        visited[A] = 1
        visited[B] = 1

# from left
s = pt[0]
add_left = list()

while True:
    left_ext = [l for l in G[s] if visited[l] == 0]
    if len(left_ext) != 0:
        s = left_ext[0]
        visited[s] = 1
        add_left.append(s)
    else:
        break

# from right
s = pt[1]
add_right = list()

while True:
    right_ext = [l for l in G[s] if visited[l] == 0]
    if len(right_ext) != 0:
        s = right_ext[0]
        visited[s] = 1
        add_right.append(s)
    else:
        break
pt = list(reversed(add_left)) + pt + add_right
print(len(pt))
print(" ".join([str(a) for a in pt]))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
ans = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    substr = str(s[l - 1:r])
    ans[i] = substr.count("AC")
print(*ans, sep='\n')

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
cum = [0] * (n + 1)
for i in range(2, n + 1):
    cum[i] = cum[i - 1]
    if s[i - 2:i] == "AC":
        cum[i] += 1

ans = [0] * q

for i in range(q):
    l, r = map(int, input().split())
    ans[i] = cum[r] - cum[l]
print(*ans, sep='\n')
### BUGGY CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

powof2 = lambda x: len("{:b}".format(x))

def f2(n, h, a):
    p = powof2(n)
    N = 2 ** p
    segt = [0] * (2 * N - 1)

    def getmax(a, b, i = 0, l = 0, r = N - 1):
        if r <= a or b <= l:
            return(0)
        if a <= l and r <= b:
            return(segt[i])
        lmax = getmax(a, b, 2 * i + 1, l, (l + r) // 2)
        rmax = getmax(a, b, 2 * i + 2, (l + r) // 2, r)
        return(lmax if lmax > rmax else rmax)

    def setmax(i, v):
        si = i + N - 1
        segt[si] = v
        while si > 0:
            si = (si - 1) // 2
            si1 = 2 * si + 1
            si2 = si1 + 1
            segt[si] = segt[si1] if segt[si1] > segt[si2] else segt[si2]

    for i in range(1, n + 1):
        m = getmax(0, h[i])
        setmax(h[i], m + a[i])

    return(getmax(0, n))

n = int(input()) # 1 <= n <= 2 x 10^5
h = [0] + list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
print(f2(n, h, a))


### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

powof2 = lambda x: len("{:b}".format(x))

def f2(n, h, a):
    p = powof2(n)
    N = 2 ** p
    segt = [0] * (2 * N - 1)

    def getmax(a, b, i = 0, l = 0, r = N - 1):
        if r <= a or b <= l:
            return(0)
        if a <= l and r <= b:
            return(segt[i])
        i1 = 2 * i + 1
        i2 = i1 + 1
        lr = (l + r) // 2
        lmax = getmax(a, b, i1, l, lr)
        rmax = getmax(a, b, i2, lr, r)
        return(lmax if lmax > rmax else rmax)

    def setmax(i, v):
        si = i + N - 1
        segt[si] = v
        while si > 0:
            si = (si - 1) // 2
            si1 = 2 * si + 1
            si2 = si1 + 1
            segt[si] = segt[si1] if segt[si1] > segt[si2] else segt[si2]

    for i in range(1, n + 1):
        m = getmax(0, h[i])
        setmax(h[i], m + a[i])

    return(getmax(0, n))

n = int(input()) # 1 <= n <= 2 x 10^5
h = [0] + list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
print(f2(n, h, a))
### BUGGY CODE ###

n, m = map(int, input().split())
l1, r1 = map(int, input().split())
num = list(range(1, n+1))
ans = set(num[l1-1:r1])
for i in range(2, m+1):
    l, r = map(int, input().split())
    can_pass = set(num[l-1:r1])
    ans = ans & can_pass
    if len(ans) == 0:
        break
print(len(ans))

### FIXED CODE ###

n, m = map(int, input().split())
l, r = map(int, input().split())
for i in range(m-1):
    l_c, r_c = map(int, input().split()) 
    l = max(l, l_c)
    r = min(r, r_c)
print(max(r-l+1, 0))