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

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

from collections import defaultdict

xs = sorted(A, reverse=True)

cs = defaultdict(int)

for x in xs:
    cs[x] += 1

result = 0

for x in xs:
    if cs[x]:
        for i in range(31, 0, - 1):
            m = 2**i
            y = m - x
            if x == y:
                if cs[y] >= 2:
                    cs[y] -= 2
                    result += 1
                    break
            else:
                if cs[y] >= 1:
                    cs[x] -= 1
                    cs[y] -= 1
                    result += 1
                    break

#print(cs)
print(result)


### FIXED CODE ###

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

xs = sorted(A, reverse=True)

cs = {}

for x in xs:
    cs[x] = cs.get(x, 0) + 1

result = 0

for x in xs:
    if cs[x]:
        for i in range(31, 0, - 1):
            m = 2**i
            y = m - x
            if y > x or y < 1:
                continue
            if y in cs:
                if x == y:
                    if cs[y] >= 2:
                        cs[y] -= 2
                        result += 1
                        break
                else:
                    if cs[y] >= 1:
                        cs[x] -= 1
                        cs[y] -= 1
                        result += 1
                        break

#print(cs)
print(result)
### BUGGY CODE ###

X,Y,Z,K = map(int, input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
A.reverse()
B.sort()
B.reverse()
C.sort()
C.reverse()


array = []
tmp = []

for a in A:
  for b in B:
    tmp.append(a+b)
tmp.sort()
tmp.reverse()

for i in tmp:
  for c in C:
    array.append(i+c)

array.sort()
array.reverse()

for i in range(K):
  print(array[i])

### FIXED CODE ###

from heapq import heappop, heappush,heapify
X,Y,Z,K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
H = []
heappush(H,[-1*(A[0]+B[0]+C[0]),0,0,0])
count = 1
memo = []
while H and count <= K:
  tmp,i,j,k = heappop(H)
  print(-1*tmp)
  count += 1
  if i+1 < X and ((i+1,j,k) not in memo):
    heappush(H,[-1*(A[i+1]+B[j]+C[k]),i+1,j,k])
    memo.append((i+1,j,k))
  if j+1 < Y and ((i,j+1,k) not in memo):
    heappush(H,[-1*(A[i]+B[j+1]+C[k]),i,j+1,k])
    memo.append((i,j+1,k))
  if k+1 < Z and ((i,j,k+1) not in memo):
    heappush(H,[-1*(A[i]+B[j]+C[k+1]),i,j,k+1])
    memo.append((i,j,k+1))
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    n, m = map(int, input().split())
    ac = []
    wa = []
    wa_count = 0
    for i in range(m):
        p, s = input().split()
        if p in ac:
            continue
        else:
            if s == 'AC':
                ac.append(p)
            else:
                wa.append(p)
    for a in ac:
        wa_count += wa.count(a)
    print(len(ac),wa_count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import numpy as np


def main():
    N, M = map(int, input().split())

    AC = np.array([0] * N)
    WA = np.array([0] * N)

    for i in range(M):
        p, S = input().split()

        if AC[int(p) - 1] == 0 and S == 'WA':
            WA[int(p) - 1] += 1
        else:
            AC[int(p) - 1] = 1
    print(sum(AC), sum(AC * WA))


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


n=int(input())
pre=[1]*(n//2+200)
pp=[1]*(n+1)
mod=998244353
for i in range(1,n//2+100):
    pre[i]=((pre[i-1]*2)%mod)
    
p=[1]*(n+1)
for i in range(n):
    p[i+1]=((p[i]*(i+1))%mod)
    pp[i+1]=pow(p[i+1],mod-2,mod)
tot=1
for i in range(n):
    tot*=3
    tot%=mod
#print(1)
#print(tot)
cc=0
for i in range(n//2+1,n+1):
    c=(((((p[n]*pp[i])%mod)*pp[n-i])%mod)*pre[n-i])%mod
    c%=mod
    cc+=c
tot-=cc
tot-=cc
tot%=mod
print(tot)


### FIXED CODE ###


n=int(input())
pre=[1]*(n//2+200)
pp=[1]*(n+1)
mod=998244353
for i in range(1,n//2+100):
    pre[i]=((pre[i-1]*2)%mod)
    
p=[1]*(n+1)
for i in range(n):
    p[i+1]=((p[i]*(i+1))%mod)
pp[-1] = pow(p[-1], mod - 2, mod)
 
for i in range(2, n + 1):
	pp[-i] = int((pp[-i + 1] * (n + 2 - i)) % mod)
tot=1
for i in range(n):
    tot*=3
    tot%=mod
#print(1)
#print(tot)
cc=0
for i in range(n//2+1,n+1):
    c=(((((p[n]*pp[i])%mod)*pp[n-i])%mod)*pre[n-i])%mod
    c%=mod
    cc+=c
tot-=cc
tot-=cc
tot%=mod
print(tot)
### BUGGY CODE ###

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

plist = list(map(int,input().split()))

maxval = 0


def expectedval(inp):
	return (1 + inp) * (inp/2) / inp

maxcomb = []
maxsum = 0
bestpos = 0

for i in range(n-(k-1)):
	summ = 0
	for j in range (k):
		summ += plist[i + j]
	if summ > maxsum:
		maxsum = summ
		bestpos = i

res = 0
for j in range (k):
	res += expectedval(plist[bestpos + j])

print(res)

### FIXED CODE ###

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

plist = list(map(int,input().split()))

maxval = 0

temp = -1

def expectedval(inp):
	return (1 + inp) /2

for i in range(n-(k-1)):
	# print(i, k)
	summ = 0
	if temp == -1:
		for j in range (k):
			summ += expectedval(plist[i + j])
		temp = summ
	else:
		# print(plist[i-1], plist[i+k -1], expectedval(plist[i - 1]), expectedval(plist[i + k - 1]))
		summ = temp - expectedval(plist[i - 1]) + expectedval(plist[i + k - 1])
		temp = summ
	# print(summ)
	maxval = max(summ, maxval)

print(maxval)
### BUGGY CODE ###

s=input()
a=int(s)
list=[]
list.append(1)
list.append(6)
list.append(9)
list.append(36)
list.append(81)
list.append(216)
list.append(729)
list.append(1296)
list.append(6561)
list.append(7776)
list.append(59049)
list.append(46656)
pp=[]
def money(x,y):
  for i in range(12):
    b=x//list[i]
    if x//list[i]==0:
      continue
    if i%2==1 and 0<b<6:
      if x%list[i]==0:
        pp.append(y+b)
      else:
        money(x-list[i],y+1)
    elif i%2==0 and i!=0 and 0<b<9:
      if x%list[i]==0:
        pp.append(y+b)
      else:
        money(x-list[i],y+1)
    else:
      if 0<b<6:
        pp.append(y+b)
money(a,0)
print(min(pp))

### FIXED CODE ###

s=input()
a=int(s)
list=[]
list.append(1)
list.append(6)
list.append(9)
list.append(36)
list.append(81)
list.append(216)
list.append(729)
list.append(1296)
list.append(6561)
list.append(7776)
list.append(59049)
list.append(46656)
pp=[]
def money(x,y):
  for i in range(12):
    b=x//list[i]
    if b==0:
      continue
    if i%2==1:
      if 0<b<6:
        if x%list[i]==0:
          pp.append(y+b)
        else:
          if y>20:
            break
          money(x-list[i],y+1)
    elif i%2==0:
      if i!=0:
        if 0<b<9:
          if x%list[i]==0:
            pp.append(y+b)
          else:
            if y>20:
              break
            money(x-list[i],y+1)
      else:
        if 0<b<6:
          pp.append(y+b)
money(a,0)
print(min(pp))
### BUGGY CODE ###

n, m = map(int, input().split())
c = []
a = []
for _ in range(m):
    ai, bi = map(int, input().split())
    ci = list(map(lambda x: 2 ** (int(x) - 1) , input().split()))
    a.append(ai)
    c.append(sum(ci))

INF = 100 ** 18
dp = [INF] * (2**n + 1)
dp[0] = 0
for i in range(m):
    for j in range(0, 2**n):
        dp[j | c[i]] = min(dp[j | c[i]], dp[j] + a[i])

ans = dp[2**n-1]
if ans == INF:
    print(-1)
    exit()
print(ans)



### FIXED CODE ###

n, m = map(int, input().split())
c = []
a = []
for _ in range(m):
    ai, bi = map(int, input().split())
    ci = list(map(lambda x: 2 ** (int(x) - 1) , input().split()))
    a.append(ai)
    c.append(sum(ci))

INF = 100 ** 18
dp = [INF] * (2**n + 1)
dp[0] = 0
for i in range(m):
    for j in range(0, 2**n):
        dp[j | c[i]] = min(dp[j | c[i]], dp[j] + a[i])

ans = dp[2**n-1]
if ans == INF:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    A = [0] * N
    for i in range(N):
        A[i] = [int(s) - 1 for s in readline().split()]

    M = N * (N - 1) // 2

    total_mathces = 0
    for day in range(M):
        matches = 0
        played = [False] * N
        for i in range(N):
            if played[i] or not A[i]:
                continue
            j = A[i][-1]
            if not played[j] and i == A[j][-1]:
                played[i] = True
                played[j] = True
                A[i].pop()
                A[j].pop()
                matches += 1

        if matches == 0:
            ans = -1
            break

        total_mathces += matches
        if total_mathces == M:
            ans = day + 1
            break

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    A = [0] * N
    for i in range(N):
        A[i] = [int(s) - 1 for s in readline().split()]

    M = N * (N - 1) // 2

    total_mathces = 0
    changed = set(range(N))
    for day in range(M):
        matches = 0
        changed_prev, changed = changed, set()
        for i in changed_prev:
            if i in changed or not A[i]:
                continue
            j = A[i][-1]
            if j not in changed and i == A[j][-1]:
                changed.add(i)
                changed.add(j)
                A[i].pop()
                A[j].pop()
                matches += 1

        if matches == 0:
            ans = -1
            break

        total_mathces += matches
        if total_mathces == M:
            ans = day + 1
            break

    print(ans)
    return


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

n,x,y = map(int,input().split())

import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

e = [[] for _ in range(n)]
for i in range(n-1):
    e[i].append((1, i+1))
    e[i+1].append((1, i)) # 有向グラフでは削除
e[x-1].append((1, y-1))
e[y-1].append((1, x-1))

d = [dijkstra(i) for i in range(n)]
d = [sorted(d[i]) for i in range(n)]

import bisect

for i in range(1,n):
    ans = 0
    for j in range(n):
        ans += bisect.bisect_right(d[j], i) - bisect.bisect_left(d[j], i)
    print(ans // 2)

### FIXED CODE ###

n,x,y = map(int,input().split())

import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

e = [[] for _ in range(n)]
for i in range(n-1):
    e[i].append((1, i+1))
    e[i+1].append((1, i)) # 有向グラフでは削除
e[x-1].append((1, y-1))
e[y-1].append((1, x-1))

d = [sorted(dijkstra(i)[i:]) for i in range(n)]

import bisect

for i in range(1,n):
    ans = 0
    for j in range(n):
        ans += bisect.bisect_right(d[j], i) - bisect.bisect_left(d[j], i)
    print(ans)
### BUGGY CODE ###

N = int(input())
S = str(input())
All = [i for i in range(1,N+1)]
R = []
G = []
B = []
for i in range(N):
    if S[i] == 'R':
        R.append(i+1)
    elif S[i] == 'G':
        G.append(i+1)
    else:
        B.append(i+1)
ans = 0
count = 0
for k in R:
    for j in G:
        for i in B:
            fr = 0
            ab = [k,j,i]
            ab.sort()
            if ab[2] - ab[1] == ab[1] - ab[0]:
                fr += 1

            if fr == 0:
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
N -= 1
S = str(input())
count = S.count('R') * S.count('G') * S.count('B')
for i in range(N):
    for j in range(i,N+1):
        k = 2*j - i
        if k > N:
            pass
        elif S[i] == S[j] or S[i] == S[k] or S[j] == S[k]:
            pass
        else:
            count -= 1
print(count)
### BUGGY CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
A = sorted(inpl())

#nCr
def comb(n,r):
    x = 1
    y = 1
    for i in range(r):
        x = x*(n-i)%mod #コンビネーションの分子
        y = y*(i+1)%mod #コンビネーションの分母
    return (x * pow(y, mod-2, mod) % mod)

ncr = [0]*(n+1)
for i in range(1,n+1):
    ncr[i] = comb(n-i,k-1)

ans = 0
for i in range(n):
    ans += (A[n-1-i] * ncr[i+1] - A[i] * ncr[i+1])
    ans %= mod

print(ans)


### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
A = sorted(inpl())

f=[1]
for i in range(1,n+1):
  f.append(f[-1]*i % mod)

#nCr
def comb(n,r):
    if n <= 0 or r <= 0:
        return 0
    x = f[n] % mod
    y = f[r] * f[n-r] % mod
    return (x * pow(y, mod-2, mod) % mod)

ans = 0
for i in range(n):
    c = comb(n-i-1,k-1)
    ans += A[n-1-i] * c - A[i] * c
    ans %= mod
    if c == 1:
        break

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

import math
from fractions import Fraction
mod = 998244353
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
pow2 = [2**i % mod for i in range(n + 1)]
used = [[False] * n for i in range(n)]
ret = (pow2[n] - 1 - n - n * (n - 1) / 2) % mod
for i in range(n):
    for j in range(i):
        if used[i][j]:
            continue
        inline = [i, j]
        for k in range(n):
            if k == i or k == j:
                continue
            if (p[i][1] - p[k][1]) * (p[j][0] - p[k][0]) == (p[j][1] - p[k][1]) * (p[i][0] - p[k][0]):
                inline.append(k)
        for k in range(len(inline)):
            for l in range(len(inline)):
                used[inline[k]][inline[l]] = True
        v = len(inline)
        ret = (ret + mod - pow2[v] + 1 + v + v * (v - 1) // 2) % mod
print(int(ret))


### FIXED CODE ###

import math
mod = 998244353
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
pow2 = [1]
for i in range(n):
    pow2.append(pow2[-1] * 2 % mod)
used = [[False] * n for i in range(n)]
ret = (pow2[n] - 1 - n - n * (n - 1) / 2) % mod
for i in range(n):
    for j in range(i):
        if used[i][j]:
            continue
        inline = [i, j]
        for k in range(n):
            if k == i or k == j:
                continue
            if (p[i][1] - p[k][1]) * (p[j][0] - p[k][0]) == (p[j][1] - p[k][1]) * (p[i][0] - p[k][0]):
                inline.append(k)
        for k in range(len(inline)):
            for l in range(len(inline)):
                used[inline[k]][inline[l]] = True
        v = len(inline)
        ret = (ret + mod - pow2[v] + 1 + v + v * (v - 1) // 2) % mod
print(int(ret))
### BUGGY CODE ###

from collections import deque
import sys

H, W = map(int, sys.stdin.readline().strip().split())
grid = [list(sys.stdin.readline().strip()) for _ in range(H)]
dq = deque([(0, 0, 1)])
while dq:
    h, w, cnt = dq.popleft()
    grid[h][w] = cnt
    nexts = [(h+1, w, cnt+1), (h-1, w, cnt+1), (h, w+1, cnt+1), (h, w-1, cnt+1)]
    for y, x, c in nexts:
        if 0 <= y and y < H and 0 <= x and x < W:
            if grid[y][x] == '.':
                dq.append((y, x, c))
            if type(grid[y][x]) == int and c < grid[y][x]:
                dq.append((y, x, c))

sharp_num = 0
max_num = 0
for h in range(H):
    sharp_num += grid[h].count('#')
if grid[-1][-1] == '.' or grid[-1][-1] == '#':
    print(-1)
else:
    print(H * W - grid[-1][-1] - sharp_num)





### FIXED CODE ###

import sys
from collections import deque
 
h,w = map(int, sys.stdin.readline().split())
maze = [list(sys.stdin.readline()) for _ in range(h)]
dis = [[-1 for _ in range(w)] for _ in range(h)]
 
que = deque()
que.append((0,0))
dis[0][0] = 1
 
while que:
    y,x = que.popleft()
    for dx, dy in ((1,0), (0,1), (-1, 0), (0, -1)):
        nx = x + dx
        ny = y + dy
        if (nx < 0) or (nx > w-1) or (ny < 0) or (ny > h-1): continue
        if (maze[ny][nx] == '.') and (dis[ny][nx] == -1):
            dis[ny][nx] = dis[y][x] + 1
            que.append((ny, nx))
 
ans = 0
black_num = 0
for m in maze:
    black_num += m.count('#')
 
if dis[h-1][w-1] == -1:
    ans = -1
else:
    ans = w*h - black_num - dis[h-1][w-1]
 
print(ans)
### BUGGY CODE ###

# ABC-139-D
N = int(input())

A = [i for i in range(1, N)]
print(sum(A))

### FIXED CODE ###

# ABC-139-D
N = int(input())

# TLEになった
# A = [i for i in range(1, N)]
# print(sum(A))

#sum(N) = ((N+1)*N)/2なのでこちらで実施。
print((N * (N-1))//2)
### BUGGY CODE ###

N = int(input())
P = [int(p) for p in input().split()]
# 先頭は必ずカウント
count = 1
for c in reversed(range(1, N)):
    min_num = min(P[:c])
    if min_num >= P[c]:
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
count = 0
min_num = N
for c in input().split():
    p = int(c)
    min_num = min(min_num, p)
    if min_num == p:
        count += 1
print(count)
### BUGGY CODE ###

import numpy as np
s = list(input())
mod = 1000000007
c = [1] + [0] * 3
for i in s:
    if i == 'A':
        c[1] = (c[1] + c[0]) % mod
    elif i == 'B':
        c[2] = (c[2] + c[1]) % mod
    elif i == 'C':
        c[3] = (c[3] + c[2]) % mod
    else:
        c[3] = (c[3] * 3 + c[2]) % mod
        c[2] = (c[2] * 3 + c[1]) % mod
        c[1] = (c[1] * 3 + c[0]) % mod
        c[0] *= 3
print(c[3])

### FIXED CODE ###

import numpy as np
s = list(input())
count = np.array([1] + [0] * 3).astype("int64")
for i in s:
    if i == 'A':
        count[1] += count[0]
    elif i == 'B':
        count[2] += count[1]
    elif i == 'C':
        count[3] += count[2]
    else:
        count[3] = count[3] * 3 + count[2]
        count[2] = count[2] * 3 + count[1]
        count[1] = count[1] * 3 + count[0]
        count[0] *= 3
    count %= 1000000007
print(count[3])
### BUGGY CODE ###

N,Q=(int(i) for i in input().split())
x=input()
a=[]
for i in range(0,Q):
  a.append([int(j) for j in input().split()])
  answer=0
  l=x[a[i][0]-1:a[i][1]]
  j=0
  while (j<len(l)-1):
    if (l[j]=="A"):
      if (l[j+1]=="C"):
        answer+=1
        j+=1
    j+=1
  print(answer)

### FIXED CODE ###

N,Q=(int(i) for i in input().split())
x=input()
a=[]

j=0
s=[0]
t=0
while (j<N-1):
  if (x[j]=="A") and (x[j+1]=="C"):
    t+=1
    s.append(t)
  else:s.append(t)
  j+=1
for i in range(0,Q):
  a.append([int(j) for j in input().split()])
  p=s[a[i][1]-1]-s[a[i][0]-1]
  print(p)
### BUGGY CODE ###

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0
 
while (que or que_warp):
    while (que):
        if count > 0:
            que_warp.append(que[0])
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)
 
print (res_S[Dh-1][Dw-1])

### FIXED CODE ###

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0
 
while (que or que_warp):
    l = len(que)
    while (que):
        if l > 0:
            que_warp.append(que[0])
            l -= 1
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)
 
print (res_S[Dh-1][Dw-1])
### BUGGY CODE ###

n,*a=map(int,open(0).read().split())
d=[0]*-~n
for h,a in zip(a,a[n:]):
 i,s=h,0
 while i:s=max(s,d[i]);i-=i&-i
 while h<=n:d[h]=max(d[h],s+a);h+=h&-h
print(max(d))

### FIXED CODE ###

class SegTree():
    def __init__(self,size,unit,f):
        self.size=size
        self.data=[unit for _ in range(2*size)]
        self.unit=unit
        self.f=f
    def update(self,i,x):
        c,f=self.data,self.f
        i+=self.size
        c[i]=f(c[i],x)
        while i>1:
            i>>=1
            c[i]=f(c[i+i],c[i-~i])
    def query(self,l,r):
        c,f=self.data,self.f
        x,y=self.unit,self.unit
        l+=self.size
        r+=self.size
        while l<r:
            if l&1:
                x=f(x,c[l])
                l+=1
            if r&1:
                r-=1
                y=f(c[r],y)
            l>>=1
            r>>=1
        return f(x,y)
def main():
    n,*a=map(int,open(0).read().split())
    dp=SegTree(n+1,0,lambda a,b:a if a>b else b)
    for h,a in zip(a,a[n:]):dp.update(h,dp.query(0,h)+a)
    print(dp.data[1])
main()