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


import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

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

top_list = [0]


for i in range(1, N):

	if a[i] > a[top_list[-1]]:
		top_list.append(i)

num_list = [0]*N
com = []
for i in range(len(top_list)):
	bisect.insort(com, a[top_list[i]])


for i in range(N - 1, top_list[-1], -1):
	bisect.insort(com, a[i])

stock = 0
#print(com, top_list, num_list)
for top in range(len(top_list) - 2, -1, -1):
	for i in range(top_list[top + 1] - 1, top_list[top], -1):
		bisect.insort(com, a[i])
	judge = 0
	total = stock*(a[top_list[top + 1]] - a[top_list[top]])
	#print(total, (a[top_list[top + 1]] - a[top_list[top]])*stock,  top)
	while judge == 0:
		x = com.pop()
		if x > a[top_list[top]]:
			total += x - a[top_list[top]]
			stock += 1
		else:
			bisect.insort(com, x)
			judge = 1
	num_list[top_list[top + 1]] = total
	#print(com, top_list, num_list, stock)


num_list[top_list[0]] = sum(a) - sum(num_list)
for i in range(N):
	print(num_list[i])

### FIXED CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

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

top_list = [0]


for i in range(1, N):

	if a[i] > a[top_list[-1]]:
		top_list.append(i)

num_list = [0]*N
com = []
for i in range(len(top_list)):
	com.append(a[top_list[i]])
com.sort()

for i in range(N - 1, top_list[-1], -1):
	com.append(a[i])
com.sort()

stock = 0
#print(com, top_list, num_list)
for top in range(len(top_list) - 2, -1, -1):
	if top_list[top + 1] - top_list[top] > 10000:
		for i in range(top_list[top + 1] - 1, top_list[top], -1):
			#bisect.insort(com, a[i])
			com.append(a[i])
		com.sort()
	else:
		for i in range(top_list[top + 1] - 1, top_list[top], -1):
			bisect.insort(com, a[i])

	judge = 0
	total = stock*(a[top_list[top + 1]] - a[top_list[top]])
	#print(total, (a[top_list[top + 1]] - a[top_list[top]])*stock,  top)
	while judge == 0:
		x = com.pop()
		if x > a[top_list[top]]:
			total += x - a[top_list[top]]
			stock += 1
		else:
			bisect.insort(com, x)
			judge = 1
	num_list[top_list[top + 1]] = total
	#print(com, top_list, num_list, stock)


num_list[top_list[0]] = sum(a) - sum(num_list)
for i in range(N):
	print(num_list[i])
### BUGGY CODE ###

s = input()
k = int(input())
import math

if len(s) == 1:
    print(math.floor(k/2))
    exit()
if len(s) == 2:
    if s[0] == s[1]:
        print(k)
        exit()
    else:
        print(0)
        exit()

ans=0
last=s[0]
length=1
change=0
for i in range(1,len(s)):
    if s[i] == last:
        length+=1
    else:
        change += math.floor(length/2)
        length=1
    last=s[i]

change += math.floor(length/2)

ans=change*k
if s[0] != s[-1]:
    print(ans)
    exit()


if s[0] != s[1] and s[-1] != s[-2]:
    print(ans+k-1)
    exit()
for i in range(10**10):
    3*4

print(ans)

### FIXED CODE ###

s = input()
k = int(input())
import math

if len(s) == 1:
    print(math.floor(k/2))
    exit()
if len(s) == 2:
    if s[0] == s[1]:
        print(k)
        exit()
    else:
        print(0)
        exit()
