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

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

n, m = map(int, input().split())
dic = defaultdict(list)
total = 0
candidates = []

for i in range(n):
    a, b = map(int, input().split())
    dic[a].append(b)

for day in range(1, m+1):
    if day in dic:
        candidates += dic[day]

    if candidates:
        fee = max(candidates)
        total += fee
        candidates.remove(fee)

print(total)

### FIXED CODE ###

import sys
import heapq
from collections import defaultdict
input = sys.stdin.readline

n, m = map(int, input().split())
dic = defaultdict(list)
total = 0
candidates = []
heapq.heapify(candidates)

for i in range(n):
    a, b = map(int, input().split())
    dic[a].append(b)

for day in range(1, m+1):
    if day in dic:
        for x in dic[day]:
            heapq.heappush(candidates, -x)

    if candidates:
        total -= heapq.heappop(candidates)

print(total)
### BUGGY CODE ###

def merge(a, left, mid, right):
    global x
    n1 = mid - left
    n2 = right - mid
    l = []
    r = [] 
    for i in range(n1):
        l.append(a[left + i])
    for i in range(n2):
        r.append(a[mid + i])
    l.append(float("inf"))
    r.append(float("inf"))
    i = 0
    j = 0
    for k in range(left,right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
            x += 1
        else :
            a[k] = r[j]
            j += 1
            x += 1

def mergeSort(a, left, right):
    if left+1 < right:
        mid = int((left + right)/2)
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)

n = int(input())
s = list(map(int,input().split()))
global x
x = 0
mergeSort(s,0,n)
print(*s)
print(x)




### FIXED CODE ###


def merge(a, left, mid, right):
    x = 0
    l = a[left:mid] + [float("inf")]
    r = a[mid:right] + [float("inf")]
    i = 0
    j = 0
    for k in range(left,right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else :
            a[k] = r[j]
            j += 1
        x += 1
    return x

def mergeSort(a, left, right,x):
    if left+1 < right:
        mid = int((left + right)/2)
        mergeSort(a, left, mid,x)
        mergeSort(a, mid, right,x)
        x[0] += merge(a, left, mid, right)

n = int(input())
s = list(map(int,input().split()))
x = [0]
mergeSort(s,0,n,x)
print(*s)
print(x[0])
### BUGGY CODE ###

s = input()
iteration = int(input())

for c in range(0,iteration):
    sousa = input().split()
    if sousa[0] == "1":
        s = s[:: -1]
    elif sousa[1] == "1":
        s = sousa[2] + s
    else:
        s = s + sousa[2]
print(s)


### FIXED CODE ###

from collections import deque
string = input()
s = deque(string)
iteration = int(input())
reverse = 1

for c in range(0,iteration):
    sousa = input().split()
    #操作１のとき
    if sousa[0] == "1":
        reverse = reverse*(-1)
    #操作２を行うとき
    elif sousa[1] == "1":
        if reverse == 1:
            s.appendleft(sousa[2])
        else:
            s.append(sousa[2])
    else:
        if reverse == 1:
            s.append(sousa[2])
        else:
            s.appendleft(sousa[2])

result = "".join(s)
if reverse == -1:
    result = result[::-1]


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

n = int(input())

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

q = int(input())

#初期化

a_dic ={}


for i in a:
    if i not in a_dic:
        a_dic[i] = i
    else:
        a_dic[i] += i

#a_sorted = sorted(a)
for i in range(q):
    ans = 0
    b,c = map(int, input().split())
    #print(a_dic)
    
    if b in a_dic:
        if c not in a_dic:
            a_dic[c] = a_dic[b]/b * c 

        else:
            tmp_c = a_dic[c]
            tmp_c += a_dic[b]/b*c
            a_dic[c] = tmp_c
        a_dic.pop(b) 
    print(int(sum(a_dic.values())))

### FIXED CODE ###

n = int(input())

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

q = int(input())

#初期化

a_dic ={}
ans = 0

for i in a:
    if i not in a_dic:
        a_dic[i] = 1
    else:
        a_dic[i] += 1
    
    ans += i

#print(ans)
#a_sorted = sorted(a)
for i in range(q):
    #ans = 0
    b,c = map(int, input().split())
    #print(a_dic)
    
    if b in a_dic:
        if c not in a_dic:
            a_dic[c] = a_dic[b]

        else:
            tmp_c = a_dic[c]
            tmp_c += a_dic[b]
            a_dic[c] = tmp_c
        tmp_a = (c-b) * a_dic[b]
        a_dic.pop(b)
        ans += tmp_a
    print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())
