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

M=10**9+7
mod =M
import sys
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table.append((i,c))
        i += 1
    if n > 1:
        table.append((int(n), 1))
    return table

from collections import defaultdict
N=input()
xs = map(int, input().split())
ys = []
d = defaultdict(int)
for x in xs:
    ps = prime_decomposition(x)
    psd = defaultdict(int)
    for p, c in ps:
        psd[p] = c
        d[p] = max(d[p], c)
    ys.append(psd)
r = 0
for ps in ys:
    t = 1
    for p in d:
        t = t*power(p,d[p]-ps[p])
    r = (r+t)
print(r%M)


### FIXED CODE ###

M=10**9+7
mod =M
import sys
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
NNN = (10**6)
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table.append((i,c))
        i += 1
    if n > 1:
        table.append((int(n), 1))
    return table

from collections import defaultdict
N=input()
xs = list(map(int, input().split()))
ys = []
d = defaultdict(int)
for x in xs:
    ps = prime_decomposition(x)
    psd = defaultdict(int)
    for p, c in ps:
        psd[p] = c
        d[p] = max(d[p], c)
    ys.append(psd)
g=1
for p in d:
    g=mul(g,p**(d[p])%M)%M
r=0
for x in xs:
    r = (r+mul(g,inverse[x]))%M
print(r%M)
### BUGGY CODE ###

# cook your code here
from sys import stdin
a = stdin.readline().strip()
l = len(a)
for i in xrange(l):
    a = a.replace('ST','')
print len(a)    

### FIXED CODE ###

# cook your code here
from sys import stdin
a = stdin.readline().strip()
l = len(a)
s = 0
t = 0
i = l-1
while i>=0:
    if a[i]=='T':
        t+=1 
    else:
        if t>0:
            t-=1 
        else:
            s+=1
    i-=1 
print s+t
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def main():
  MOD = 10**9+7
  n = int(input())
  T = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
  C = [[] for _ in range(n)]
  seen = [False]*n
  dp = [0]*n
  def dfs(v):
    cnt = 1
    seen[v] = True
    for nv in T[v]:
      if seen[nv]:
        continue
      C[v].append(nv)
      cnt += dfs(nv)
    dp[v] = cnt
    return cnt

  dfs(0)

  p = [1]*(n+1)
  inv = [1]*(n+1)
  inv_two = pow(2, MOD-2, MOD)
  for i in range(n):
    p[i+1] = p[i] * 2 % MOD
    inv[i+1] = inv[i] * inv_two % MOD
  ans = 0
  for i in range(n):
    s = 1
    t = 1
    cnt = 1
    for c in C[i]:
      l = dp[c]
      s *= inv[l]
      s %= MOD
      t += p[l] - 1
      t %= MOD
      cnt += l
    r = n - cnt
    s *= inv[r]
    s %= MOD
    t += p[r] - 1
    t %= MOD
    res = (1 - s*t) % MOD * inv_two
    res %= MOD
    ans += res
    ans %= MOD
  print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def main():
  MOD = 10**9+7
  n = int(input())
  T = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
  C = [[] for _ in range(n)]
  seen = [False]*n
  dp = [0]*n
  def dfs(v):
    cnt = 1
    seen[v] = True
    for nv in T[v]:
      if seen[nv]:
        continue
      C[v].append(nv)
      cnt += dfs(nv)
    dp[v] = cnt
    return cnt

  dfs(0)

  p = [1]*(n+1)
  inv = [1]*(n+1)
  inv_two = pow(2, MOD-2, MOD)
  for i in range(n):
    p[i+1] = p[i] * 2 % MOD
    inv[i+1] = inv[i] * inv_two % MOD
  ans = 0
  for i in range(n):
    s = 1
    t = 1
    cnt = 1
    for c in C[i]:
      l = dp[c]
      s *= inv[l]
      s %= MOD
      t += p[l] - 1
      t %= MOD
      cnt += l
    r = n - cnt
    s *= inv[r]
    s %= MOD
    t += p[r] - 1
    t %= MOD
    res = (1 - s*t) % MOD * inv_two
    res %= MOD
    ans += res
    ans %= MOD
  print(ans)

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

from collections import Counter
import math

def ncr(n, r):
  if r > n:
    return 0
  return math.factorial(n) // math.factorial(n-r) // math.factorial(r)

