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

import sys
sys.setrecursionlimit(10 ** 9)
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    ai, bi = map(int, input().split())
    g[ai - 1].append(bi - 1)
    g[bi - 1].append(ai - 1)

ans = [0] * n
for _ in range(q):
    pi, xi = map(int, input().split())
    ans[pi - 1] += xi


def dfs(v, p=-1):
    for u in g[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)


dfs(0)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
# 深さ優先探索で各直線を考える


def main():
    def dfs(v, p):
        for u in tree[v]:
            if u == p:
                continue
            # 累積和の計算
            ans[u] += ans[v]
            dfs(u, v)

    n, q = map(int, input().split())
    # tree[i]: 頂点i+1の子どもたち
    tree = [[] for i in range(n)]
    ans = [0] * n

    for _ in range(0, n - 1):
        a, b = map(int, input().split())
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)

    for _ in range(q):
        p, x = map(int, input().split())
        ans[p - 1] += x

    # 根ノードの頂点 1 から開始
    dfs(0, -1)

    print(*ans)


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

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

r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r*g*b

for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if S[i]!=S[j]!=S[k]!=S[i]:
        if j-i==k-j:
          ans -= 1

print(ans)

### FIXED CODE ###

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

r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r*g*b

for i in range(N):
  for j in range(i+1,N):
    k=2*j-i
    if k<N and S[i]!=S[j]!=S[k]!=S[i]:
      ans -= 1

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

import sys
#import copy
#import numpy as np
#import itertools
#import collections
#from collections import deque
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

inf = float('inf')

def main():
    # input
    N = int(readline())
    A = list(map(int, readline().split()))

    K = N//2
    DP = [[-inf] * (K)  for _ in range(N)]

    DP[0][0] = A[0]
    DP[1][0] = max(A[0], A[1])
    for i in range(2, N):
        for j in range(K):
            if j == 0:
                DP[i][j] = max(A[i], DP[i-1][j])
            else:
                DP[i][j] = max(DP[i-2][j-1] + A[i], DP[i-1][j])

    ans = DP[N-1][K-1]
    #print(DP)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#import copy
#import numpy as np
#import itertools
#import collections
#from collections import deque
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

inf = float('inf')
#inf = pow(10, 10)

def main():
    # input
    N = int(readline())
    A = list(map(int, readline().split()))

    K = N//2
    DP0 = [-inf] * N
    DP1 = [-inf] * N
    DP2 = [-inf] * N

    DP2[0] = A[0]
    DP2[1] = max(A[0], A[1])
    DP1[:2] = [0] * 2
    DP0[:4] = [0] * 4
    for i in range(2, N):
        if i%2 == 0:
            DP2[i] = DP2[i-2] + A[i]
            DP1[i] = max(DP2[i-1], DP1[i-2] + A[i])
            DP0[i] = max(DP1[i-1], DP0[i-2] + A[i])
        else:
            DP2[i] = max(DP2[i-2] + A[i], DP2[i-1])
            DP1[i] = max(DP1[i-1], DP1[i-2] + A[i])
            DP0[i] = max(DP0[i-1], DP0[i-2] + A[i])

    if N%2 == 0:
        ans = DP2[N-1]
    else:
        ans = DP1[N-1]

    #print(DP0)
    #print(DP1)
    #print(DP2)
    print(ans)


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

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]

for i in range(q):
    # print(s[lr[i][0] - 1:lr[i][1]])
    print(s[lr[i][0] - 1:lr[i][1]].count('AC'))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]
ac_list = [0] * (n+1)
for i in range(n):
    ac_list[i+1] = ac_list[i] + (1 if s[i:i+2] == 'AC' else 0)
