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

import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n-1+m)]
tree_go = [[] for i in range(n+1)]
tree_come = [[] for i in range(n+1)]
excess = [0 for i in range(n+1)]
for a,b in ab:
  tree_go[a].append(b)
  tree_come[b].append(a)
for i in range(1,n+1):
  if tree_come[i] == []:
    root = i
  if len(tree_come[i]) > 2:
    excess[i] = len(tree_come[i])-1
que = deque([(root,0)])
parent = [0 for i in range(n+1)]
visited = [0 for i in range(n+1)]
while que:
  x,px = que.popleft()
  parent[x] = px
  if excess[x] >= 1:
    excess[x] -= 1
    continue
  for y in tree_go[x]:
    que.append((y,x))
print(*parent[1:],sep="\n")


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n-1+m)]
tree_go = [[] for i in range(n+1)]
tree_come = [[] for i in range(n+1)]
excess = [0 for i in range(n+1)]
for a,b in ab:
  tree_go[a].append(b)
  tree_come[b].append(a)
for i in range(1,n+1):
  if tree_come[i] == []:
    root = i
  if len(tree_come[i]) >= 2:
    excess[i] = len(tree_come[i])-1
que = deque([(root,0)])
parent = [0 for i in range(n+1)]
visited = [0 for i in range(n+1)]
while que:
  x,px = que.popleft()
  parent[x] = px
  if excess[x] >= 1:
    excess[x] -= 1
    continue
  for y in tree_go[x]:
    que.append((y,x))
print(*parent[1:],sep="\n")
### BUGGY CODE ###

mod = 998244353
from bisect import bisect_left
N = int(input())
xd = [list(map(int,input().split())) for _ in range(N)]
xd.sort()
X = [xd[i][0] for i in range(N)]
D = [xd[i][1] for i in range(N)]

class rmq(object):
    def __init__(self, N):
        self.N0 = 2**(N-1).bit_length()
        self.INF = 2**31-1
        self.data = [self.INF]*(4*self.N0)

    def update(self, k, x):
        k += self.N0-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])

    # [l,r)の最小値
    def query(self, l, r):
        L = l + self.N0; R = r + self.N0
        s = self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])

            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

tree = rmq(N)
for i in range(N-1,-1,-1):
    j = bisect_left(X,X[i]+D[i])
    tree.update(i,-i)
    tree.update(i,tree.query(i,j))

dp = [0]*(N+1)
dp[-1] = 1
for i in range(N-1,-1,-1):
    dp[i] += dp[i+1]
    dp[i] += dp[-tree.query(i,i+1)+1]
    dp[i] %= mod

print(dp[0])

### FIXED CODE ###

mod = 998244353
from bisect import bisect_left
from operator import itemgetter
N = int(input())
xd = [list(map(int,input().split())) for _ in range(N)]
xd.sort(key=itemgetter(0))
X = [xd[i][0] for i in range(N)]
D = [xd[i][1] for i in range(N)]

N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(4*N0) #長さが足りないことがある. 3*N0にすればいい?

# k番目の要素をxに更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

# [l,r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N-1,-1,-1):
    j = bisect_left(X,X[i]+D[i])
    update(i,-i)
    update(i,query(i,j))

dp = [0]*(N+1)
dp[-1] = 1
for i in range(N-1,-1,-1):
    dp[i] += dp[i+1]
    dp[i] += dp[-query(i,i+1)+1]
    dp[i] %= mod

print(dp[0])
### BUGGY CODE ###

H,W=map(int,input().split())
A=[[False]*(W+2)]+\
  [[i=="." for i in "#"+input()+"#"] for _ in range(H)] + \
  [[False]*(W+2)]

q=[[(i,j) for i in range(1,H+1) for j in range(1,W+1) if not A[i][j]]]

