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

from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
stage = ['#'+input()+'#' for i in range(h)]
stage = ['#'*(w+2)] + stage + ['#'*(w+2)]
queue = deque([(ch,cw)])
check = [(ch,cw)]
searched_temp = [(ch,cw)]
count = 0

while True:
  searched = searched_temp
  
  while len(queue):
    v = queue.popleft()
    if v == (dh,dw):
      print(count)
      exit()

    if stage[v[0]-1][v[1]] == '.' and (v[0]-1,v[1]) not in check:
      queue.append((v[0]-1,v[1]))
      check.append((v[0]-1,v[1]))
      searched.append((v[0]-1,v[1]))
    if stage[v[0]+1][v[1]] == '.' and (v[0]+1,v[1]) not in check:
      queue.append((v[0]+1,v[1]))
      check.append((v[0]+1,v[1]))
      searched.append((v[0]+1,v[1]))
    if stage[v[0]][v[1]-1] == '.' and (v[0],v[1]-1) not in check:
      queue.append((v[0],v[1]-1))
      check.append((v[0],v[1]-1))
      searched.append((v[0],v[1]-1))
    if stage[v[0]][v[1]+1] == '.' and (v[0],v[1]+1) not in check:
      queue.append((v[0],v[1]+1))
      check.append((v[0],v[1]+1))
      searched.append((v[0],v[1]+1))
  
  count += 1
  searched_temp = []
  for s in searched:
    for i in range(-2,3):
      for j in range(-2,3):
        y = s[0] + i
        x = s[1] + j
        if 1 <= y and y <= h and 1 <= x and x <= w and stage[y][x] == '.' and (y,x) not in check:
          check.append((y,x))
          queue.append((y,x))
          searched_temp.append((y,x))
  if len(queue) == 0:
    print(-1)
    break

### FIXED CODE ###

from collections import deque
 
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
stage = ['#'+input()+'#' for i in range(h)]
stage = ['#'*(w+2)] + stage + ['#'*(w+2)]
queue = deque([(ch,cw)])
check = [[1]*(w+2) for i in range(h+2)]
searched_temp = [(ch,cw)]
count = 0
 
while True:
  searched = searched_temp
  
  while len(queue):
    v = queue.popleft()
    if v == (dh,dw):
      print(count)
      exit()
 
    if stage[v[0]-1][v[1]] == '.' and check[v[0]-1][v[1]]:
      queue.append((v[0]-1,v[1]))
      check[v[0]-1][v[1]] = 0
      searched.append((v[0]-1,v[1]))
    if stage[v[0]+1][v[1]] == '.' and check[v[0]+1][v[1]]:
      queue.append((v[0]+1,v[1]))
      check[v[0]+1][v[1]] = 0
      searched.append((v[0]+1,v[1]))
    if stage[v[0]][v[1]-1] == '.' and check[v[0]][v[1]-1]:
      queue.append((v[0],v[1]-1))
      check[v[0]][v[1]-1] = 0
      searched.append((v[0],v[1]-1))
    if stage[v[0]][v[1]+1] == '.' and check[v[0]][v[1]+1]:
      queue.append((v[0],v[1]+1))
      check[v[0]][v[1]+1] = 0
      searched.append((v[0],v[1]+1))
  
  count += 1
  searched_temp = []
  for s in searched:
    for i in range(-2,3):
      for j in range(-2,3):
        y = s[0] + i
        x = s[1] + j
        if 1 <= y and y <= h and 1 <= x and x <= w:
          if stage[y][x] == '.' and check[y][x]:
            check[y][x] = 0
            queue.append((y,x))
            searched_temp.append((y,x))
          
  if len(queue) == 0:
    print(-1)
    break
### BUGGY CODE ###

# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#
from copy import deepcopy
h, w = map(int, input().split())
ss = [list(map(str, list(input()))) for i in range(h)]
flag = True
ans = 0
while (flag):
    flag = False
    s = deepcopy(ss)
    for i in range(h):
        for j in range(w):
            if (ss[i][j] == "#"):
                if i+1 < h:
                    s[i+1][j] = "#"
                if i-1 >= 0:
                    s[i-1][j] = "#"
                if j+1 < w:
                    s[i][j+1] = "#"
                if j-1 >= 0:
                    s[i][j-1] = "#"
            else:
                flag = True
    if (flag):
        ans += 1
    ss = deepcopy(s)

