Harryxun/stf_run huggingface dataset:
n = int(input())
p = [int(x) for x in input().split()]

count = 0
index = []

for i in range(n-1):
  if p[i] < p[i+1]:
    pass
  else:
    count += 1
    index.append(i)

if count == 0:
  print('YES')
elif count == 2:
  print('NO')
else:
  p[index[0]], p[index[1] + 1] = p[index[1] + 1], p[index[0]]
  sorted_p = sorted(p)
  if p == sorted_p:
    print('YES')
  else:
    print('NO')

### FIXED CODE ###

n = int(input())
p = [int(x) for x in input().split()]
 
count = 0
index = []
 
for i in range(n-1):
  if p[i] < p[i+1]:
    pass
  else:
    count += 1
    index.append(i)

if count == 0:
  print('YES')
elif count != 2:
  print('NO')
else:
  p[index[0]], p[index[1] + 1] = p[index[1] + 1], p[index[0]]
  sorted_p = sorted(p)
  if p == sorted_p:
    print('YES')
  else:
    print('NO')
target = int(input())
rest = 0
for i in range(1, int(target/2)):
  if target % i == 0:
	rest = target / i
    if rest < 10:
      break

if rest > 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

target = int(input())
rest = 0
for i in range(1, int(target/2)+2):
    if target % i == 0:
        rest = target / i
    if i < 10 and rest < 10:
        print("Yes")
        exit(0)
 