for k in range(2000):
    q.append([])
    f=True
    for i,j in q[k]:
        if A[i-1][j]:
            A[i-1][j]=False
            q[k+1].append((i-1,j))
            f=False
        if A[i+1][j]:
            A[i+1][j]=False
            q[k+1].append((i+1,j))
            f=False
        if A[i][j-1]:
            A[i][j-1]=False
            q[k+1].append((i,j-1))
            f=False
        if A[i][j+1]:
            A[i][j+1]=False
            q[k+1].append((i,j+1))
            f=False
    if f:
        break
print(k)

### FIXED CODE ###

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)
### BUGGY CODE ###

S = input()
Q = int(input())
querys = [input() for _ in range(Q)]
is_reverse = False

for q in querys:
    query = q.split()
    if len(query) == 1:
        is_reverse = not is_reverse
        continue
    _, f, c = query
    if is_reverse:
        
        if f == "1":
            S = S + c
        elif f == "2":
            S = c + S
    else:
        if f == "1":
            S = c + S
        elif f == "2":
            S = S + c
if is_reverse:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
querys = [input() for _ in range(Q)]
is_reverse = False
d = deque([S])

for q in querys:
    query = q.split()
    if len(query) == 1:
        is_reverse = not is_reverse
        continue
    _, f, c = query
    if is_reverse:
        
        if f == "1":
            d.append(c)
        elif f == "2":
            d.appendleft(c)
    else:
        if f == "1":
            d.appendleft(c)
        elif f == "2":
            d.append(c)
if is_reverse:
    print("".join(d)[::-1])
else:
    print("".join(d))
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int , input().split()))
for i in range(N):
    K =[]
    K.extend(A)
    K.pop(i)
    a = collections.Counter(K)
    S = len(list(set(K)))
    k = 0
    for j in range (S):
        b =a.most_common()[j][1]
        k = b * (b-1)/2 + k
    print(int(k))
    K.clear()
    K.extend(A)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int , input().split()))
a = collections.Counter(A)
k = 0
def comb(n):
    return n * (n - 1) // 2
for j in a.values():
    k += comb(j)
    
for i in range(N):
    s = A[i]
    p = a[s]
    print(int(k - p + 1))
### BUGGY CODE ###

N,K,Q = map(int,input().split(" "))
a=[]
a2={}

for i in range(Q):
  a.append(input())
  
for i in range(N):
  a2[i+1] = a.count(str(i+1))

for i in range(N):
  if a2[i+1] >= Q-K+1:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N,K,Q = map(int,input().split(" "))
a2={}
for i in range(Q):
  j = input()
  if j not in a2:
    a2[j] = 1
  else:
    a2[j] += 1
    
for i in range(N):
  if str(i+1) not in a2:
    a2[str(i+1)] = 0
  if a2[str(i+1)] >= Q-K+1:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys.stdout import flush

def inpl(): return tuple(map(int, input().split()))

def ismale(S):
    if S == "Male":
        return 1
    elif S == "Female":
        return 0
    else:
        exit()

N = int(input())
print(0)
flush()

c0 = ismale(input())
w = c0