print(ans)


### FIXED CODE ###

# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#
from copy import deepcopy
from collections import deque

d = deque()
h, w = map(int, input().split())
s = [list(map(str, list(input()))) for i in range(h)]
used = [[True for j in range(w)] for i in range(h)]
# used = [[True]*w]*h
for i in range(h):
    for j in range(w):
        if (s[i][j] == "#"):
            d.append([i, j])
            used[i][j] = False


ans = -1
while (d):

    tmp = deque()
    while(d):
        i, j = d.popleft()

        if i+1 < h and used[i+1][j]:
            s[i+1][j] = "#"
            tmp.append([i+1, j])
            used[i+1][j] = False

        if i-1 >= 0 and used[i-1][j]:
            s[i-1][j] = "#"
            tmp.append([i-1, j])
            used[i-1][j] = False

        if j+1 < w and used[i][j+1]:
            s[i][j+1] = "#"
            tmp.append([i, j+1])
            used[i][j+1] = False

        if j-1 >= 0 and used[i][j-1]:
            s[i][j-1] = "#"
            tmp.append([i, j-1])
            used[i][j-1] = False

    d = tmp
    ans += 1

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

import fractions
a, b = map(int, input().split())
l = []
x = fractions.gcd(a, b)
i = 1
# while i * i <= x:
#     if x % i == 0:
#         l.append(i)
#         l.append(x//i)
#     i += 1
# table = list(set(l))
for i in range(1, int(x**0.5)+1):
    if x % i == 0:
        l.append(i)
        if i**2 == x:
            continue
        l.append(x//i)
table = l
ans = []
for i in range(len(table)):
    check = True
    for j in range(2, int(table[i]**0.5)+1):
        if table[i] % j == 0:
            check = False
    if check:
        ans.append(table[i])
print(len(ans))

### FIXED CODE ###

import fractions
a, b = map(int, input().split())
n = fractions.gcd(a, b)
i = 1
ass = [1]
for i in range(2, int(n**0.5)+1):
    while n % i == 0:
        ass.append(i)
        n = n//i
if n != 1:
    ass.append(n)
print(len(set(ass)))
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
 
a_spec = set(a) #aの種類
 
b = []
for i in a_spec:
  b.append(a.count(i))
 
b.sort()
 
d = len(a_spec) - k #減らす数字の種類
print(sum(b[0:d]))

### FIXED CODE ###

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

from collections import Counter
c = Counter(list(map(int, input().split())))

#Counterからの取り出し
l = []
m = []
for x, y in c.items():
    l += [y]
    m += [x]

L = sorted(l)
M = len(m)

cnt = 0 
if M <= k:
    print(0)
else:
    for i in range(M-k):
        cnt += L[i]
    print(cnt)
### BUGGY CODE ###

def z_algo(s):
    """https://www.youtube.com/watch?v=f6ct5PQHqM0
    """
    n = len(s)
    ret = [0] * n

    ref_frm, ref_tail = -1, -1  # 一番末尾まで探索したケースの起点と終点
    for frm in range(n):
        cont = max(0, min(ret[frm - ref_frm], ref_tail - frm)) if ~ref_frm else 0

        while (frm + cont < n) and (s[cont] == s[frm + cont]): cont += 1
        ret[frm] = cont
        if ref_tail < frm + cont:
            ref_tail = frm + cont
            ref_frm = frm
    return ret


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

    ret = 0
    t = ''
    for c in reversed(S):
        # zalgoは[0,i]の比較で
        # 先頭が固定されているので
        # 末尾から文字を増やしていくことで
        # 先頭をSの各文字にしている
        t = c + t
        lcp = z_algo(t)
        for diff, len_ in enumerate(lcp):
            ret = max(ret, min(diff, len_))
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

n = int(input())
s = input()

dp = [[0] * (n + 1) for _ in range(n + 1)]

res = 0
for i in range(n - 1, -1, -1):
    for j in range(n - 1, i, -1):
        if s[i] == s[j]:
            dp[i][j] = dp[i + 1][j + 1] + 1
            # dp[i][j] = max(dp[i][j], dp[i + 1][j + 1] + 1)
        res = max(res, min(dp[i][j], j - i))
print(res)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    inf = float('inf')
    dp = [inf] * n
    dp[0] = 0
    for i1 in range(1, n):
        #print(i1, dp)
        start = max(0, i1 - k)
        for i2 in range(start, i1):
            dp[i1] = min(dp[i1], dp[i2] + abs(h[i1] - h[i2]))
    print(dp[n - 1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

dp = [0] * n
for i in range(1, n):
  start = max(0, i - k)
  dp[i] = dp[start] + abs(h[start] - h[i])
  for j in range(start+1, i + 1):
    dp[i] = min(dp[i], dp[j] + abs(h[j]-h[i]))
  
print(dp[n-1])
### BUGGY CODE ###

h, w, d = map(int, input().split())
g = [[] for _ in range(w)]
for _ in range(h):
    tmp_list = list(map(int, input().split()))
    for i in range(w):
        g[i].append(tmp_list[i])
q = int(input())
qs = [list(map(int, input().split())) for _ in range(q)]
loc = [0]*(h*w+1)
for i in range(h):
    for j in range(w):
        loc[g[j][i]] = (i,j)
roots = [[0]*(h*w+1) for _ in range(d)]
for i in range(1,d+1):
    j = i + d
    while j < h*w+1:
        cost = abs(loc[j][0]-loc[j-d][0]) + abs(loc[j][1]-loc[j-d][1])
        roots[i-1][j] = cost + roots[i-1][j-d]
        j += d
for i in qs:
    l, r = i[0], i[1]
    print(roots[(l-1)%d][r] - roots[(l-1)%d][l])

### FIXED CODE ###

h, w, d = map(int, input().split())
g = [[] for _ in range(w)]
for _ in range(h):
    tmp_list = list(map(int, input().split()))
    for i in range(w):
        g[i].append(tmp_list[i])
q = int(input())
qs = [list(map(int, input().split())) for _ in range(q)]
loc = [0]*(h*w+1)
for i in range(h):
    for j in range(w):
        loc[g[j][i]] = (i,j)
roots = [0]*(h*w+1)
for i in range(1,d+1):
    j = i + d
    while j < h*w+1:
        cost = abs(loc[j][0]-loc[j-d][0]) + abs(loc[j][1]-loc[j-d][1])
        roots[j] = cost + roots[j-d]
        j += d
for i in qs:
    l, r = i[0], i[1]
    print(roots[r] - roots[l])
### BUGGY CODE ###

n = 50001
is_prime = [True for i in range(n)]
is_prime[0] = is_prime[1] = False
i = 2
while i**2 <= n:
    j = i*2
    while j < n:
        is_prime[j] = False
        j += i
    i += 1

cnt_pair = [0 for i in range(n)]
for i in range(n):
    if is_prime[i]:
        for j in range(i, n):
           if i + j >= n:
               break
           if is_prime[j]:
               cnt_pair[i + j] += 1

while True:
    n = int(input())
    if n == 0:
        break
    print(cnt_pair[n])



### FIXED CODE ###

n = 50001
is_prime = [i for i in range(n)]
is_prime[0] = is_prime[1] = 0
i = 2
while i**2 <= n:
    j = i*2
    while j < n:
        is_prime[j] = 0
        j += i
    i += 1

prime_set  = set(is_prime)
prime_set.remove(0)
prime_list = sorted(list(prime_set))

while True:
    cnt = 0
    n = int(input())
    if n == 0:
        break
    for i in prime_list:
        if i > n//2:
            break
        if n - i in prime_set:
            cnt += 1
    print(cnt)
### BUGGY CODE ###

from collections import deque

def main():
    K = int(input())
    if K <= 0:
        print(K)

    que = deque(range(1,10))
    # print(que)
    cnt = 9
    while True:
        x = que.popleft()
        mod = x % 10

        if mod != 0:
            que.append(10 * x + mod - 1)
            # print(que)
            cnt += 1
            if cnt == K:
                print(que[-1])
                return

        que.append(10 * x + mod)
        # print(que)
        cnt += 1
        if cnt == K:
            print(que[-1])
            return

        if mod != 9:
            que.append(10 * x + mod + 1)
            # print(que)
            cnt += 1
            if cnt == K:
                print(que[-1])
                return

main()


### FIXED CODE ###

from collections import deque

def main():
    K = int(input())
    if K <= 9:
        print(K)
        return

    que = deque(range(1,10))
    # print(que)
    cnt = 9
    while True:
        x = que.popleft()
        mod = x % 10

        if mod != 0:
            que.append(10 * x + mod - 1)
            # print(que)
            cnt += 1
            if cnt == K:
                print(que[-1])
                return

        que.append(10 * x + mod)
        # print(que)
        cnt += 1
        if cnt == K:
            print(que[-1])
            return

        if mod != 9:
            que.append(10 * x + mod + 1)
            # print(que)
            cnt += 1
            if cnt == K:
                print(que[-1])
                return

main()
### BUGGY CODE ###

import math
n,m=map(int,input().split())
a=list(map(int,input().split()))

for i in range(m):
  a=sorted(a,reverse=True)
  a[0]=math.floor(a[0]/2)
     
print(sum(a))


### FIXED CODE ###

import heapq as hq
n,m=map(int,input().split())
a=[-int(x) for x in input().split()]
hq.heapify(a)
for i in range(m):
    x=hq.heappop(a)
    x=-x//2
    hq.heappush(a,-x)
 
print(sum(a)*-1)
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[23]:


N = int(input())
L = sorted(list(map(int, input().split())))


# In[27]:


count = 0
for i in range(N):
    for j in range(i+1, N):
        #print(i, j)
        #print(L[i], L[j], L[i]+L[j])
        for k in range(j+1, N):
            #print(L[i], L[j], L[k], L[i]+L[j] > L[k])
            if L[i]+L[j] > L[k]:
                count += 1
print(count)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[9]:


import bisect


# In[10]:


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


# In[11]:


s_L = sorted(L)
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ans += bisect.bisect_left(s_L,s_L[i]+s_L[j])-j-1
print(ans)


# In[ ]:
### BUGGY CODE ###

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

ans = 0
A.sort()
B.sort()
#A_b:a以上のBのパーツ数。ソートしているのでそのままBのindexと対応が付く
A_b = [sum(b > a for b in B) for a in A] 
B_c = [sum(c > b for c in C) for b in B]

ans = sum(sum(B_c[N-x:]) for x in A_b) 
#aはB[i](i>N-x)の上に乗せられる。
#B[i]を乗せられるCのパーツ数はリストB_cにまとめてある。
print(ans)

### FIXED CODE ###

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

import bisect as bs
import numpy as np
A.sort()
C.sort()
#B_a:b未満のAのパーツ数、B_c:b超のCのパーツ数
B_a = np.array([bs.bisect_left(A,b) for b in B]) 
B_c = np.array([N-bs.bisect_right(C,b) for b in B])
ans = np.dot(B_a, B_c)
print(ans)
### BUGGY CODE ###

N = int(input())
l = [int(x) for x in input().split()]
l_dict = {k: v for v, k in enumerate(l)}
l.sort()

s = ""
for x in l:
    s = s + str(l_dict[x] + 1) + " "

print(s[:-1])

### FIXED CODE ###


N = int(input())
l = [int(x) for x in input().split()]
l_dict = {k: v for v, k in enumerate(l)}
l.sort()

for i, x in enumerate(l):
    if i == 0:
        print(l_dict[x] + 1, end="")
    else:
        print(" {}".format(str(l_dict[x] + 1)), end="")
### BUGGY CODE ###

n,q=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
ab = [list(map(int, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]
#print(ab)
#print(px)
ans= [[0 for i in range(n)] for i in range(n)]
ans2= [0 for i in range(n)]
for i in range(n):
    ans[i][i] = 1
for i in range(len(ab)):
    ans[ab[i][0]-1][ab[i][1]-1]+=1
for i in range(n):
    for j in range(i+1,n):
        if(ans[i][j]>0):
            for k in range(j,n):
                ans[i][k]+=ans[j][k]
for i in range(q):
    for j in range(n):
        ans2[j]+=px[i][1]* 1 if ans[px[i][0]-1][j] else 0
print(" ".join(list(map(str,ans2))))

### FIXED CODE ###

import collections

N,Q=map(int,input().split())
M=[[] for i in range(N+1)]
P=[0 for i in range(N+1)]
for i in range(N-1):
  a,b=map(int,input().split())
  M[a].append(b)
  M[b].append(a)
#print("M:",M)

S=[0 for i in range(N+1)]
for i in range(Q):
  p,x=map(int,input().split())
  S[p]+=x
#print(S)
  
d=collections.deque([1])

while len(d):
  dd=d.popleft()
  if P[dd]==0:
    P[dd]=1
    for i in M[dd]:
      if P[i]==0:
        S[i]+=S[dd]
      d.append(i)
  #print(d,S)
print(*S[1:])
### BUGGY CODE ###

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

result = 0

for i in range(n):
    kari = 0
    for j in range(i, n-1):
        if height[j] >= height[j+1]:
            kari += 1
        else:
            break

    if kari > result:
        result = kari

print(result)

### FIXED CODE ###

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

top = [0] + [i+1 for i in range(n-1) if height[i] < height[i+1] ]

result = [top[i+1]-top[i]-1 for i in range(len(top)-1)] + [(n-1)-top[len(top)-1]]

print(max(result))
### BUGGY CODE ###

x,k,d=map(int,input().split())

m=[]
n=[]

for i in range(1,k+1):
    a=d*i
    b=-d*i
    m.append(a)
    n.append(b)

mx=[]
for i in m:
    m1=x+i
    m2=abs(m1)
    mx.append(m2)

nx=[]
for i in n:
    n1=-1*(x+i)
    n2=abs(n1)
    nx.append(n2)

mxmin=min(mx)
nxmin=min(nx)

ans=min(mxmin,nxmin)

print(ans)

### FIXED CODE ###

import sys
x,k,d=map(int,input().split())

x=abs(x)

a=x//d

if a>=k:
    ans=x-k*d

elif (k-a)%2==0:
    ans=x-d*a

else:
    ans=x-d*a-d

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

import fractions

def main():
  x,y=map(int,input().split())
  mod=10**9+7

  if (2*x-y)%3==0 and (2*y-x)%3==0 and (2*x-y)>=0 and (2*y-x)>=0:
    a=(2*x-y)//3
    b=(2*y-x)//3
    #print(a,b)

    result=0.0
    bunbo=1
    bunshi=1

    for i in range(min(a,b)):
      bunbo=bunbo*(a+b-i)
      temp=1+i
      
      if bunbo%temp==0:
        bunbo=bunbo//temp
      else:
        bunshi=bunshi*(1+i)
      while bunbo%2==0 and bunshi%2==0:
        bunbo=bunbo//2
        bunshi=bunshi//2
      while bunbo%3==0 and bunshi%3==0:
        bunbo=bunbo//3
        bunshi=bunshi//3
      while bunbo%5==0 and bunshi%5==0:
        bunbo=bunbo//5
        bunshi=bunshi//5
      #print(bunbo,bunshi)
      f=fractions.gcd(bunbo,bunshi)
      bunbo=bunbo//f
      bunshi=bunshi//f
      
    result=bunbo//bunshi%mod
    print(int(result))

  else:
    print(0)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float('inf')
MOD=10**9+7
input=sys.stdin.readline

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



if (x+y)%3!=0:
    print(0)
    exit()

if x==0 and y==0:
    print(0)
    exit()


n=(2*y-x)//3
m=(2*x-y)//3


if m<0 or n<0:
    print(0)
    exit()

if n==0 and m==1:
    print(1)
    exit()
if n==1 and m==0:
    print(1)
    exit()
    

#n+mCm
#(n+m)!/m!


def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)



print(cmb(n+m, m, 10**9+7))
### BUGGY CODE ###

N=int(input())
H=tuple(map(int,input().split()))
A=tuple(map(int,input().split()))
class SegTreeMax:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[-self.INF]*(2*self.N0)
        self.d=[0]*N
    def update(self,i,x):
        self.d[i]=x
        i+=self.N0-1
        self.data[i]=x
        while i>0:
            i=(i-1)//2
            self.data[i]=max(self.data[i*2+1],self.data[i*2+2])
    def max(self,l,r):
        L = self.N0 + l; R = self.N0 + r
        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
s=SegTreeMax(N+1)
s.update(0,0)
for i,h in enumerate(H):
    m=s.max(0,h)
    s.update(h,m+A[i])
print(s.max(0,N+1))

### FIXED CODE ###

N=int(input())
H=tuple(map(int,input().split()))
A=tuple(map(int,input().split()))
class SegTreeMax:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[-self.INF]*(2*self.N0)
        self.d=[0]*N
    def update(self,i,x):
        self.d[i]=x
        i+=self.N0-1
        self.data[i]=x
        while i>0:
            i=(i-1)//2
            self.data[i]=max(self.data[i*2+1],self.data[i*2+2])
    def max(self,l,r):
        L = self.N0 + l; R = self.N0 + r
        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
s=SegTreeMax(N+1)
s.update(0,0)
for i,h in enumerate(H):
    m=s.max(0,h)
    s.update(h,m+A[i])
print(s.max(0,N+1))
### BUGGY CODE ###

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

inf = n * (10**4)
c = [inf] * n

c[0] = 0
c[1] = abs(h[1]-h[0]) + c[0]

for i in range(2,n):
    for j in range(1, k + 1):
        if i - j < 0:
            continue
        if c[i] < c[i-j]:
            continue
        c[i] = min(c[i], abs(h[i] - h[i-j]) + c[i-j])

print(c[n-1])


### FIXED CODE ###

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

inf = n * (10**4)
c = [inf] * n

c[0] = 0
c[1] = abs(h[1]-h[0]) + c[0]

for i in range(2,n):
    for j in range(1, k + 1):
        if i - j < 0:
            continue
        if c[i] < c[i-j]:
            continue
        c[i] = min(c[i], abs(h[i] - h[i-j]) + c[i-j])

print(c[n-1])
### BUGGY CODE ###

N = int( input() )

I = range( 1, N + 1 )
P = [ i for i in range(2, N + 1) ] + [ 1 ]

cnt = 0
for i in range( N ):
  cnt += I[ i ] % P[ i ]

print( cnt )

### FIXED CODE ###

N = int( input() )
print( N * ( N - 1 ) // 2 )
### BUGGY CODE ###

import itertools

N, A, B, C = map(int, input().split())
L = [int(input()) for n in range(N)]
P = []

for n in range(1, N + 1):
    P.extend(itertools.combinations([n for n in range(N)], n))

add_len = {s: sum(L[i] for i in s) for s in P}


def cost(v, s):
    return 10 * (len(s) - 1) + abs(v - add_len[s])


res = 2 << 30
for a in P:
    cost_a = cost(A, a)
    if res < cost_a:
        continue

    for b in P:
        cost_b = cost(B, b)
        if res < cost_b:
            continue

        if len(set(a) & set(b)):
            continue

        for c in P:
            cost_c = cost(C, c)
            if res < cost_c:
                continue

            if len(set(a) & set(c)) + len(set(b) & set(c)):
                continue
            res = min(res, cost(A, a) + cost(B, b) + cost(C, c))

print(res)


### FIXED CODE ###

import itertools

N, A, B, C = map(int, input().split())
L = [int(input()) for n in range(N)]
P = []

for n in range(1, N + 1):
    P.extend(itertools.combinations([n for n in range(N)], n))

add_len = {s: sum(L[i] for i in s) for s in P}


def cost(v, s):
    return 10 * (len(s) - 1) + abs(v - add_len[s])


res = 2 << 30
for a in P:
    cost_a = cost(A, a)
    if res < cost_a:
        continue

    for b in P:
        cost_b = cost(B, b)
        if res < cost_b:
            continue

        set_a = set(a)
        set_b = set(b)
        if len(set_a & set_b):
            continue

        for c in P:
            cost_c = cost(C, c)
            if res < cost_c:
                continue

            set_c = set(c)
            if len(set_a & set_c) or len(set_b & set_c):
                continue
            res = min(res, cost_a + cost_b + cost_c)

print(res)