Q = int(input())


class Bit:
    """1-indexed"""

    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


en2asc = lambda s: ord(s) - 97

Bits = [Bit(N) for _ in range(26)]
for i, s in enumerate(S):
    Bits[en2asc(s)].add(i + 1, 1)

for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        i, c = int(q[1]), q[2]
        old = S[i - 1]
        Bits[en2asc(old)].add(i, -1)
        Bits[en2asc(c)].add(i, 1)
        S[i - 1] = c
    else:
        l, r = int(q[1]), int(q[2])
        ans = 0
        for b in Bits:
            ans += bool(b.sum(r) - b.sum(l - 1))
        print(ans)


### FIXED CODE ###

N = int(input())
S = list(input())
Q = int(input())


class Bit:
    """1-indexed"""

    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


en2asc = lambda s: ord(s) - 97

Bits = [Bit(N) for _ in range(26)]
for i, s in enumerate(S):
    Bits[en2asc(s)].add(i + 1, 1)

for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        i, c = int(q[1]), q[2]
        old = S[i - 1]
        Bits[en2asc(old)].add(i, -1)
        Bits[en2asc(c)].add(i, 1)
        S[i - 1] = c
    else:
        l, r = int(q[1]), int(q[2])
        ans = 0
        for b in Bits:
            ans += bool(b.sum(r) - b.sum(l - 1))
        print(ans)
### BUGGY CODE ###