C = [0 for _ in range(N)]
if c0 == 1:
    C[::2] = [1]*(N//2+1)
else:
    C[1::2] = [1]*(N//2)

L = 0
R = N - 1
post = (R - L + 1)//2
while True:
    print(post)
    flush()
    
    if post % 2 == 1:
        c = ismale(input())
        if c != w:
            L = post + 1
        else:
            R = post - 1
    else:
        c = ismale(input())
        if c != w:
            R = post
        else:
            L = post + 1

    if R - L == 2:
        print((R-L+1)//2)
        c = ismale(input())
        print(R)
        c = ismale(input())
        print(L)
        c = ismale(input())
    else:
        post = (R - L + 1)//2

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

def inpl(): return tuple(map(int, input().split()))

def ismale(S):
    if S == "Male":
        return 1
    elif S == "Female":
        return 0
    else:
        exit()

N = int(input())
print(0)
sys.stdout.flush()

c0 = ismale(input())
w = c0

C = [0 for _ in range(N)]

L = 0
R = N - 1
post = (R + L)//2
while True:
    print(post)
    sys.stdout.flush()
    
    if post % 2 == 1:
        c = ismale(input())
        if c != w:
            L = post + 1
        else:
            R = post - 1
    else:
        c = ismale(input())
        if c != w:
            R = post
        else:
            L = post

    if R - L == 2:
        print((R+L+1)//2)
        sys.stdout.flush()
        c = ismale(input())
        print(R)
        sys.stdout.flush()
        c = ismale(input())
        print(L)
        sys.stdout.flush()
        c = ismale(input())
    else:
        post = (R + L)//2
### BUGGY CODE ###

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

INF = 10 ** 12
dp = [INF] * 100010

dp[0] = 0

for i in range(1, N):
    for j in range(1, K+1):
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))

print(dp[N-1])


### FIXED CODE ###

INF = 105 * 10 ** 7
dp = [INF] * 100100

N, K = map(int, input().split())
h = list(map(int, input().split())) + [0] * 100

dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]))

print(dp[N-1])
### BUGGY CODE ###

n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort()

ans = 0
import queue
q=queue.Queue()


kaisuu = (xh[0][1] +a-1) // a
damege = kaisuu*a
ans += kaisuu
iti = xh[0][0] + 2*d
maedame = damege
skip =False
for i in range(1,n):
    while(iti < xh[i][0]):
        if skip:
            skip = False
            iti,damege = q.get()
            continue
        damege -= maedame
        if q.empty():
            skip =True
            break
        iti,maedame = q.get()
    if xh[i][1] - damege <= 0:
        continue
    kaisuu = (xh[i][1] - damege +a-1) // a
    damege += kaisuu*a
    q.put((xh[i][0] + 2*d, kaisuu*a))
    ans += kaisuu
print(ans)

### FIXED CODE ###

n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort()

import collections
pq=collections.deque()

ans = 0
totalDamage = 0


for i in range(n):
    x,h = xh[i]
    while len(pq) > 0 and pq[0][0] < x:
        totalDamage -= pq[0][1]
        pq.popleft()
    h -=totalDamage
    if h <= 0:
        continue
    num = (h + a -1) //a
    ans += num
    dam = num*a
    totalDamage += dam
    pq.append((x+2*d,dam))

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

import math
n = int(input())
a = list(map(int,input().split()))
list_S = []
ans = 0
for i in range(n+1):
    S = sum(a[0:i])
    list_S.append(S)
S_set = list(set(list_S))
for i in range(len(S_set)):
    I = list_S.count(S_set[i])
    if I <= 1:
        pass
    elif I == 2:
        ans += 1
    else:
        ans += math.factorial(I) // (math.factorial(I-2)*2)
print(ans)


### FIXED CODE ###

import math
n = int(input())
a = list(map(int,input().split()))
dic_S = {0:[0]}
S = 0
ans = 0
for i in range(n):
    S += a[i]
    if S not in dic_S:
        dic_S[S] = []
    else:
        pass
    dic_S[S].append(a[i])
    

for k in dic_S.keys():
    I = len(dic_S[k])
    if 3 <= I:
        ans += math.factorial(I) // (math.factorial(I-2)*2)
    elif I == 2:
        ans += 1
    else:
        pass
print(ans)
### BUGGY CODE ###

s = input()
K = int(input())

alp = 'abcdefghijklmnopqrstuvwxyz'
loc = []
ini = []
flg = 0
rem = 0
for i in alp:
    flg_2 = 0
    idx = 0
    for j in s:
        if j == i:
            if flg_2 == 0:
                flg_2 = 1
                ini.append(i)
                loc.append((idx, i))
                rem += len(s[idx:])
                if rem >= K:
                    flg = 1
            else:
                loc.append((idx, i))
        idx += 1
    if flg == 1:
        break