if len(set(list(s))) == 1:
    print(len(s) * k // 2)
    exit()

ans=0
last=s[0]
length=1
change=0
for i in range(1,len(s)):
    if s[i] == last:
        length+=1
    else:
        change += math.floor(length/2)
        length=1
    last=s[i]

change += math.floor(length/2)
ans=change*k
if s[0] != s[-1]:
    print(ans)
    exit()

l_length=1
last=s[0]
for i in range(1,len(s)):
    if s[i] == last:
        l_length+=1
    else:
        break
r_length=1
last=s[-1]
for i in range(len(s)-2,-1,-1):
    if s[i] == last:
        r_length+=1
    else:
        break

if l_length%2==1 and r_length%2==1:
    print(ans+k-1)
    exit()

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = []
for a in A:
  if a < K:
    B.append(a)

N = len(B)
B.sort(reverse=True)
check = [True] + [False]*N
dp = [[False]*(K+1) for i in range(N+1)]
dp[0][0] = True
for i, b in enumerate(B, 1):
  for j in range(K+1):
    dp[i][j] = dp[i-1][j]
    if K-b <= j <= K - 1 and dp[i][j]:
      check[i] = True
    if j >= b and dp[i-1][j-b]:
      dp[i][j] = True

ans = 0
for i in range(N, -1, -1):
  if check[i]:
    break
  ans += 1

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = []
for a in A:
  if a < K:
    B.append(a)

N = len(B)
B.sort(reverse=True)
check = [True] + [False]*N
dp = [[False]*(K+1) for i in range(N+1)]
dp[0][0] = True
for i, b in enumerate(B, 1):
  for j in range(K+1):
    dp[i][j] = dp[i-1][j]
    if K-b <= j <= K - 1 and dp[i][j]:
      check[i] = True
    if j >= b and dp[i-1][j-b]:
      dp[i][j] = True

ans = 0
for i in range(N, -1, -1):
  if check[i]:
    break
  ans += 1

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

import sys
A, B, C, K = map(int, input().split())

mycnt = 0
myans = 0

if A >= K:
    print(K)
    sys.exit()
else:    
    while mycnt < K:
        if A>0:
            mycnt += 1
            A -=1
            myans += 1
        elif B>0:
            mycnt += 1
            B -=1
        else:
            mycnt+=1
            myans -=1
print(myans)

### FIXED CODE ###

import sys
A, B, C, K = map(int, input().split())

mycnt = 0
myans = 0

if A >= K:
    print(K)
    sys.exit()
elif A+B >=K:
    print(A)
else:
    print(A+(K-A-B)*-1)
### BUGGY CODE ###

import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
cs = [0] * N
cs[0] = a[0]
for i in range(N - 1): cs[i + 1] = cs[i] + a[i + 1]
res = float("inf")
for m in range(1, N - 1):
  l = bl(cs[: m], cs[m] // 2)
  r = bl(cs[m: ], cs[m] + (cs[-1] - cs[m]) // 2) + m
  l -= l == m
  r += r == m
  nl = l + 0
  nr = r + 0
  for i in range(3):
    if 0 <= l + i - 1 < m:
      if abs(cs[m] - 2 * cs[l + i - 1]) < abs(cs[m] - 2 * cs[l]):
        nl = l + i - 1
    if m < r + i - 1 < N:
      if abs(cs[-1] - 2 * cs[r + i - 1] + cs[m]) < abs(cs[-1] - 2 * cs[r] + cs[m]):
        nr = r + i - 1
  l = nl
  r = nr
  res = min(res, max(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]) - min(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]))
print(res)

### FIXED CODE ###

import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
cs = [0] * N
cs[0] = a[0]
for i in range(N - 1): cs[i + 1] = cs[i] + a[i + 1]
res = float("inf")
for m in range(1, N - 1):
  l = bl(cs, cs[m] // 2, hi = m)
  r = bl(cs, cs[m] + (cs[-1] - cs[m]) // 2, lo = m)
  l -= l == m
  r += r == m
  nl = l + 0
  nr = r + 0
  for i in range(3):
    if i == 1: continue
    if 0 <= l + i - 1 < m:
      if abs(cs[m] - 2 * cs[l + i - 1]) < abs(cs[m] - 2 * cs[l]):
        nl = l + i - 1
    if m < r + i - 1 < N:
      if abs(cs[-1] - 2 * cs[r + i - 1] + cs[m]) < abs(cs[-1] - 2 * cs[r] + cs[m]):
        nr = r + i - 1
  l = nl
  r = nr
  res = min(res, max(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]) - min(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]))
print(res)
### BUGGY CODE ###

import sys
s = input()
X, Y = map(int, input().split())

sys.setrecursionlimit(8001)

dirs = [(1, 0), (0, -1), (-1, 0), (0, 1)]
S = list(map(len, s.split('T')))
N = len(S)
memo = {}
def process(i, x, y, d):
  if (i,x,y,d) in memo:
    return
  if i >= N:
    if x == X and y == Y:
      print('Yes')
      exit()
    return
  memo[(i,x,y,d)] = 1
  x += dirs[d][0] * S[i]
  y += dirs[d][1] * S[i]
  process(i+1, x, y, (d+1)%4)
  process(i+1, x, y, (d-1)%4)

process(0, 0, 0, 0)
print('No')

### FIXED CODE ###

import sys
sys.setrecursionlimit(8001)
s = input()
X, Y = map(int, input().split())
S = list(map(len, s.split('T')))
N = len(S)
# if N == 1:
#   print(['No', 'Yes'][X == S[0] and Y == 0])
#   exit()
# elif N == 2:
#   print(['No', 'Yes'][X == S[0] and abs(Y) == S[1]])
#   exit()

x = S[0]
y = 0
xmoves = S[2::2]
xmoves.sort()
xmoves.reverse()
ymoves = S[1::2]
ymoves.sort()
ymoves.reverse()

def process(a, l, i, v, d, memo, r):
  if (i,v) in memo:
    return False
  if l == i:
    return v == d
  ab = abs(d-v)
  if ab > r:
    ret = False
  elif a == r:
    ret = True
  else:
    ret = process(a, l, i+1, v+a[i], d, memo, r-a[i]) or process(a, l, i+1, v-a[i], d, memo, r-a[i])
  memo[(i,v)] = ret
  return ret

if process(xmoves, len(xmoves), 0, x, X, {}, sum(xmoves)) and process(ymoves, len(ymoves), 0, y, Y, {}, sum(ymoves)):
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

N = int(input())
S = list(input())
R = [S[:i].count('W') + S[i:].count('E') for i in range(N)]

print(min(R))


### FIXED CODE ###

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

A = []

for n in range(N):
    if n == 0:
        L = 0
        R = sum([s == 'E' for s in S[n+1:]])
    else:
        L += 0 if S[n-1] == 'E' else 1
        R -= 0 if S[n]   != 'E' else 1
    A.append(L+R)

print(min(A))
### BUGGY CODE ###

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

cnt=0
for i in range(n):
    for j in range(i+1,n):
        if A[i]==A[j]:
            cnt+=1

if cnt==0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

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

A = list(set(A))

if len(A) == n:
    print('YES')
else :
    print('NO')
### BUGGY CODE ###

n=int(input())
A=[int(input().replace(' ',''),2)for _ in[0]*n]
p=[0]*2**n
p[0]=1
for I in range(2**n-1):
 a=A[bin(I).count('1')]&~I
 for j in range(n):
  if a&1<<j:p[I|1<<j]+=p[I];p[I|1<<j]%=10**9+7
print(p[-1])

### FIXED CODE ###

n=int(input());
A=[int(input().replace(' ',''),2)for _ in[0]*n]
dp=[0]*2**n
dp[0]=1
for I in range(2**n-1):
    a=A[bin(I).count('1')]&~I
    for j in range(n):
        if a&1<<j:dp[I|1<<j]=(dp[I|1<<j]+dp[I])%(10**9+7)
print(dp[-1])
### BUGGY CODE ###

def popcount(n):
    count = 0
    while n > 0:
        if n % 2 == 1:
            count += 1
        n //= 2
    return count


N = int(input())
X = input()

X_int = int(X, 2)

for i,bit in enumerate(X):
    mask = 2**(N-i-1) * (-1)**(int(bit))
    Xi = X_int + mask

    n = Xi
    ans = 0
    while n > 0:
        ans += 1
        n %= popcount(n)
    print(ans)

### FIXED CODE ###

def popcount(n):
    return bin(n).count('1')


def main():
    N = int(input())
    X = input()

    X_int = int(X, 2)

    pcount_X = popcount(X_int)

    pcount_X_pls1 = pcount_X + 1
    pcount_X_mns1 = pcount_X - 1
    
    X_mod_pcount_X_pls1 = X_int % pcount_X_pls1
    if pcount_X_mns1 != 0:
        X_mod_pcount_X_mns1 = X_int % pcount_X_mns1

    for i,bit in enumerate(X):
        bit = int(bit)
        if bit == 0:
            n = (X_mod_pcount_X_pls1 + pow(2, N-i-1, pcount_X_pls1)) % pcount_X_pls1
        else:
            if pcount_X_mns1 == 0:
                print(0)
                continue
            n = (X_mod_pcount_X_mns1 - pow(2, N-i-1, pcount_X_mns1)) % pcount_X_mns1

        ans = 1
        while n > 0:
            ans += 1
            n %= popcount(n)
        print(ans)
        
main()
### BUGGY CODE ###

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

sum = []

s = 1
for i in range(k):
    s *= a[i]
sum.append(s)

for i in range(k+1, n+1):
    i -= 1
    s = s * a[i] // a[i-k]
    sum.append(s)

for i in range(n-k):
    i += 1
    if sum[i] > sum[i-1]:
        print("Yes")
    else:
        print("No")



### FIXED CODE ###

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

for i in range(k+1, n+1):
    i -= 1
    if a[i-k] < a[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

n,m = map(int,readline().split())
s = [set() for i in range(n)]
c = [set() for i in range(n)]
for i in range(m+n-1):
  a,b = map(int,readline().split())
  a -= 1
  b -= 1
  s[a].add(b)
  c[a].add(b)
  
class segment_():
    def __init__(self,n,ide_ele,segfunc):
        self.ide_ele = ide_ele
        self.num = 1 << n.bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        self.segfunc = segfunc
                
    def update(self, k, r):
        k += self.num
        self.seg[k] = r
        while k:
            k >>= 1
            self.seg[k] = self.segfunc(self.seg[k*2], self.seg[k*2+1])

S = segment_(n,set(),lambda a, b: a|b)
for i,ci in enumerate(c):
  S.update(i,ci)
  
p = set([int(i) for i in range(n)])
ans = [0]*n
root = deque()
root.append(-1)
cnt = 0
l = [1]*n

while root:
  if cnt == n:
    break
  now = root.popleft()
  if now >= 0:
    S.update(now,set())
    l[now] -= 1
  child = list(p-S.seg[1])
  for nex in child:
    cnt += 1
    ans[nex] = now+1
    root.append(nex)
    p.remove(nex)
print(*ans,sep='\n')

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque,defaultdict

n,m = map(int,readline().split())
c = [set() for i in range(n)]
d = defaultdict(int)
for i in range(m+n-1):
  a,b = map(int,readline().split())
  a -= 1
  b -= 1
  c[a].add(b)
  d[b] += 1
  
ans = [0]*n
root = deque()
for i in range(n):
  if d[i] == 0:
    root.append(i)
    break
cnt = 1

while True:
  now = root.popleft()
  for nex in c[now]:
    d[nex] -= 1
    if d[nex] == 0:
      cnt += 1
      ans[nex] = now+1
      root.append(nex)
  if cnt == n:
    break
print(*ans,sep='\n')
### BUGGY CODE ###

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    
    A_cand = [0 for i in range(N)]
    B_cand = [0 for i in range(N)]
    for i, B_i in enumerate(B):
        cnt = 0
        for C_i in C:
            if B_i < C_i:
                cnt += 1
        B_cand[i] = cnt
    
    for i, A_i in enumerate(A):
        cnt = 0
        for j, B_j in enumerate(B):
            if A_i < B_j:
                cnt += B_cand[j]
        A_cand[i] = cnt
    
    print(sum(A_cand))
    

solve()

### FIXED CODE ###

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    
    A.sort()
    B.sort()
    C.sort()
    
    A_cand = [0 for i in range(N)]
    B_cand = [0 for i in range(N)]
    
    skip_loop = 0
    for i in range(N):
        cnt = skip_loop
        for j in range(N-skip_loop):
            if B[N-i-1] < C[N-skip_loop-j-1]:
                cnt += 1
            else:
                break
        B_cand[N-i-1] = cnt
        skip_loop = cnt
    
    skip_loop = 0
    ans = 0
    pre_loop_ans = 0
    for i in range(N):
        cnt = skip_loop
        ans += pre_loop_ans
        for j in range(N-skip_loop):
            if A[N-i-1] < B[N-skip_loop-j-1]:
                ans += B_cand[N-skip_loop-j-1]
                pre_loop_ans += B_cand[N-skip_loop-j-1]
                cnt += 1
            else:
                break
        A_cand[N-i-1] = cnt
        skip_loop = cnt
    print(ans)
    

solve()
### BUGGY CODE ###

T = int(input())

for i in range(T):
  a, b, c, d = map(int, input().split())
  if d<b or a<b:
    print('No')
    continue
  if b-1<=c:
    print('Yes')
    continue
  visited=[]
  while True:
    a = c+(a-c)%b
    if a>c and a<b:
      print('No')
      break
    elif a == c:
      if c in visited:
        print('Yes')
        break
      visited.append(a)
    else:
      a = a-b
      if a in visited:
        print('Yes')
        break
      visited.append(a)
    a+=d



### FIXED CODE ###

import fractions
T = int(input())

for i in range(T):
  a, b, c, d = map(int, input().split())

  if d<b or a<b:
    print('No')
    continue

  if b-1<=c:
    print('Yes')
    continue

  gcd=fractions.gcd(d,b)
  e=b-gcd+a%gcd
  if e>c:
    print('No')
  else:
    print('Yes')
### BUGGY CODE ###

h, w = map(int, input().split())
C = [list(map(int , input().split())) for _ in range(h)]


#import numpy as np
#print(np.array(C))
from collections import deque
step = [(0,1), (1,0)]
que = deque()
que.append((0,0))
seen = [[0] * w for _ in range(h)]
seen[0][0] = 1
ans = []
while len(que) > 0:
    x, y = que.popleft()
    for tx, ty in step:
        xi, yi = x + tx, y + ty
        if xi < 0 or yi < 0 or xi >= h or yi >= w:
            continue
        if seen[xi][yi] == 0:
            if C[x][y] % 2 == 1:
                C[x][y] -= 1
                C[xi][yi] += 1
                seen[xi][yi] = 1
                ans.append((x+1, y+1, xi+1, yi+1))
            que.append((xi, yi))
        #print(np.array(C))
        #print(np.array(seen))
#print(C, seen)
print(len(ans))
for ansi in ans:
    print(' '.join(map(str, ansi)))

### FIXED CODE ###

h, w = map(int, input().split())
a = [list(map(int , input().split())) for _ in range(h)]

res = []
for hi in range(h):
    for wi in range(w-1):
        if a[hi][wi] % 2 == 1:
            a[hi][wi] -= 1
            a[hi][wi+1] += 1
            res.append((hi+1, wi+1, hi+1, wi+1+1))
for hi in range(h-1):
    wi = w - 1
    if a[hi][wi] % 2 == 1:
        a[hi][wi] -= 1
        a[hi+1][wi] += 1
        res.append((hi+1, wi+1, hi+1+1, wi+1))

print(len(res))
for resi in res:
    print(' '.join(map(str, resi)))
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

H, W = map(int, readline().split())
A = [readline() for i in range(H)]

dist = [[0]*(W+1) for i in range(H+1)]
for i in range(H):
    dist[i][W] = 1
for i in range(W):
    dist[H][i] = 1
dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = []
push = que.append
for i in range(H):
    di = dist[i]
    Ai = A[i]
    for j in range(W):
        if Ai[j] == '#':
            di[j] = 1
            push((i, j))

d = 0
que1 = []
while que:
    push = que1.append
    for y, x in que:
        for dx, dy in dd:
            nx = x + dx; ny = y + dy
            if dist[ny][nx]:
                continue
            dist[ny][nx] = 1
            push((ny, nx))
    que.clear()
    que, que1 = que1, que
    d += 1
sys.stdout.write("%d\n" % (d-1))

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
que = deque()
A = [input() for i in range(H)]

dist = [[-1]*W for i in range(H)]
dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            dist[i][j] = 0
            que.append((i, j))

d = 0
while que:
    y, x = que.popleft()
    d = dist[y][x]
    for dx, dy in dd:
        nx = x + dx; ny = y + dy
        if not 0 <= nx < W or not 0 <= ny < H or dist[ny][nx] != -1:
            continue
        dist[ny][nx] = d+1
        que.append((ny, nx))
print(d)
### BUGGY CODE ###

X, K, D = map(int, input().split())

i = 0
nokori = 0

if X > 0 :
    while X > 0 and i < K:
        X -= D
        i += 1
    
    nokori = K - i
    if nokori % 2 == 1 :
        X += D

else :
    while X <= 0 and i < K:
        X += D
        i += 1
    nokori = K - i
    if nokori % 2 == 1 :
        X -= D

print(abs(X))

### FIXED CODE ###

X, K, D = map(int, input().split())

X = abs(X)
aa = X // D

if K < aa :
    X -= K * D
else :
    if (K - aa) % 2 == 1 :
        X -= (aa+1) * D
    else :
        X -= aa * D

print(abs(X))
### BUGGY CODE ###


import sys
input = sys.stdin.readline
#区間の管理は　[a, b)で管理していることに注意

# INT_MIN = -10 ** 18
# MAX_N = 4 * 10 ** 5
# MAX_N = 20


# def init(n_):
#     #簡単にするために2のべき乗に揃える
#     n = 1
#     while n <= n_:
#         n *= 2
#     return n

#初期化
N = int(input())
# n = 1
# while n <= N:
#     n *= 2

n = 262144
data = [0] * (2 * n - 1)

def update(k, a):
    k = k + n - 1
    # data[k] = a
    while k >= 0:
        data[k] = max(a, data[k])
        k = (k - 1) // 2
        # data[k] = max(data[2 * k + 1], data[2 * k + 2])

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

H = tuple(map(int, input().split()))
A = tuple(map(int, input().split()))

# ans = 0

dp = [A[0]] + [0] * (N - 1)
update(H[0] - 1, A[0])
for i in range(1, N):
    # h = int(input())
    # a = int(input())
    dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
    # h = H[i]
    # a = A[i]
    # tmp = query(1, h + 1) #[1, h)での最大値
    # print (h, tmp)
    update(H[i] - 1, dp[i])
    # ans = max(ans, tmp + a)
    # print (data)

print (max(dp))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    # MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    # def init(n_):
    #     #簡単にするために2のべき乗に揃える
    #     n = 1
    #     while n <= n_:
    #         n *= 2
    #     return n

    #初期化
    N = int(input())
    # n = 1
    # while n <= N:
    #     n *= 2

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        # data[k] = a
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            # data[k] = max(data[2 * k + 1], data[2 * k + 2])

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

    H = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))

    # ans = 0

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        # h = int(input())
        # a = int(input())
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        # h = H[i]
        # a = A[i]
        # tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(H[i] - 1, dp[i])
        # ans = max(ans, tmp + a)
        # print (data)

    print (query(0, N, 0, 0, n))

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

import sys
n = int(input())
s = [input() for i in range(n)]

ans = 0
dic =[]
for i in s:
    a = [c for c in i]
    a.sort()
    if len(dic) == 0:
        dic.append(a)
    else:
        for d in dic:
            if a==d:
                ans+=1
            
        dic.append(a)
print(ans)


### FIXED CODE ###

import sys
n = int(input())
s = [input() for i in range(n)]

ans = 0
d = {}
for i in s:
    a = [c for c in i]
    a.sort()
    a = "".join(a)
    if a in d:
        ans+= d[a]
        d[a] +=1
    else:
        d[a] = 1
print(ans)
### BUGGY CODE ###

x, k = [int(i) for i in input().split()]
for i in range(10000000000):
    if x <= abs(x-k):
        print(x)
        break
    else:
        x = abs(x-k)
        continue

### FIXED CODE ###

x, k = [int(i) for i in input().split()]
ans = min(x%k, k - x%k)
print(ans)
### BUGGY CODE ###

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

while True:
    if abs(k - n) < n:
        n = abs(k - n)
    else:
        break

print(n)

### FIXED CODE ###

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

if n >= k:
    n -= k * (n // k)      

if k-n > n:
    print(n)
else:
    print(k-n)