def main():

    K = int(input())
    S = input()

    mod = pow(10, 9) + 7
    N = len(S)

    g1 = [1, 1]
    g2 = [1, 1]
    inv = [0, 1]

    for i in range(2, K+N+1):
        g1.append((g1[-1] * i) % mod)
        inv.append( ( -inv[mod % i] * (mod//i)) % mod )
        g2.append((g2[-1] * inv[-1]) % mod)

    def combi(n, r):
      r = min(r, n-r)
      return g1[n]*g2[r]*g2[n-r]%mod

    pow25 = [1]
    pow26 = [1]
    for i in range(K):
        pow25.append(pow25[-1] * 25 % mod)
        pow26.append(pow26[-1] * 26 % mod)

    ans = 0
    for i in range(N-1, N+K):
        ans += combi(i, N-1) * pow25[i-N+1] * pow26[K-i+N-1] % mod
        ans %= mod
    return ans

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

def main():

    K = int(input())
    S = input()

    mod = pow(10, 9) + 7
    N = len(S)

    g1 = [1, 1]
    g2 = [1, 1]
    inv = [0, 1]

    for i in range(2, K+N+1):
        g1.append((g1[-1] * i) % mod)
        inv.append( ( -inv[mod % i] * (mod//i)) % mod )
        g2.append((g2[-1] * inv[-1]) % mod)

    def combi(n, r):
      r = min(r, n-r)
      return g1[n]*g2[r]*g2[n-r]%mod

    pow25 = [1]
    pow26 = [1]
    for i in range(K):
        pow25.append(pow25[-1] * 25 % mod)
        pow26.append(pow26[-1] * 26 % mod)

    ans = 0
    for i in range(N-1, N+K):
        ans += combi(i, N-1) * pow25[i-N+1] % mod * pow26[K-i+N-1] % mod
        ans %= mod
    return ans

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

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

from_pos, from_neg = [], []
for i in range(N):
  if i%2 == 0:
    from_pos.append(alist[i])
    from_neg.append(-1*alist[i])
  else:
    from_pos.append(-1*alist[i])
    from_neg.append(alist[i])    

ans = []
for i in range(N):
  if i%2== 0:
    ans.append(sum(from_neg[:i])+sum(from_pos[i:]))
  else:
    ans.append(sum(from_pos[:i])+sum(from_neg[i:]))
print(*ans)

### FIXED CODE ###

N = int(input())
alist = list(map(int, input().split()))
m1, m2 = 0, 0
for i, a in enumerate(alist):
  if i == 0:
    m1+=a
    m2+=a
  elif i%2 == 0:
    m1+=a
    m2+=-1*a
  else:
    m1+=-1*a
    m2+=a    

ans = [m1, m2]
for i in range(2, N-1, 2):
  # index=i
  ans.append(ans[i-2] -2*alist[i-2] + 2*alist[i-1])
  # index=i+1
  ans.append(ans[i-1] - 2*alist[i-1] + 2*alist[i])

ans.append(ans[N-3] - 2*alist[N-3] + 2*alist[N-2])

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

N = input()
prime = 0

for _ in xrange(N):
    n = input()

    
    for i in xrange(2,n):
        if n%i == 0:
            break
    else:
        prime += 1

print prime

### FIXED CODE ###

N = input()
sum = 0
for _ in xrange(N):
    n = input()
    for i in xrange(2,n):
        if i > n/i:
            sum += 1
            break
        if n%i == 0:
            break
    else:
        sum += 1
print sum
### BUGGY CODE ###

"""
ビット演算, XOR

XORは桁ごとに独立して計算できるので、桁ごとに計算する
XORが1になるのは0と1を足した時。2つの数を足す時、一方の数のi桁目が1でもう一方の数のi桁目が0であれば、2つの数を足した時のi桁目が1になる
全部で数がn個あるとき、i桁目が1の数がx個ある場合は、i桁目が0の数がn-x個あることになるので、x*(n-x)個の組み合わせでi桁目のXORが1になる
"""

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

MOD = 10**9+7
ans = 0

for i in range(60):
    x = 0 # i桁目が1である数の個数
    for j in range(n):
        if a[j]>>i&1: # "a[j]のi桁目が1である"という意味
            x += 1
    now = x*(n-x)%MOD
    for j in range(i):
        now = now*2%MOD # 2**60をかけると容易にオーバーフローするので、安全に2をかけるごとにMODをとっている
    ans += now
    ans %= MOD
    
print(ans)

### FIXED CODE ###

"""
ビット演算, XOR

XORは桁ごとに独立して計算できるので、桁ごとに計算する
XORが1になるのは0と1を足した時。2つの数を足す時、一方の数のi桁目が1でもう一方の数のi桁目が0であれば、2つの数を足した時のi桁目が1になる
全部で数がn個あるとき、i桁目が1の数がx個ある場合は、i桁目が0の数がn-x個あることになるので、x*(n-x)個の組み合わせでi桁目のXORが1になる
"""

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

MOD = 10**9+7
ans = 0

for i in range(60):
    x = 0 # i桁目が1である数の個数
    for j in range(n):
        if a[j]>>i&1: # "a[j]のi桁目が1である"という意味
            x += 1
    now = x*(n-x)%MOD
    for j in range(i):
        now = now*2%MOD # 2**60をかけると容易にオーバーフローするので、安全に2をかけるごとにMODをとっている
    ans += now
    ans %= MOD
    
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())

ans = 0
for a in range(1, N+1):
    cnt = 0
    tmp = K - a % K
    if tmp > N:
        continue
    for b in range(tmp, N+1, K):
        if K - b % K != tmp:
            continue
        for c in range(tmp, N+1, K):
            cnt += 1
    ans += cnt

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())

ans = (N // K) ** 3

if K % 2 == 0:
    ans += ((N + K//2) //K) ** 3

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

mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n,k=mi()
h=li()
dp = [0]*n
for i in range(1,n):
    st = max(0,i-k)
    for j in range(st,i):
        if j == st:
            comp = dp[j]+abs(h[i] - h[j])
        else:
            comp = min(comp,dp[j]+abs(h[i] - h[j]))
    dp[i] = comp
print(dp[n-1])


### FIXED CODE ###

mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
import numpy as np
n,k=mi()
h=np.array(li())
dp = np.array([0]*n)
for i in range(1,n):
    st = max(0,i-k)
    dp[i] = min(dp[st:i]+abs(h[i] - h[st:i]))
print(dp[n-1])
### BUGGY CODE ###

import numpy as np
n=int(input())
a=list(map(int,input().split()))
a1=[]
a2=[]
for i in range(n):
  a1.append(i+1-a[i])
for i in range(n):
  a2.append(i+1+a[i])
count=0
p=0
q=1
while q<n:
  if a1[q]==a2[p]:
    count+=1
  p+=1
  if p==q:
    p=0
    q+=1
print(count)

### FIXED CODE ###

from collections import Counter
n=int(input())
alist=list(map(int,input().split()))
a1=[]
a2=[]
for i,a in enumerate(alist):
  a2.append(i-a)
  a1.append(i+a)
aa=Counter(a2)
count=0
for k in a1:
  count+=aa.get(k,0)
print(count)
### BUGGY CODE ###

#bitDP(再帰使用)
#forの組合せでやろうとすると男性の集合/女性の集合を分けるのが難しい

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

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

    #dp[s]：sは既に使った女性をbitで表していて、
    #          dp[s]は残りの男女の組合せの場合の数
    dp = [-1]*(1<<N)
    #全員相手が見つかった状態
    dp[-1] = 1

    #numは今見ている男性
    def dfs(s, num):
        #既にその状態を調べ終わっているなら返す
        if dp[s] != -1:
            return dp[s]

        #resは状態(s, num)において考えられる場合の数で
        #for文で全ての女性について考えて足している
        res = 0

        #状態sにおいて, 男性numと全ての女性とのマッチングを考える
        for i in range(N):
            #i番目の女性がまだ使っていなくて, 今見ている男性と相性が良い時
            if(s >> i) & 1 == 0 and a[num][i] == 1:
                #sを更新して, 次の男性について調べる
                #次の状態が既に調べ終わっていたらその場合の数が足される
                res += dfs(s+(1<<i), num+1)
        dp[s] = res % mod
        return dp[s]

    print(dfs(0, 0))

if __name__ == '__main__':
    main()

### FIXED CODE ###

#bitDP(再帰使用)
#forの組合せでやろうとすると男性の集合/女性の集合を分けるのが難しい

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

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

    #dp[s]：sは既に使った女性をbitで表していて、
    #          dp[s]は残りの男女の組合せの場合の数
    dp = [-1]*(1<<N)
    #全員相手が見つかった状態
    dp[-1] = 1

    #numは今見ている男性
    def dfs(s, num):
        #既にその状態を調べ終わっているなら返す
        if dp[s] != -1:
            return dp[s]

        #resは状態(s, num)において考えられる場合の数で
        #for文で全ての女性について考えて足している
        res = 0

        #状態sにおいて, 男性numと全ての女性とのマッチングを考える
        for i in range(N):
            #i番目の女性がまだ使っていなくて, 今見ている男性と相性が良い時
            if(s >> i) & 1 == 0 and a[num][i] == 1:
                #sを更新して, 次の男性について調べる
                #次の状態が既に調べ終わっていたらその場合の数が足される
                res += dfs(s+(1<<i), num+1)
        dp[s] = res % mod
        return dp[s]

    print(dfs(0, 0))

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

n=int(input())
a=list(map(int,input().split()))
b=[(v,s) for s,v in enumerate(a)]
b.sort(reverse=True)

dp=[[0 for i in range(n+1)] for i in range(n+1)]
for i in range(n+1):
    for j in range(n+1-i):
        if i+j==0:
            continue
        v=b[i+j-1][0]
        pos=b[i+j-1][1]
        if i==0:
            dp[0][j]=dp[0][j-1]+v*abs(n-j-pos)
        elif j==0:
            dp[i][0]=dp[i-1][0]+v*abs(i-1-pos)
        else:
            dp[i][j]=max(dp[i-1][j]+v*abs(i-1-pos),dp[i][j-1]+v*abs(n-j-pos))
ans=0
for i in range(n):
    happy=dp[i][n-i]
    if happy>ans:
        ans=happy
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[(v,s) for s,v in enumerate(a)]
b.sort(reverse=True)

dp=[[0 for i in range(n+1)] for i in range(n+1)]
for i in range(n+1):
    for j in range(n+1-i):
        if i+j==0:
            continue
        v=b[i+j-1][0]
        pos=b[i+j-1][1]
        if i==0:
            dp[0][j]=dp[0][j-1]+v*abs(n-j-pos)
        elif j==0:
            dp[i][0]=dp[i-1][0]+v*abs(i-1-pos)
        else:
            dp[i][j]=max(dp[i-1][j]+v*abs(i-1-pos),dp[i][j-1]+v*abs(n-j-pos))
ans=0
for i in range(n):
    happy=dp[i][n-i]
    if happy>ans:
        ans=happy
print(ans)
### BUGGY CODE ###

S = list(str(input()))
Q = int(input())
for i in range(Q):
    query = list(map(str,input().split()))
    if query[0] == '1':
        S.reverse()
    if query[0] == '2':
        if query[1] == '1':
            S.insert(0, query[2])
        else:
            S.append(query[2])
print(*S, sep = '')

### FIXED CODE ###

S = str(input())
Q = int(input())
s1 = ''
s2 = ''
reverse = False
for i in range(Q):
    query = list(map(str,input().split()))
    if query[0] == '1':
        if reverse == True:
            reverse = False
        else:
            reverse = True
    if query[0] == '2':
        if query[1] == '1':
            if reverse == False:
                s1 = query[2] + s1
            else:
                s2 = s2 + query[2]
        else:
            if reverse == True:
                s1 = query[2] + s1
            else:
                s2 = s2 + query[2]
S = s1 + S + s2
if reverse == True:
    S = S[::-1]
print(S)
### BUGGY CODE ###

import sys
mod = 10**9+7
N = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
B = []
ans = 0
for i in A:
    B.append(list(bin(i)[2:]))
C = [0 for i in range(60)]
for i in B:
    for l in range(len(i)):
        if i[-(l+1)] == '1':
            C[l] += 1
for i in range(60):
    t = C[i]
    ans = (ans + t*(N-t)*(2**i)) % mod
print(ans)

### FIXED CODE ###

import sys
mod = 10**9+7
N = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
B = []
ans = 0
C = [0 for i in range(60)]
for i in A:
    for l in range(60):
        if ((i >> l) & 1) == 1:
            C[l] += 1
for i in range(60):
    t = C[i]
    ans = (ans + t*(N-t)*(2**i)) % mod
print(ans)
### BUGGY CODE ###

def resolve():
    N = int(input())
    S = input()
    d = {}
    for i in range(N):
        key = S[i]
        for j in range(i, N):
            if j != i:
                key += S[j]
            d.setdefault(key, [])
            if len(d[key]) > 0:
                if d[key][-1][1] < i:
                    d[key].append((i, j))    
            else:
                d[key].append((i, j))
    #print(d)
    ans = 0
    for k, v in d.items():
        if len(v) > 1:
            ans = max(ans, len(k))
    print(ans)





if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    S = input()
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in reversed(range(N)):
        for j in reversed(range(N)):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
    
    ans = 0
    for i in range(N):
        for j in range(i, N):
            ans = max(min(dp[i][j], j-i), ans)
    print(ans)


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

n,k=map(int,input().split())
A=list(map(int,input().split()))
lst=[1]*n
for i in range(n):
  if i==0:
    lst[i]=A[i]
  elif 1<=i<=k-1:
    lst[i]=lst[i-1]*A[i]
  else:
    temp=lst[i-1]//A[i-k]
    lst[i]=temp*A[i]
    print("Yes" if lst[i]>lst[i-1] else "No")

### FIXED CODE ###

n,k=map(int,input().split())
A=list(map(int,input().split()))
for i in range(1, n-k+1):
    print("Yes" if A[i+k-1]>A[i-1] else "No")
### BUGGY CODE ###

N,M=input().split()
N =int(N)
M =int(M)
a= []
a= list(int(_) for _ in input().split())
dict={}
for i in range(N+1):
    p = sum(a[:i])%M
    if p not in dict:
        dict[p] = 1
    else:
        dict[p] += 1
ans_list =list(dict.values())
ans=0
for i in range(len(ans_list)):
    ans = ans + ans_list[i]*(ans_list[i]-1)/2
print(int(ans))

### FIXED CODE ###

N,M=input().split()
N =int(N)
M =int(M)
a= list(map(int,input().split()))
dict={}
ans = 0
p = 0
dict[0] = 1
for i in range(N):
    p = (p+a[i])%M
    if p not in dict:
        dict[p] = 1
    else:
        ans +=dict[p]
        dict[p] += 1
print(ans)
### BUGGY CODE ###

def solve(n, p_list):

    count = 1
    for i in range(n-1):
        target_num = p_list.pop()
        if min(p_list) > target_num:
            count += 1
    return count

if __name__ == "__main__":

    n = int(input())
    p_list = [int(i) for i in input().split()]
    ans = solve(n, p_list)
    print(ans)

### FIXED CODE ###

def solve(n, p_list):

    count = 0
    j = 2 * 10**5 +1
    for i in p_list:
        if j > i:
            count += 1
            j = i

    return count

if __name__ == "__main__":

    n = int(input())
    p_list = [int(i) for i in input().split()]
    ans = solve(n, p_list)
    print(ans)
### BUGGY CODE ###

H,W = map(int,input().split())
Ch, Cw = map(int,input().split())
Dh, Dw = map(int,input().split())
S = [list(input()) for _ in range(H)]

INF = H * W

def steppable(h,w):
    if not (h in range(H)) or not (w in range(W)):
        return False
    if S[h][w] == '#':
        return False
    else:
        return True

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0

# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0

# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop(0) # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        next_  = [
            (h[0] + 1, h[1], 0),
            (h[0] - 1, h[1], 0),
            (h[0], h[1] + 1, 0),
            (h[0], h[1] - 1, 0),]

        for n in next_:
            if steppable(n[0], n[1]) and num_step[n[0]][n[1]] > num_warp:
                queue.append(n)
                num_step[n[0]][n[1]] = num_warp

        # 魔法を使っていける場所を検討
        dx = [-2, -1 , 0, 1, 2]
        dy = [-2, -1 , 0, 1, 2]

        for x in dx:
            for y in dy:
                if steppable(h[0] + y, h[1] + x) and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] == num_warp
            queue.append((magic[0],magic[1]))

print(-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 _ in range(H)]

INF = H * W

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0

# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0

# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop() # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        for i in range(4):
            if 0 <= h[0]+dy[i] < H and 0 <= h[1]+dx[i] < W and S[h[0]+dy[i]][h[1]+dx[i]] == '.' \
                 and num_step[h[0]+dy[i]][h[1]+dx[i]] > num_warp:
                queue.append((h[0]+dy[i], h[1]+dx[i]))
                num_step[h[0]+dy[i]][h[1]+dx[i]] = num_warp

        # 魔法を使っていける場所を検討
        mx = [-2, -1 , 0, 1, 2]
        my = [-2, -1 , 0, 1, 2]

        for x in mx:
            for y in my:
                 if 0 <= h[0] + y < H and 0 <= h[1] + x < W and S[h[0] + y][h[1] + x] == '.' \
                     and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] = num_warp
            queue.append((magic[0], magic[1]))

print(-1)