len_s = len(s)
list_rank = []
for i in ini:
    tmp = [j for j in loc if j[1] == i]
    for j in tmp:
        idx = j[0]
        for k in range(len_s-idx):
            if len(s[idx:idx+k+1]) <= K:
                if s[idx:idx+k+1] not in list_rank:
                    list_rank.append(s[idx:idx+k+1])
    if len(list_rank) >= K:
        break

list_rank.sort()

print(list_rank[K-1])


### FIXED CODE ###

s = input()
K = int(input())

ct = 0
alp = 'abcdefghijklmnopqrstuvwxyz'
for i in alp:
    ct += s.count(i)
    if ct >= K:
        break

key = i

list_rank = []
for i in range(len(s)):
    if s[i] > key:
        continue
    if i < len(s) - K + 1:
        for j in range(K):
            if s[i:i+j+1] not in list_rank:
                list_rank.append(s[i:i+j+1])
    else:
        for j in range(len(s)-i):
            if s[i:i+j+1] not in list_rank:
                list_rank.append(s[i:i+j+1])

list_rank.sort()
print(list_rank[K-1])
### BUGGY CODE ###

import fractions
from functools import reduce
n = int(input())
a = list(map(int, input().split()))
def lcm_base(x, y):
    return (x*y) // fractions.gcd(x, y)

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

l = lcm(list(set(a)))
mod = 10**9+7
total = 0
for i in a:
    total += l//i
    if total > mod:
        total %= mod
print(total)

### FIXED CODE ###

#GCD, LCM
def gcd_base(a, b):
    while b!=0:
        a, b = b, a%b
    return a

def lcm(num_list):
    ans = 1
    for i in num_list:
        ans = ans * i // gcd_base(ans, i)
    return ans

n = int(input())
a = list(map(int, input().split()))
l = lcm(a)
mod = 10**9+7
total = 0
for i in a:
    total += l//i
print(total%mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
 
 
N, K = list(map(int, input().split()))
ab = []
for i in range(N-1):
    ab.append(list(map(int, input().split())))
 
ki = []
 
for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []
 
for i in range(N-1):
    ki[ab[i][0] - 1]["eda"].append([ab[i][1] - 1])
    ki[ab[i][1] - 1]["eda"].append([ab[i][0] - 1])
 
def P(m ,n):
    if m <= 0 or n <= 0:
        return 0
    else:
        num = 1
        for i in range(n):
            num *= m-i
        return num
 
def saiki(i, base, ki):
    num = 1
    eda_num = len(ki[i]["eda"])-1
    if eda_num == 0:
        return num
    num *= P(K-2, eda_num)
 
    for edge in ki[i]["eda"]:
        if edge[0] != base:
            num *= saiki(edge[0], i, ki)
 
    num = num % 1000000007
    return num
 
total_num = K
if len(ki[0]["eda"]) != 0:
    total_num *= P(K-1, len(ki[0]["eda"]))
    for edge in ki[0]["eda"]:
        total_num *= saiki(edge[0], 0, ki)
        total_num = total_num % 1000000007
        if total_num == 0:
            break
 
print(total_num)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def isprime(n):
    for i in xrange(2, int(n ** 0.5)+1 ):
        if n % i == 0: return False
    return True


outList = []
for line in sys.stdin.readlines():
    List = map(int, line.strip().split())

    [a, b] = List

    # LCM
    LCM = 1
    for i in xrange(2, min(a, b)):
        if not isprime(i): continue
        while(a % i == 0 and b % i == 0):
            LCM *= i
            a /= i
            b /= i

    # GCD
    GCD = List[0] * b

    print LCM, GCD

### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def isprime(n):
    for i in xrange(2, int(n ** 0.5)+1 ):
        if n % i == 0: return False
    return True


outList = []
for line in sys.stdin.readlines():
    List = map(int, line.strip().split())

    [a, b] = List

    # LCM
    LCM = 1
    i = 1
    while( i <= min(a, b) ):
        i += 1
        if not isprime(i): continue
        while(a % i == 0 and b % i == 0):
            LCM *= i
            a /= i
            b /= i

    # GCD
    GCD = List[0] * b

    print LCM, GCD
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000)
INF = 1<<32


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):

    import itertools
    BC = list(itertools.chain.from_iterable([[C[i]] * B[i] for i in range(M)]))
    BC.sort(reverse=True)
    
    idx = 0
    A.sort()

    for i in range(N):
        if idx < len(BC) and A[i] < BC[idx]:
            A[i] = BC[idx]
            idx += 1

    print(sum(A))

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, A, B, C)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    x = [[B[i],C[i]] for i in range(M)]
    x = sorted(x, key=lambda x: -x[1])

    A.sort()

    dn = 0
    for b, c in x:
        for j in range(b):
            if(dn >= N):
                break
            if(A[dn] < c):
                A[dn] = c
                dn += 1
            else:
                break


    print(sum(A))

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]" 
    C = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, A, B, C)

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