# print(ac_list)
for i in range(q):
    print(ac_list[lr[i][1]-1] - ac_list[lr[i][0]-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
X = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
dp1 = [set() for _ in range(W)]
dp1[0].add(X[0][0])
dp2 = [set() for _ in range(W)]
for i in range(H):
  if i % 2 == 0:
    dp2 = [set() for _ in range(W)]
  else: dp1 = [set() for _ in range(W)]
  for j in range(W):
    if i % 2 == 0:
      for k in dp1[j]:
        if i + 1 < H:
          u = k + X[i + 1][j]
          v = abs(k - X[i + 1][j])
          dp2[j].add(u)
          dp2[j].add(v)
        if j + 1 < W:
          u = k + X[i][j + 1]
          v = abs(k - X[i][j + 1])
          dp1[j + 1].add(u)
          dp1[j + 1].add(v)
    else:
      for k in dp2[j]:
        if i + 1 < H:
          u = k + X[i + 1][j]
          v = abs(k - X[i + 1][j])
          dp1[j].add(u)
          dp1[j].add(v)
        if j + 1 < W:
          u = k + X[i][j + 1]
          v = abs(k - X[i][j + 1])
          dp2[j + 1].add(u)
          dp2[j + 1].add(v)
res = float("inf")
if H % 2:
  for k in dp1[-1]: res = min(k, res)
else:
  for k in dp2[-1]: res = min(k, res)
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
X = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
dp1 = [set() for _ in range(W)]
dp1[0].add(X[0][0])
dp2 = [set() for _ in range(W)]
dplimit = [[0] * W for _ in range(H)]
dplimit[-1][-1] = 80
for i in range(H - 1, -1, -1):
  for j in range(W - 1, -1, -1):
    x = X[i][j]
    if i > 0: dplimit[i - 1][j] = max(dplimit[i - 1][j], dplimit[i][j] + x)
    if j > 0: dplimit[i][j - 1] = max(dplimit[i][j - 1], dplimit[i][j] + x)
for i in range(H):
  if i % 2 == 0:
    dp2 = [set() for _ in range(W)]
  else: dp1 = [set() for _ in range(W)]
  for j in range(W):
    if i % 2 == 0:
      for k in dp1[j]:
        if i + 1 < H:
          u = k + X[i + 1][j]
          v = abs(k - X[i + 1][j])
          if u <= dplimit[i][j]: dp2[j].add(u)
          if v <= dplimit[i][j]: dp2[j].add(v)
        if j + 1 < W:
          u = k + X[i][j + 1]
          v = abs(k - X[i][j + 1])
          if u <= dplimit[i][j]: dp1[j + 1].add(u)
          if v <= dplimit[i][j]: dp1[j + 1].add(v)
    else:
      for k in dp2[j]:
        if i + 1 < H:
          u = k + X[i + 1][j]
          v = abs(k - X[i + 1][j])
          if u <= dplimit[i][j]: dp1[j].add(u)
          if v <= dplimit[i][j]: dp1[j].add(v)
        if j + 1 < W:
          u = k + X[i][j + 1]
          v = abs(k - X[i][j + 1])
          if u <= dplimit[i][j]: dp2[j + 1].add(u)
          if v <= dplimit[i][j]: dp2[j + 1].add(v)
res = float("inf")
if H % 2:
  for k in dp1[-1]: res = min(k, res)
else:
  for k in dp2[-1]: res = min(k, res)
print(res)
### BUGGY CODE ###

import numpy as np
n,m = map(int, input().split())

routes = []
for i in range(m):
    route = list(map(int, input().split()))
    routes.append(route)

for i in range(m):
    routes[i] = routes[i] - np.ones(2) #道の番号をずらす

rooms = np.zeros(n) # 行ってない部屋は0、行った部屋は1
marks = np.zeros(n) # 部屋におく道標
roomsrate = [[0]] # １回目、２回目、３回目…に行ける部屋
rooms[0] = 1
marks[0] = 1

turn = 0
for i in roomsrate:
    newrate = []
    for j in roomsrate[turn]: #turn回目に行ける部屋を調べる
        for k in range(m):
            a = int(routes[k][0])
            b = int(routes[k][1]) 
            if (j == a or j == b):
                if (int(rooms[b]) == 0):
                    rooms[b] = 1
                    marks[b] = a
                    newrate.append(b)
                elif (int(rooms[a]) == 0):
                    rooms[a] = 1
                    marks[a] = b
                    newrate.append(a)
    roomsrate.append(newrate)
    if (len(newrate) == 0):
        break
    turn = turn + 1

if(np.all(rooms) == True):
    print('Yes')
    for i in range(1,n):
        print(str(int(marks[i]) + 1))

else:
    print('No')

### FIXED CODE ###

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

routes = [[] for i in range(n)]
for i in range(m):
    x,y = map(int, input().split())
    routes[x-1].append(y-1)
    routes[y-1].append(x-1)


rooms = [0 for i in range(n)] # 行ったら1,まだなら0
marks = [0 for i in range(n)] # 部屋におく道標
rooms_rate = [[0]] # ０回目、１回目、２回目、３回目…に行ける部屋
rooms[0] = 1

turn = 0
for i in rooms_rate:
    newrate = []
    for j in rooms_rate[turn]: #(turn)回目に行けた部屋から行ける部屋を調べる
        for k in routes[j]: 
            if (rooms[k] == 0): #行ったことのない部屋なら
                rooms[k] = 1
                marks[k] = j # 道標をセット
                newrate.append(k)
    rooms_rate.append(newrate)
    if (len(newrate) == 0): #新しく行けなくなったら終わり
        break
    turn = turn + 1


if(all(rooms) == True):
    print('Yes')
    for i in range(1,n):
        print(str(int(marks[i]) + 1))

else:
    print('No')
### BUGGY CODE ###

H, W, D = map(int, input().split())

A = [-1] * (H * W + 1)

for i in range(1, H+1) :
    line = list(map(int, input().split()))
    for j in range(1, W + 1) :
        A[line[j - 1]] = (i, j)

memo = [[-1 for _ in range(H * W + 1)] for _ in range(H * W + 1)]

def cost(nowPoint, endPoint) :
    if nowPoint == endPoint :
        return 0
    if memo[nowPoint][endPoint] >= 0 :
        return memo[nowPoint][endPoint]

    nextPoint = nowPoint + D

    nowCost = abs(A[nextPoint][0] - A[nowPoint][0]) + abs(A[nextPoint][1] - A[nowPoint][1])
    nowCost += cost(nextPoint, endPoint)

    memo[nowPoint][endPoint] = nowCost
    return nowCost

Q = int(input())

for _ in range(Q) :
    start, end = map(int, input().split())
    print(cost(start, end))



### FIXED CODE ###

H, W, D = map(int, input().split())
A = [tuple(map(int, input().split())) for _ in range(H)]

aToHW = {}
for h in range(H):
    for w, a in enumerate(A[h]):
        aToHW[a] = (h, w)

cnt = [-1] * (H * W + 1)
for start in range(1, H * W + 1)[:: -1]:
    c = 0
    for now in range(start, H * W + 1, D):
        if now + D > H * W:
            break
        if cnt[now] >= 0:
            c += cnt[now]
            break

        nH, nW = aToHW[now]
        tH, tW = aToHW[now + D]
        c += abs(nH - tH) + abs(nW - tW)
    cnt[start] = c

Q = int(input())
ans = []
for _ in range(Q):
    L, R = map(int, input().split())
    ans.append(cnt[L] - cnt[R])

print(*ans, sep='\n')
### BUGGY CODE ###

from collections import deque
N, Q = map(int, input().split())
pathes = []
for _ in range(N-1):
    a, b = map(int, input().split())
    pathes.append((a, b))
childs = [[] for i in range(N+1)]
for a, b in pathes:
    childs[a].append(b)
    childs[b].append(a)
cnt = [0]*(N+1)
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x
closed = []
nodes = deque()
nodes.append(1)
while len(nodes) != 0:
    node = nodes.popleft()
    closed.append(node)
    for c in childs[node]:
        if c in closed:
            continue
        nodes.append(c)
        cnt[c] += cnt[node]
for i in range(1, N+1):
    print(cnt[i])

### FIXED CODE ###

from collections import deque
N, Q = map(int, input().split())
pathes = []
for _ in range(N-1):
    a, b = map(int, input().split())
    pathes.append((a, b))
childs = [[] for i in range(N+1)]
for a, b in pathes:
    childs[a].append(b)
    childs[b].append(a)
cnt = [0]*(N+1)
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x
closed = [False]*(N+1)
nodes = deque()
nodes.append(1)
while len(nodes) != 0:
    node = nodes.popleft()
    closed[node] = True
    for c in childs[node]:
        if closed[c]:
            continue
        nodes.append(c)
        cnt[c] += cnt[node]
for i in range(1, N+1):
    print(cnt[i])
### BUGGY CODE ###

n=int(input())
s_list=[sorted(list(input())) for i in range(n)]
S=[]
ans=0

for i in range(n): #リストの文字列変換
  S.append("".join(s_list[i]))
for i in range(n):
  for j in range(i+1,n):
    if S[i] == S[j]:
      ans+=1
print(ans)


### FIXED CODE ###

n = int(input())
d = {}
ans = 0
for i in range(n):
    s = str(sorted(input()))
    if s in d:
        ans+=d[s]
        d[s]+=1
    else:
        d[s]=1
print(ans)
### BUGGY CODE ###

A, B, C, D = map(int, input().split())
count = 0
#AからBをiに代入
for i in range(A, B+1):
    if i % C != 0 and i % D != 0:
        count = count + 1
    else:
        pass   #何もしない

print(count)

### FIXED CODE ###

#最大公約数
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

#最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

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

A = A -1
c_num = B//C - A//C
d_num = B//D - A//D
    
lcm_num = lcm(C, D)

cd_num = B//lcm_num - A//lcm_num
    
print(B - A - c_num - d_num + cd_num)
### BUGGY CODE ###

L, R = map(int, input().split())

ans = 2018
for i in range(L, R):
    for j in range(i+1, R + 1):
        tmp = (i * j) % 2019
        if ans  > tmp:
            ans = tmp
        if tmp == 0:
            ans = 0
            break

print(ans)


### FIXED CODE ###

L, R = map(int, input().split())

ans = 2018
for i in range(L, R):
    for j in range(i+1, R + 1):
        tmp = (i * j) % 2019
        if ans  > tmp:
            ans = tmp
        if tmp == 0:
            ans = 0
            print(ans)
            exit()

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

import collections

n = int(input())

l = [input() for i in range(n)]

c = collections.Counter(l)

max_list = [kv[0] for kv in c.items() if kv[1] == max(c.values())]
max_list.sort()
for i in range(len(max_list)):
    print(max_list[i])


### FIXED CODE ###

n = int(input())
l = [input() for i in range(n)]
d={}

for i in range(len(l)):
    if l[i] in d:
        d[l[i]]+=1
    else:
        d[l[i]]=1

largest=max(d.values())
ans=[]
for key in d.keys():
    if d[key]==largest:
        ans.append(key)
ans=sorted(ans)
for word in ans:
    print(word)
### BUGGY CODE ###

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

### FIXED CODE ###

import numpy as np
n = int(input())
A = np.array(list(map(int, input().split())),dtype=np.longlong)
mod = 7+10**9
cs = 0
for a in A:
    cs += a
    cs %= mod
cumsum = np.mod(np.cumsum(A),mod)
rev = -1*(cumsum-cs)
ans = 0
for i in range(n-1):
    ans += rev[i]*A[i]
    ans %= mod
print(ans)
### BUGGY CODE ###

from collections import*
h,w,d=map(int,input().split())
g=defaultdict(tuple)
for i in range(h):
    tmp=[]
    for j,v in enumerate(map(int,input().split())):
        g[v]=(i,j)
q=int(input())
for i in range(q):
    ans=0
    l,r=map(int,input().split())
    for j in range(l,r-d+1,d):
        ans+=sum(abs(s-t)for s,t in zip(g[j],g[j+d]))
    print(ans)

### FIXED CODE ###

from itertools import*
from collections import*
h,w,d=map(int,input().split())
g=defaultdict(tuple)
f=defaultdict(int)
for i in range(h):
    for j,v in enumerate(map(int,input().split())):
        g[v]=(i,j)
        
q=int(input())

for i in range(1,d+1):
    for k,v in enumerate(accumulate([0]+[sum(abs(s-t)for s,t in zip(g[j+d],g[j]))for j in range(i,h*w+1-d,d)])):
        f[i+k*d]=v
        
for i in range(q):
    l,r=map(int,input().split())
    print(f[r]-f[l])
### BUGGY CODE ###

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N = int(input())
edge = np.array([input().split() for _ in range(N-1)], dtype = np.int64).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
Q, K = map(int,input().split())
XY = [list(map(int,input().split())) for _ in range(Q)]

distance_mat_K = dijkstra(graph, directed = False, indices = K-1)

for i in range(Q):
  print(int(distance_mat_K[XY[i][0]-1]+ distance_mat_K[XY[i][1]-1]))

### FIXED CODE ###

import sys
import numpy as np
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import defaultdict

N = int(input())
lines = readlines()
graph = defaultdict(list)
for line in lines[:N-1]:
  a,b,c = map(int,line.split())
  graph[a].append((b,c))
  graph[b].append((a,c))
Q, K = map(int,lines[N-1].split())
XY = np.array([line.split() for line in lines[N:]],np.int64)

def degreesOfSeparation(graph,start):
    if start not in graph:
        return -1
    visited = set()
    frontier = set()
    table = [0] * (len(graph) + 1)
    degrees = 0
    visited.add(start)
    frontier.add(start)
    while len(frontier) > 0:
        #print(frontier,":",degrees)
        #degrees += 1
        newfront = set()
        for g in frontier:
            for next in graph[g]:
                if next[0] not in visited:
                    visited.add(next[0])
                    newfront.add(next[0])
                    table[next[0]] += next[1] + table[g]
        frontier = newfront
    return table
table = degreesOfSeparation(graph,K)
for q in range(Q):
  print(table[XY[q][0]] + table[XY[q][1]])
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n , m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]

l = [[0 for i in range(n)] for i in range(n)]

a = np.array(l)

for i in range(m):
    l[ab[i][0 ]-1][ab[i][1]-1] = 1
    l[ab[i][1]-1][ab[i][0]-1] = 1

a = np.array(l)
d, p = shortest_path(a, return_predecessors=True, indices=0, method='D')

if float('inf') in d:
    print('No')
    

else:
    print('Yes')

for i in p[1:]:
    print(i+1)


### FIXED CODE ###

from collections import deque

n, m = map(int,input().split())
graph = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
ans = [0]*(n+1)
seen = [False]*(n+1)

que = deque()
que.append(1)

while len(que) != 0:
    k = que.popleft()
    seen[k] = True
    
    for i in graph[k]:
        if seen[i]:
            continue
        ans[i] = k
        que.append(i)
        seen[i] = True

ans = ans[2:]

for i in ans:
    if i == 0:
        print('No')
        exit()

print('Yes')

for i in ans:
    print(i)
### BUGGY CODE ###

A=list(map(int,input().split()))
C=[]
for i in range(int(A[1])):
    if i>=A[0]:
        for t in range (int(A[1])+1):
            if t>i:
                C.append(t*i%2019)
D=sorted(C)
print(D[0])

### FIXED CODE ###

l,r=list(map(int,input().split()))
f=True
C=2019
if (r-l)<2019:
    for i in range(l,r+1):
        if C==0:
            break
        for t in range(i+1,r+1):
            if t*i%2019<C:
                C=t*i%2019
                if C==0:
                    break
else:
    C=0
print(C)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 0

for i in range(n):
    minp = min(p[:i + 1])
    if p[i] <= minp:
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 0
minp = p[0]


for i in range(n):
    if p[i] <= minp:
        ans += 1
        minp = p[i]

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

N,M,V = list(map(int,input().split()))
A=list(map(int,input().split()))
B=list(map(int,input().split()))
S=list(map(int,A+B))
ans=0
time=0
K=sorted(S)
for i in range(N+M):
  if K[0]+time>V:
    print(ans)
    exit()
  elif i==N+M-1:
    print(N+M)
  else:
    time+=K[0]
    K.pop(0)
    ans+=1

### FIXED CODE ###

a,b,money=list(map(int,input().split()))
A=[0]+list(map(int,input().split()))
B=[0]+list(map(int,input().split()))
for i in range(1,a+1):
  A[i]+=A[i-1]
for j in range(1,b+1):
  B[j]+=B[j-1]
ans=0
b_cnt=b
for a_cnt in range(a+1):
  if A[a_cnt]>money:
    continue
  while A[a_cnt]+B[b_cnt]>money:
    b_cnt-=1
  ans=max(ans,a_cnt+b_cnt)
print(ans)
### BUGGY CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

def f3(n, h, a):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        hi = h[i]
        dp[hi] = max(dp[:hi]) + a[i]
    return(max(dp))

n = int(input()) # 1 <= n <= 2 x 10^5
h = [0] + list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
print(f3(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())
task = []
for i in range(n):
    a,b = map(int,input().split())
    task.append([b,a])
task.sort(reverse=True)
day = [i for i in range(1,m+1)]
salaly = 0
for k in range(n):
    for i in day:
        if task[k][1] <= i:
            day.remove(i)
            salaly += task[k][0]
            break
print(salaly)


### FIXED CODE ###

import heapq
from collections import defaultdict
n,m = map(int,input().split())
day = []
d = defaultdict(list)
for i in range(n):
    a,b = map(int,input().split())
    d[a].append(b)
task = []
cost = 0
heapq.heapify(task)
for i in range(1,m+1):
    for j in d[i]:
        heapq.heappush(task,-j)
        #print(task,j)
    if task != []:
        c = heapq.heappop(task)
        cost += (-1)*c  
print(cost)
### BUGGY CODE ###

import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(0, n+1)}
sizes = {i:1 for i in range(0, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, u):
	while (parent[u] != u):
		u = parent[u]
	return u
	return parent[u]

for a,b in friendships:
	if a != b:
		pa,pb = f(parent, a), f(parent, b)
		
		adj[a].add(b)
		adj[b].add(a)

		if pa != pb:
			parent[pb] = pa
			sizes[pa] += sizes[pb]

for c,d in disses:
	pc,pd = f(parent, c), f(parent, d)
	if (pc == pd):
		hd[c] += 1
		hd[d] += 1
"""
hd[u] = k
u has k disses in its connected component
"""

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])

### FIXED CODE ###

import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(0, n+1)}
sizes = {i:1 for i in range(0, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, u):
	if parent[u] != u: 
		parent[u] = f(parent, parent[u])
	return parent[u]

for a,b in friendships:
	if a == b: continue

	pa,pb = f(parent, a), f(parent, b)
	
	adj[a].add(b)
	adj[b].add(a)

	if pa != pb:
		if sizes[pa] >= sizes[pb]:
			parent[pb] = pa
			sizes[pa] += sizes[pb]
		else:
			parent[pa] = pb
			sizes[pb] += sizes[pa]

for c,d in disses:
	pc,pd = f(parent, c), f(parent, d)
	if (pc == pd):
		hd[c] += 1
		hd[d] += 1
"""
hd[u] = k
u has k disses in its connected component
"""

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])