input()
As = list(map(int, input().split()))
counter = Counter(As)
res = {}
for k, v in counter.items():
  res[k] = (ncr(v, 2), ncr(v-1, 2))
total = sum(v[0] for k,v in res.items())
for a in As:
  v1, v2 = res[a]
  print(total - v1 + v2)

### FIXED CODE ###

from collections import Counter
import math

def ncr(n, r):
  if r > n:
    return 0
  return math.factorial(n) // math.factorial(n-r) // math.factorial(r)

input()
As = list(map(int, input().split()))
counter = Counter(As)
res = {}
total = 0
for k, v in counter.items():
  x = ncr(v, 2)
  res[k] = (x, (x * (v-2) // (v)))
  total += x
for a in As:
  v1, v2 = res[a]
  print(total - v1 + v2)
### BUGGY CODE ###

K, S = map(int, input().split())
x,y,z = 0,0,0
ans = 0

for i in range(K+1):
  x = i
  for j in range(K+1):
    y = j
    z = S - x - y
    if x + y + z == S and 0 <= x <= K and 0 <= y <= K and 0 <= z <= K:
      ans += 1
print(ans)

### FIXED CODE ###

K, S = map(int,input().split())
ans = 0

for i in range(K+1):
  for j in range(K+1):
    if 0<=S-i-j<=K:
      ans += 1
#    print(i, j, S-i-j, ans)
      

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

from itertools import accumulate
def is_prime(n):
   if n == 1:
       return False
   for i in range(2, int(n ** 0.5) + 1):
       if n % i == 0:
           return False
   return True

for _ in range(int(input())):
    l, r = map(int, input().split())
    c = [0] * (r + 1)

    check = []
    for i in range(l, r+1):
        if (i % 2 == 1):
            flg = (is_prime(i) and is_prime((i+1)/2))
        else:
            flg = 0
        check.append(flg)

    check = [0] + check
    check = list(accumulate(check))
    print(check[-1]-check[0])

### FIXED CODE ###

from itertools import accumulate
def is_prime(n):
   if n == 1:
       return False
   for i in range(2, int(n ** 0.5) + 1):
       if n % i == 0:
           return False
   return True

q = int(input())

l, r = [],[]
for _ in range(q):
    t, tt = map(int, input().split())
    l.append(t)
    r.append(tt)

m_r = max(r)

table = [0] * (m_r + 2)
for i in range(1, m_r + 1, 2):
    if is_prime(i) and is_prime((i + 1) // 2):
        table[i] = 1

c_table = list(accumulate(table))

for i in range(q):
    print(c_table[r[i]] - c_table[l[i]-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import heapq

INF = 10 ** 10

class Edge():
    def __init__(self, end, cost):
        self.end = end
        self.cost = cost

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for e in G[v]:
            if dist[e.end] > dist[v] + e.cost:
                dist[e.end] = dist[v] + e.cost
                heapq.heappush(h, (dist[e.end], e.end))
    return dist


H, W = map(int, input().split())
N = H * W
ch, cw = map(lambda x:int(x)-1, input().split())
gh, gw = map(lambda x:int(x)-1, input().split())

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

for h in range(H):
   s.append(input().rstrip('\n'))

for h in range(H):
    for w in range(W):
        if s[h][w] != '.':
            continue
        for dh in (-2, -1, 0, 1, 2):
            for dw in (-2, -1, 0, 1, 2):
                if dh == 0 and dw == 0:
                    continue
                nh = h + dh
                nw = w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W and s[nh][nw] == '.':
                    a = h*W+w
                    b = nh*W+nw
                    if (dh, dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
                        es[a].append(Edge(b, 0))
                    else:
                        es[a].append(Edge(b, 1))

dist = dijkstra(N, es, ch*W+cw)
if dist[gh*W+gw] == INF:
    print(-1)
else:
    print(dist[gh*W+gw])

### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq

INF = 10 ** 10

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for end, cost in G[v]:
            if dist[end] > dist[v] + cost:
                dist[end] = dist[v] + cost
                heapq.heappush(h, (dist[end], end))
    return dist


H, W = map(int, input().split())
N = H * W
ch, cw = map(lambda x:int(x)-1, input().split())
gh, gw = map(lambda x:int(x)-1, input().split())

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

for h in range(H):
   s.append(input().rstrip('\n'))

for h in range(H):
    for w in range(W):
        if s[h][w] != '.':
            continue
        a = h*W+w
        esappend = es[a].append
        for dh in (-2, -1, 0, 1, 2):
            for dw in (-2, -1, 0, 1, 2):
                if dh == 0 and dw == 0:
                    continue
                nh = h + dh
                nw = w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W and s[nh][nw] == '.':
                    b = nh*W+nw
                    if (dh, dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
                        esappend((b, 0))
                    else:
                        esappend((b, 1))

dist = dijkstra(N, es, ch*W+cw)
if dist[gh*W+gw] == INF:
    print(-1)
else:
    print(dist[gh*W+gw])
### BUGGY CODE ###

s = input()
q = int(input())
f = 1
for i in range(q):
  query = list(map(str, input().split()))
  if query[0] == '1':
    f *= -1
  else:
    if f == 1:
      if query[1] == '1':
        s = query[2] + s
      else:
        s += query[2]
    else:
      if query[1] == '1':
        s += query[2]
      else:
        s = query[2] + s
if f == -1:
  s = s[::-1]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
flag = 1
f = ''
b = ''
for i in range(q):
  query = list(map(str, input().split()))
  if query[0] == '1':
    flag *= -1
  else:
    if flag == 1:
      if query[1] == '1':
        f += query[2]
      else:
        b += query[2]
    else:
      if query[1] == '1':
        b += query[2]
      else:
        f += query[2]
ans = f[::-1] + s + b
if flag == -1:
  ans = ans[::-1]
print(ans)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
k = min(x * y * z, k)
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
a = a[:k]
b = b[:k]
c = c[:k]

def f(a, b):
    results = []
    cnt = 0
    for i in a:
        for j in b:
            cnt += 1
            results.append(i + j)
    return results
ab_results = f(a, b)
ab_results.sort(reverse=True)

results = f(c, ab_results[:k])
results.sort(reverse=True)

print("\n".join(map(str, results[:k])))


### FIXED CODE ###

import numpy as np
x, y, z, k = map(int, input().split())
k = min(x * y * z, k)
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))
c = np.array(list(map(int, input().split())))

ab = np.ravel(a + b[:, None])
ab.sort()
abc = np.ravel(c + ab[-k:, None])
abc.sort()
print(np.sum(abc[-k:][::-1].astype(str).astype(object) + "\n"), end="")
### BUGGY CODE ###

s = input()
q = int(input())

for _ in range(q):
    tmp = input().split(" ")
    if (len(tmp) == 1):
        s = s[::-1]
    else:
        t, f, c = tmp
        if (f == '1'):
            s = c + s
        else:
            s = s + c
print(s)

### FIXED CODE ###

import collections

d = collections.deque()
for i in input():
    d.append(i)
q = int(input())
is_head = True

for _ in range(q):
    tmp = input().split(" ")
    if (len(tmp) == 1):
        is_head = not is_head
    else:
        t, f, c = tmp
        if (f == '1'):
            if (is_head):
                d.appendleft(c)
            else:
                d.append(c)
        else:
            if (is_head):
                d.append(c)
            else:
                d.appendleft(c)

ans = ""
if is_head:
    while len(d) > 0:
        ans += d.popleft()
else:
    while len(d) > 0:
        ans += d.pop()
print(ans)
### BUGGY CODE ###

import sys
N=int(input())
print(0)
s=input()
if s=='Vacant':
  sys.exit()
a=s
print(N-1)
s=input()
if s=='Vacant':
  sys.exit()
left=0
right=N
while True:
  n=(left+right)//2
  print(n)
  s=input()
  if s=='Vacant':
    sys.exit()
  if n%2!=0:
    if s==a:
      right=n
    else:
      left=n
  else:
    if s!=x:
      right=n
    else:
      left=n

### FIXED CODE ###

import sys
N=int(input())
print(0)
s=input()
a=s
if s=='Vacant':
  sys.exit()
left=0
right=N
while True:
  n=(left+right)//2
  print(n)
  s=input()
  if s=='Vacant':
    sys.exit()
  if n%2!=0:
    if s==a:
      right=n
    else:
      left=n
  else:
    if s!=a:
      right=n
    else:
      left=n
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
    b=(a[i]*sum(a[i+1:n]))%1000000007
    ans=ans+b
d=ans%(1000000007)
print(d)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
c=sum(a)
for i in range(n):
    c=c-a[i]
    b=(a[i]*c)
    ans=ans+b
d=ans%(1000000007)
print(d)
### BUGGY CODE ###

l = input().split()
n1 = int(l[0])
n0 = int(l[1])
n = int(l[2])
k = int(l[3])

ans = 0

for i in range(n1):
    if k < 1:
        break
    k -= 1
    ans += 1

for i in range(n0):
    if k < 1:
        break
    k -= 1
    ans += 0

for i in range(n):
    if k < 1:
        break
    k -= 1
    ans -= 1 

print(ans)

### FIXED CODE ###

l = input().split()
n1 = int(l[0])
n0 = int(l[1])
n = int(l[2])
k = int(l[3])

ans = 0

if k >= n1:
    ans += n1

else:
    ans += k

k -= n1

k -= n0

if k > 0:
    ans -= k

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

L,R = map(int,input().split())

ans = 10 ** 12
for i in range(L,R):
    for j in range(i+1,R+1):
        ans = min(ans,((i%2019) * (j%2019))%2019)

print(ans)


### FIXED CODE ###

L,R = map(int,input().split())

ans = 10 ** 7

di = R//2019 - L//2019

L=L%2019
R=R%2019



if(di == 0):
    for i in range(L,R):
        for j in range(i+1,R+1):
            ans = min(ans, (i*j)%2019)

else:
    ans = 0


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

N, M = map(int,input().split()) 
P = [list(map(int,input().split())) for i in range(M)]
A = [ [0 for __ in range(N)] for _ in range(N)]
for path in P:
    A[path[1]-1][path[0]-1]=1
    A[path[0]-1][path[1]-1]=1
#print(A)
depth_list = [0 for _ in range(N)]
next_generation = set([0])
depth = 0
#old_generation = set()
direction = [0 for _ in range(N)]
used = [0 for _ in range(N)]
while len(next_generation)!=0:
    #print('next_gen',next_generation)
    current = next_generation
    for node in next_generation:
        used[node] = 1
    #[old_generation.add(node) for node in next_generation]
    next_generation = set()
    for index in current:
        depth_list[index]=depth
    for node in current:
        #print('node',node,':',A[node])
        
        #print('old',old_generation)
        for i,neighbor in enumerate(A[node]):
            #print("trm",neighbor)

            if neighbor == 1 and used[i]==0:
                #print("unseen",i)
                next_generation.add(i)
                direction[i]=node+1
    depth+=1
if used.count(1) != N:
    print('No')
else:
    print('Yes')
    for d in direction[1:]:
        print(d)
#print(depth_list)
        

### FIXED CODE ###

from collections import deque
N, M = map(int,input().split()) 
P = [list(map(int,input().split())) for i in range(M)]
A = [ [] for _ in range(N)]
#node_info = [{'node':d,'connect':[],'depth':-1,'dir':-1} for d in range(N)]

for path in P:
    A[path[1]-1].append(path[0]-1)
    A[path[0]-1].append(path[1]-1)
#print(A)

previous = [-1 for i in range(N)]
previous[0]=0

que = deque([0])

while len(que) != 0:
    v = que.popleft()
    for v_i in A[v]:
        if previous[v_i] != -1:
            continue
        else:
            que.append(v_i)
            previous[v_i] = v
for i in range(N):
    if previous[i] == -1:
        print('No')
        exit()
print('Yes')
for i in range(1,N):
    print(previous[i]+1)
### BUGGY CODE ###

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


T=list(map(int,input().split()))
S=[10**10]*(10**6)
DP=[10**10]*(10**6)

for i in range(N):
    S[i]=T[i]    

def chmin(a,b):
    if a>b:
        return b
    else:
        return a

def chmax(a,b):
    if a>b:
        return a
    else:
        return b

DP[0]=0
DP[1]=abs(S[1]-S[0])

for i in range(N):
    for j in range(1,K+1):
        DP[i+j]=chmin(DP[i]+abs(S[i+j]-S[i]),DP[i+j])
    
print(DP[N-1])


### FIXED CODE ###

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

L=list(map(int,input().split()))
S=[0]*110000
for i in range(N):
    S[i]=L[i]

DP=[10**12]*110000

DP[0]=0
for i in range(N):
    for j in range(1,M+1):
        if DP[i+j]>DP[i]+abs(S[i+j]-S[i]):
            DP[i+j]=DP[i]+abs(S[i+j]-S[i])



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

n,k=map(int,input().split())
h=sorted([int(input()) for _ in range(n)])
a=10**9
for i in range(n-k+1):
    a1=max(h[i:i+k])-min(h[i:i+k])
    a=min(a,a1)
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
h=sorted([int(input()) for _ in range(n)])
a=10**9
for i in range(n-k+1):
    a1=h[i+k-1]-h[i]
    a=min(a,a1)
print(a)
### BUGGY CODE ###

n,m = map(int, input().split())
A = sorted(list(map(int, input().split())),reverse=True)

def cnt(x):
    c = 0
    for j in reversed(range(len(A))):
        i = 0
        while i <n and A[j]+A[i]>=x:
            c += 1
            i += 1
    return c

def happiness(x):
    c = 0
    for j in reversed(range(len(A))):
        i = 0
        while i <n and A[j]+A[i]>=x:
            c += A[j]+A[i]
            i += 1
    return c

def binary_search(l, r):
    mid = (l+r)//2
    c = cnt(mid)
    if c < m:
        return binary_search(l, mid)   
    else:
        if l == mid:
            return(l, c-m)
        return binary_search(mid, r)

x, dm = binary_search(0, A[0]*2+1)
print(happiness(x)-dm*x)

### FIXED CODE ###

N, M = map(int, input().split())
A = sorted(list(map(int,input().split())), reverse=True)

# jとの組み合わせがx以上になるiの個数
def combinations(x):
  s = 0
  i = 0
  for j in reversed(range(N)):
    while i<N and A[i]+A[j]>=x:
      i += 1
    s += i
  return s
 
#↑のような組み合わせの合計幸福度
def koufukudo(x):
  s = 0
  si = 0
  i = 0
  for j in reversed(range(N)):
    while i<N and A[i]+A[j]>=x:
      si += A[i]
      i += 1
    s += si + A[j]*i  
  return s
 
#
def bsearch(l, u):
  m = (l+u)//2
  c = combinations(m)
#   print(f"m{m}, c{c},c-M{c-M}")
  if c<M:
    return bsearch(l, m)
  else:
    if l==m:
      return (l, c-M)
    return bsearch(m, u)
 
x, dm = bsearch(0, A[0]*2+1)
print(koufukudo(x)-dm*x)
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    import collections

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num for _ in range(W)] for _ in range(H)]

    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    from collections import deque

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num] * W for _ in range(H)]

    que = deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

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

import itertools
K,S = map(int,input().split())
print(sum([i+j+k==S for i,j,k in itertools.product(range(0,K+1),range(0,K+1),range(0,K+1))]))

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if 0 <= z <= k:
            count += 1
print(count)
### BUGGY CODE ###

N, Y = map(int, input().split())
number =[]
if N * 10000 >= Y and Y % 1000 == 0:
  Z = Y / 1000
  for x in range (0, N+1):
    for y in range (0, N+1):
      for z in range (0, N+1):
        if x + y +z == N and x*10000 + 5000*y + z*1000 == Y:
          number.append(x)
          number.append(y)
          number.append(z)

if len(number) >=3:
  print('{} {} {}'.format(number[0],number[1],number[2]))
else:
  print('-1 -1 -1')
  

### FIXED CODE ###

N, Y = map(int, input().split())
number =[]
for x in range (0, N+1):
  for y in range (0, N+1-x):
    z = N -x -y
    if z >= 0 and x*10000 + 5000*y + z*1000 == Y:
        number.append(x)
        number.append(y)
        number.append(z)

if len(number) >=3:
  print('{} {} {}'.format(number[0],number[1],number[2]))
else:
  print('-1 -1 -1')
### BUGGY CODE ###

h, n = map(int, input().split())
inf = 10**10
dp = [inf]*(h+1)
dp[0] = 0
for i in range(n):
    a, b = map(int, input().split())
    
    for j in range(h+1):
        if j- a>0:
            dp[j] = min(dp[j-a]+b, dp[j])
        else:
            dp[j]= min(dp[j], b)

print(dp[h])

### FIXED CODE ###

h, n = map(int, input().split())
inf = 10**10
dp = [inf]*(h+1)
dp[0] = 0
for i in range(n):
    a, b = map(int, input().split())
    
    for j in range(h+1):
        if j- a>0:
            dp[j] = min(dp[j-a]+b, dp[j])
        else:
            dp[j]= min(dp[j], b)

print(dp[h])