def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  dist=[-1]*N
  dist[K]=0
  que=[K]
  while que:
    label=que.pop(0)
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist

N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=map(int,input().split())
distance=BFS(K-1,path,N)
for i in range(Q):
  x,y=map(int,input().split())
  print(distance[x-1]+distance[y-1])


### FIXED CODE ###

from sys import stdin
input = stdin.readline
from collections import deque
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  dist=[-1]*N
  dist[K]=0
  que=deque()
  que.append(K)
  while que:
    label=que.popleft()
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])
### BUGGY CODE ###

A, B, C, X, Y = tuple(map(int, input().split()))

# 大きな値で初期化
TOTAL_MIN = A * X + B * Y + C * (X+Y) * 2

if 2 * C < A:
    i_max = 0
else:
    i_max = X
if 2 * C < B:
    j_max = 0
else:
    j_max = Y

for i in range(i_max + 1):
    for j in range(j_max + 1):
        k = max(X - i, Y - j) * 2
        total_tmp = A * i + B * j + C * k
        if total_tmp < TOTAL_MIN:
            TOTAL_MIN = total_tmp

print(TOTAL_MIN)


### FIXED CODE ###

A, B, C, X, Y = tuple(map(int, input().split()))

# 大きな値で初期化
TOTAL_MIN = A * X + B * Y + C * (X+Y) * 2

for a in range(X + 1):
    c = (X - a) * 2
    if c // 2 < Y:
        if B < 2 * C:
            b = Y - c // 2
        else:
            b = 0
            c = max(c, Y * 2) 
    else:
        b = 0
    
    total_tmp = A * a + B * b + C * c
    if total_tmp < TOTAL_MIN:
        TOTAL_MIN = total_tmp
        

print(TOTAL_MIN)
### BUGGY CODE ###

#!/usr/bin/env python3

import heapq
import sys
input=sys.stdin.readline

def calc():
  h,w=map(int,input().split())
  sy,sx=map(int,input().split())
  gy,gx=map(int,input().split())
  board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
  costs=[[10**18]*(w+1) for _ in range(h+1)]
  costs[sy][sx]=0
  q=[]
  heapq.heappush(q,(0,sy,sx))
  while len(q)!=0:
    cost,y,x=heapq.heappop(q)
    if y==gy and x==gx:
      print(cost)
      exit()
    for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
      if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and costs[y+dy][x+dx]>costs[y][x]:
        costs[y+dy][x+dx]=costs[y][x]
        heapq.heappush(q,(cost,y+dy,x+dx))
    for dy in range(-2,3):
      for dx in range(-2,3):
        if dy==0 and dx==0:
          continue
        if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and costs[y+dy][x+dx]>costs[y][x]+1:
          costs[y+dy][x+dx]=costs[y][x]+1
          heapq.heappush(q,(cost+1,y+dy,x+dx))
  print(-1)
calc()

### FIXED CODE ###

#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])