print("No")
import math
N=int(input())
print(math.factorial(N)%(7+1e9)

### FIXED CODE ###

import math
N=int(input())
print(math.factorial(N)%(7+10**9))
forecast = input()
actual = input()
count = 0

for i in range(len(forecast)):
  if forcast[i] = actual[i]:
    count += 1
print(count)

### FIXED CODE ###

forecast = input()
actual = input()
count = 0
 
for i in range(len(forecast)):
  if forecast[i] == actual[i]:
    count += 1
print(count)
n=int(input())
L=list(map(int,input().split()))

d=L[int(n/2)+1]-L[int(n/2)]


print(d)




### FIXED CODE ###

n=int(input())
L=list(map(int,input().split()))
L.sort()
d=L[n//2]-L[n//2-1]

print(d)
A, B = [int(input()) for _ in range(2)]
 
P = A + B
M = A - B
T = A * B
 
li = [P, M, T]
print(max(li))


### FIXED CODE ###

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

P = A + B
M = A - B
T = A * B

print(max(P, M, T))
import fractions
from functools import reduce
import copy

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
  
n = int(input())
A = list(int(i) for i in (input().split()))

red_list = list(set(A))

ans = 0
tmp = 0
reduce_num = 0
for i in range(len(red_list)):
  if( i != 0): red_list.append(reduce_num)
  reduce_num = red_list.pop(0)
  tmp = gcd_list(red_list)
  if(ans < tmp):
    ans = tmp

print(ans)

### FIXED CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
  
n = int(input())
A = list(int(i) for i in (input().split()))

front = []
end = []
for i in range(n):
  if(i == 0):
    front.append(gcd(*[A[0]]))
    end.append(gcd(*[A[n-1]]))
  else:
    front.append(gcd(*[front[i - 1],A[i]]))
    end.append(gcd(*[end[i - 1],A[n-1-i]]))

ans = 0
for i in range(n):
  if(i == 0):
    tmp = end[n-2]
  elif(i == n-1):
    tmp = front[n-2]
  else:
    tmp = gcd(*[front[i-1],end[n-2-i]])
  if(ans < tmp):
    ans = tmp
print(ans)
num = int(input())
nu_list = [int(v) for v in input().split()]
count = 0
#print(nu_list)
bool = True
while bool == True:
  for i in range(len(nu_list)):
    if nu_list[i] % 2 != 0:
      bool = False
      break
    else:
      nu_list[i] = nu_list[i] // 2
  if bool == True:
    count += 1 
print(count)

### FIXED CODE ###

st_list = list(input())
nu_list = [int(v) for v in st_list]
count = 0
for i in range(len(nu_list)):
  if nu_list[i] == 1:
    count += 1
print(count)
a=[]
for i in range(5):
  a.append(int(input()))
a.sort(key=x:lambda (x-1)%10)
b=0
for i in range(5):
  if i==1:
    b+=a[i]
  else:
    c=(a[i]+1)//10+1
    b+=c*10
print(b)

### FIXED CODE ###

a=[]
for i in range(5):
  a.append(int(input()))
a.sort(key=lambda x:(x-1)%10)
b=0
for i in range(5):
  if i==0:
    b+=a[i]
  else:
    c=(a[i]-1)//10+1
    b+=c*10
print(b)
a, b = input().split()
table = list(map(int(), b.split()))

print(min(table), average(table), max(table))





### FIXED CODE ###

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

print(min(data), max(data), sum(data))
N= int(input())
s = []

for _ in range(N):
    s.append(input())

for i in range(N):
    s[i] = tuple(sorted(s[i]))

import collections
c = collections.Counter(s)
d = [i for i in c.values()]

counter = 0
from math import factorial
for i in d:
    if i > 1:
        counter += factorial(i)/factorial(2)/factorial(i-2)

print(int(counter))   

### FIXED CODE ###

N= int(input())
s = []

for _ in range(N):
    s.append(input())

for i in range(N):
    s[i] = tuple(sorted(s[i]))

import collections
c = collections.Counter(s)
d = [i for i in c.values()]

counter = 0
from math import factorial
for i in d:
    if i > 1:
        counter += i*(i-1)/2

print(int(counter))
a,b,c=map(str,input().split())
e,f,g=map(str,input().split())
if a==g and b==f and c==e:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a,b,c=map(str,input().replace(""," ").split())
e,f,g=map(str,input().replace(""," ").split())
if a==g and b==f and c==e:
    print("YES")
else:
    print("NO")
i = list(map(int, input().split))
list = [-i[1]]*i[0]
for j in range(i[2]):
    list[int(input())-1] += 1

for ans in list:
    if ans > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

inp_list = list(map(int, input().split()))
n = inp_list[0]
k = inp_list[1]
q = inp_list[2]
ans_list = [k-q]*n
for i in range(q):
    ans_list[int(input())-1] += 1

for ans in ans_list:
    if ans > 0:
        print("Yes")
    else:
        print("No")
import sys
input = sys.stdin.readline
 
N,M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]
 
a2 = 1
a1 = 0 if 1 in A else 1
i = 1
def stair(stepb2,stepb1):
    global i
    i+=1
    step = stepb2 + stepb1
    
    if i in A:
        step = 0
    if i == N:
        print(step%1000000007)
        return step
    else:
        stair(stepb1,step)
_ = stair(a2,a1)

### FIXED CODE ###

n,m = map(int,input().split())
a = [ int(input()) for _ in range(m)]
M=10**9+7
lis = [1] + [0]*n

for i in a:
  lis[i]=-1
lis[1] += 1
for i in range(n-1):
  if lis[i+2]<0:
    lis[i+2]= 0
  else:
    lis[i+2] = (lis[i+1] + lis[i])%M
print(lis[n])
import numba
@numba.njit('(i8,)', cache=True)
def m(n):
    return sum(m*((n//m)**2+n//m-m**2) for m in range(1,int(n**.5)+1))

print(m(int(input())))

### FIXED CODE ###

n=int(input())
from math import sqrt,floor
x=floor(sqrt(n))
print(sum(m*(n//m+m)*(n//m+1-m) for m in range(1,floor(sqrt(n))+1))  -x*(x+1)*(2*x+1)//6)
from collections import defaultdict, deque
import sys
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []

    def merge(a, b, m):
        m = min(m, len(a) + len(b))
        res = [0] * m
        ia = len(a) - 1
        ib = len(b) - 1
        for i in range(m):
            j = m - 1 - i
            if a[ia] > b[ib]:
                res[j] = a[ia]
                ia -= 1
                if ia < 0:
                    while j >= 0:
                        res[j] = b[ib]
                        ib -= 1
                        j -= 1
                    return res
            else:
                res[j] = b[ib]
                ib -= 1
                if ib < 0:
                    while j >= 0:
                        res[j] = a[ia]
                        ia -= 1
                        j -= 1
                    return res
        return res

    for i in range(1, M + 1):
        current = ARR[i]
        if len(current) != 0:
            if len(q) != 0:
                if current[-1] > q[-1]:
                    res += current.pop()
                else:
                    res += q.pop()
            else:
                res += current.pop()
            q = sorted(q + current)
            q = merge(q, current, M - i)
            # q = q[-(M - i):]
        else:
            if len(q) != 0:
                res += q.pop()
            else:
                pass
        # q += current
        # q = sorted(q)
        # # print(q)
        # if len(q) != 0:
        #     mm = q.pop()
        #     res += mm
        # q = q[-(M - i):]
    print(res)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, deque
import sys
import heapq
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    # AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []
    for i in range(1, M + 1):
        current = ARR[i]
        for a in current:
            heapq.heappush(q, -a)
        if len(q) != 0:
            res -= heapq.heappop(q)
    print(res)


if __name__ == '__main__':
    main()
N = int(input())
A = list(map(int, input().split()))

def sunuke(b):
    ret = 0
    sub = 1
    for a in A:
        ret += abs(a - (b+ sub))
        sub += 1
    return ret


B = []

sub = 1
for a in A:
    b = a - sub
    B.append(b)
    sub += 1

B.sort()
b1 = N // 2
if N < 3:
    print(sunuke(B[b1]))
    exit()

b2 = b1 + 1
b1_s = sunuke(B[b1])
b2_s = sunuke(B[b2])
if b1_s < b2_s:
    print(b1_s)
else:
    print(b2_s)


### FIXED CODE ###

N = int(input())

if N % 2 == 0:
    print(N)
else:
    print(N * 2)
import math
def listint():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a
 
a,b,c = listint()
if a+b+2*math.sqrt(a*b) < c:
    print('Yes')
else:
    print('No')
import math
def listint():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a

a,b,c = listint()
if math.sqrt(a)+math.sqrt(b) < math.sqrt(c):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

a,b,c = input().split()
a = int(a)
b = int(b)
c = int(c)

if 4*a*b < (c - a - b)*(c-a-b) and a + b< c:
    print('Yes')
else:
    print('No')
import numpy as np 
inf = 10**18
n = int(input())
A = list(map(int,input().split()))
S = np.prod(A)
if A > inf;
	print("-1")
  else:
    print(S)

### FIXED CODE ###

N = int(input())
*A, = map(int,input().split())
max = 10**18
ans = 1
if 0 in A:
    print(0)
    exit()
for i in range(N):
    ans *= A[i]
    if ans > max:
        print(-1)
        exit()
print(ans)
import　fractions

n,m=map(int,input().split())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1,n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])


b = [int(i/2) for i in a]
ans2= b[0]
for i in range(1,n):
    ans2 = ans2 * b[i] // fractions.gcd(ans2, b[i])



### FIXED CODE ###

import fractions,sys

n,m=map(int,input().split())
a = list(map(int, input().split()))
# ans = a[0]
# for i in range(1,n):
#     ans = ans * a[i] // fractions.gcd(ans, a[i])
ff=[]
for j in  a:
    count=0
    for i in range(1,36):
        if j%(2**i)==0:
            count+=1
    ff.append(count)
ff=[i==ff[0] for i in ff]

 
b = [int(i/2) for i in a]
# b_list=[i%4==0 for i in b]
# bb=sum(b_list)
# if bb!=0 and bb!=n:
if all(ff)==False:
    print(0)
    exit()

ans2= b[0]
for i in range(1,n):
    ans2 = ans2 * b[i] // fractions.gcd(ans2, b[i])

# tf=[(ans2/i)%2==0 for i in b]
# and any(tf)
if ans2>m:
    print(0)
else:
    print((m-ans2)//(ans2*2)+1)
import sys
import numpy as np
input=sys.stdin.readline
s=input()
t=input()
n,m=len(s),len(t)

dp=[['']*(m+1) for i in range(n+1)]

for i in range(n):
  for j in range(m):
    if s[i]!=t[j]:
      x=len(dp[i+1][j])
      y=len(dp[i][j+1])
      if x>y:
        dp[i+1][j+1]=dp[i+1][j]
      else:
        dp[i+1][j+1]=dp[i][j+1]
    else:
      x=len(dp[i][j])+1
      y=len(dp[i+1][j])
      z=len(dp[i][j+1])
      tmp=max(x,y,z)
      if x==tmp:
        dp[i+1][j+1]=dp[i][j]+s[i]
      elif  y==tmp:
        dp[i+1][j+1]=dp[i+1][j]
      else:
        dp[i+1][j+1]=dp[i][j+1]
print(dp[n][m])
      

### FIXED CODE ###

import sys

input=sys.stdin.readline
s=input()
t=input()
n,m=len(s),len(t)

dp=[[0]*(m+1) for i in range(n+1)]
ans=[]

for i in range(n):
  for j in range(m):
    if s[i]!=t[j]:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
    else:
      dp[i+1][j+1]=dp[i][j]+1
      
i,j=n,m      
while i>0 and j>0:
  if s[i-1]==t[j-1]:
    ans.append(s[i-1])
    i-=1
    j-=1
  elif dp[i][j]==dp[i-1][j]:
    i-=1
  else:
    j-=1
print(''.join(ans[::-1]))
while 1:
	n,k = map(int,raw_input().split())
	if n == 0: break
	s = [0]*(n+1)
	c = sorted([int(raw_input()) for i in range(k)])
	p = min(0,C[0])
	pre = 0
	for i in c[p:]:
		s[i] = s[i-1] + 1
		if p and s[i-1] == 0:
			if s[i-2]:
				s[i] += s[i-2] + 1 - pre
				pre = s[i-2] + 1
			if s[i-2] == 0:
				pre = 0
	print max(s)

### FIXED CODE ###

while 1:
	n,k = map(int,raw_input().split())
	if n == 0: break
	s = [0]*(n+1)
	c = sorted([int(raw_input()) for i in range(k)])
	p = 1 if c[0] == 0 else 0
	pre = 0
	for i in c[p:]:
		s[i] = s[i-1] + 1
		if p and s[i-1] == 0:
			if s[i-2] > 0:
				s[i] += s[i-2] + 1 - pre
				pre = s[i-2] + 1
			if s[i-2] == 0:
				pre = 0
	print max(s)
# -*- coding: utf-8 -*-
# abc136/abc136_b
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    str_n = str(N)
    len_n = len(str_n)
    s = N - int('9' * (len_n - 1)) if len_n % 2 else 0
    for i in range(1, len_n, 2):
        s += 9 * 10**(i - 1)
    print(s)
    return

main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
# abc136/abc136_b
import sys
from math import log10

N = int(sys.stdin.readline().rstrip())
len_n = int(log10(N)) + 1
s = N - 10**(len_n - 1) + 1 if len_n % 2 else 0
for i in range(1, len_n, 2):
    s += 9 * 10**(i - 1)
print(s)
data = input()

if data[3] == data[4] and data[5] == data[6]:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

data = input()
 
if data[2] == data[3] and data[4] == data[5]:
  print("Yes")
else:
  print("No")
a,b = map(int,input().split())

p = [["."]*50 for _ in range(20)]
q = [["#"]*50 for _ in range(21)]

for t in range(b-1):
  p[t//25*2][t%25*2] = "#"
for t in range(a-1):
  q[t//25*2+1][t%25*2] = "."
  
print(41, 50)
for l in q:
  print("".join(l))
  


### FIXED CODE ###

a,b = map(int,input().split())

p = [["."]*100 for _ in range(20)]
q = [["#"]*100 for _ in range(21)]

for t in range(b-1):
  p[t//50*2][t%50*2] = "#"
for t in range(a-1):
  q[t//50*2+1][t%50*2] = "."
  
print(41, 100)
for l in p+q:
  print("".join(l))
# coding: utf-8

N = int(input())

F = []
P = []


table = [2**i for i in range(10)]

for i in range(N):
    lis = list(map(int, input().split()))
    F.append(lis)

for i in range(N):
    lis = list(map(int, input().split()))
    P.append(lis)

maxx = -1000000001

for i in range(1, 1025):
    total = 0
    for j in range(N):
        n = 0
        for t in range(10):
            n += (i&table[t])*F[j][t]
        total += P[j][n]
    if total > maxx:
        maxx = total

print(maxx)

### FIXED CODE ###

# coding: utf-8
N = int(input())

F = []
P = []

table = [2**i for i in range(10)]

for i in range(N):
    lis = list(map(int, input().split(' ')))
    F.append(lis)

for i in range(N):
    lis = list(map(int, input().split(' ')))
    P.append(lis)

maxx = -1000000001

for i in range(1, 1024):
    total = 0
    for j in range(N):
        n = 0
        for t in range(10):
            n += (1 if i&table[t] != 0 else 0)*F[j][t]
        total += P[j][n]
    if total > maxx:
        maxx = total

print(maxx)
import sys #追加
sys.setrecursionlimit(500*500)

def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return int(x)

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

LCM = lcm(A)

ans = 0
for a in A:
    ans += int(LCM/a)
    ans %= 1000000007

print(ans)

### FIXED CODE ###

import sys #追加
sys.setrecursionlimit(500*500)

def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return int(x)

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

LCM = lcm(A)

ans = 0
for a in A:
    ans += LCM//a

ans %= 1000000007

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

x = min(l)
print((int(n/x)+1) + 4)


### FIXED CODE ###


n = int(input())
l = []
for _ in range(5):
    l.append(int(input()))

x = min(l)

if n % x == 0:
    print(n // x + 4)
else:
    print(n // x + 5)
N = int(input())
A = list(map(int,input().split()))
A.sort()
print(abs(A[0]-A[-1]))

### FIXED CODE ###

x = int(input())

if x%2 == 0:
  print(x)
else:
  print(x*2)
#include <iostream>

using namespace std;

int main()
{
    long long n;
    scanf("%lld",&n);
    printf("%lld\n",n*(n-1)/2);
    return 0;
}


### FIXED CODE ###

n=int(input())
n-=1
print(n*(n+1)//2)
##############################################################################################################################################################################################################################
while True:
    s = input()
    if s == '.':break
    while True:
        index = min(max(0, s.find('+')), max(0, s.find('-')))
        if index == 0 and s[0] != '+' and s[0] != '-':
            index = s.rfind('[')
            if index == -1:
                break
            e = s[index:].find(']')
            s = s[:index] + s[index + 1:e][::-1] + s[e + 1:]
        else:
            e = index
            f = 0
            while s[e] == '+' or s[e] == '-':
                e += 1
                if s[e] == '+':
                    f += 1
                else:
                    f -= 1
            r = s[e]
            if r != '?':
                r = chr(ord(r) + f)
            s = s[:index] + r + s[e + 1:]
    print(s.replace('?','A'))


### FIXED CODE ###

while True:
    s = input()
    if s == '.':break
    while True:
        if s.find('+') == -1 and s.find('-') == -1:
            index = s.rfind('[')
            if index == -1:break
            e = s.find(']', index)
            s = s[:index] + s[index + 1:e][::-1] + s[e + 1:]
        else:
            index = s.find('+')
            if index == -1:
                index = s.find('-')
            if s.find('-') != -1:
                index = min(index, s.find('-'))
            e = index
            f = 0
            while s[e] == '+' or s[e] == '-':
                f += [-1, 1][s[e] == '+']
                e += 1
            r = s[e]
            if r != '?':
                r = chr((ord(r) - ord('A') + f) % 26 + ord('A'))
            s = s[:index] + r + s[e + 1:]
    print(s.replace('?', 'A'))
# ABC115D - Christmas
def burger(n):
    x = "P"
    for i in range(n):
        x = "B" + x + "P" + x + "B"
    return x


def main():
    N, X = tuple(map(int, input().split()))
    n_burger = burger(N)[:X]
    ans = n_burger.count("P")
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# ABC115D - Christmas
def burger(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    if x <= 1 + B[n - 1]:
        return burger(n - 1, x - 1)
    return burger(n - 1, x - 2 - B[n - 1]) + P[n - 1] + 1


def main():
    global B, P
    N, X = tuple(map(int, input().split()))
    B, P = [1], [1]  # burger, patty
    for i in range(N):
        B += [B[i] * 2 + 3]
        P += [P[i] * 2 + 1]
    ans = burger(N, X)
    print(ans)


if __name__ == "__main__":
    main()
n = int(input())

testimony_dict = {}
for i in range(n):
    a = int(input())
    testimony_dict[i + 1] = []
    for j in range(a):
        xy = input().split(' ')
        testimony_dict[i + 1].append(xy)

max_valid_bin = ''
for i in range(2 ** n - 1, 0, -1):
    is_valid = True
    bin_i = format(i, '0{}b'.format(n)
    for j in range(1, len(bin_i) + 1):
        if bin_i[j - 1] == '1':
            for xy_list in testimony_dict[j]:
                if bin_i[int(xy_list[0]) - 1] != xy_list[1]:
                    is_valid = False
    if is_valid:
        max_valid_bin = bin_i
        break

print(len([i for i in max_valid_bin if i == '1']))


### FIXED CODE ###

a, b, c = map(int, input().split(' '))
print('win') if a + b + c <= 21 else print('bust')
import numpy as np

N,W = map(int,input().split())
wv = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,W+1])

for i in range(1,N+1):
    for j in range(W+1):
        if j-wv[i-1][0]<0:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
print(int(dp[-1][-1])


### FIXED CODE ###

import numpy as np

N,W = map(int,input().split())
wv = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,W+1])

#　繰り返し回数節約
for i in range(1,N+1):
    dp[i][:wv[i-1][0]] = dp[i-1][:wv[i-1][0]]
    dp[i][wv[i-1][0]:] = np.maximum(dp[i-1][wv[i-1][0]:],dp[i-1][:W+1-wv[i-1][0]]+wv[i-1][1])
print(int(dp[-1,-1]))
# -*- coding: utf-8 -*-
a,b = map(str,input().split())
if (a = "H" and b = "H")or(a = "D" and b = "D"):
  print("H")
else:
  print("D")

### FIXED CODE ###

# -*- coding: utf-8 -*-
a,b = map(str,input().split())
if (a == "H" and b == "H")or(a =="D" and b == "D"):
  print("H")
else:
  print("D")
import copy
import sys
from collections import deque
H, W = map(int,input().split())
C_h, C_w = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
check_visited = [[False] * W for _ in range(H)]
dq = deque([0, C_h, C_w])
while dq:
   d, i, j = dq.popleft()
   if [i, j] == D:
      print(d)
      exit()
   if check_visited[i][j]:
      continue
   check_visited[i][j] = True
   for move_h, move_w in [[-1,0], [1,0], [0,-1], [0,1]]:
      i += move_h
      j += move_c
      if 0 =< i <= H-1 and 0 =< j <= W-1 and (not check_visited[i][j]) and S[i][j] == '.':
         dq.appendleft([d, i, j])
   for move_h in range(-2, 3):
      for move_c in range(-2, 3):
         if move_h, move_c == 0, 0:
            continue
         i += move_h
         j += move_c
         if 0 =< i <= H-1 and 0 =< j <= W-1 and (not check_visited[i][j]) and S[i][j] == '.':
            dp.append([d+1, i, j])
print(-1)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input().rstrip() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
dq = deque([(0, Ch, Cw)])
while dq:
    d, i, j = dq.popleft()
    if (i, j) == (Dh, Dw):
        print(d)
        exit()
    if visited[i][j]:
        continue
    visited[i][j] = True
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
            dq.appendleft((d, ni, nj))
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.' and not visited[ni][nj]:
                dq.append((d + 1, ni, nj))
print(-1)