Harryxun/stf_run huggingface dataset:
import sys
def dfs(x, y, sym):
	tile[x][y] = "."
	for i in range(len(DX)):
		nx = x + DX[i]
		ny = y + DY[i]
		if (0<=nx and nx<N and 0<=ny and ny<M and tile[nx][ny] is sym):
			dfs(nx, ny, sym)

def solve():
	res = 0
	for i in range(N):
		for j in range(M):
			sym = tile[i][j]
			if tile[i][j] != ".":
				if tile[i][j] is sym:
					dfs(i, j, sym)
					res += 1
	print(res)

counter=0
DX = [-1, 0, 1, 0]
DY = [0, -1, 0, 1]
sys.setrecursionlimit(10**7)
while True:
	line = input()
	if ' ' in line:
		nums = line.split(" ")
		N = int(nums[0])
		M = int(nums[1])
		tile = [[0 for i in range(N)] for j in range(M)]
	else:
		tile[counter-1] = list(line)
	if N is 0 and M is 0:
		break
	if counter is M:
		solve()
		counter = 0
	counter += 1

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys
def dfs(x, y, sym):
	tile[x][y] = "."
	for i in range(len(DX)):
		nx = x + DX[i]
		ny = y + DY[i]
		if (0<=nx and nx<N and 0<=ny and ny<M and tile[nx][ny] is sym):
			dfs(nx, ny, sym)

def solve():
	res = 0
	for i in range(N):
		for j in range(M):
			sym = tile[i][j]
			if tile[i][j] != ".":
				if tile[i][j] is sym:
					dfs(i, j, sym)
					res += 1
	print(res)

counter=0
DX = [-1,0,1,0]
DY = [0,-1,0,1]
sys.setrecursionlimit(10**7)
while True:
	line = input()
	if " " in line:
		nums = line.split(" ")
		N = int(nums[0])
		M = int(nums[1])
		tile = [[0 for i in range(M)] for j in range(N)]
	else:
		tile[counter-1] = list(line)
	if N is 0 and M is 0:
		break
	counter += 1
	if counter-1 is N:
		solve()
		counter = 0
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
res = a[0]
for i in range(1, n):
    res += a[i]
    res /= 2
print(resz)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
res = a[0]
for i in range(1, n):
    res += a[i]
    res /= 2
print(res)
n=int(input())
a=[int(input()) for _ in range(n)]
aa=sorted(list(set(a[:])),reverse=True)
maxa=aa[0]
for i in range(n):
    if a[i] == maxa:
        print(aa[1])
    else:
        print(maxa)

### FIXED CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
aa=sorted(list(set(a[:])),reverse=True)
maxa=aa[0]
f=False if a.count(maxa) != 1 else True
for i in range(n):
    if a[i] == maxa and f:
        print(aa[1] if len(aa) != 1 else maxa)
    else:
        print(maxa)
a, b = map(int, input())

print( ((b-a) * (b-a) - b - a) / 2)

### FIXED CODE ###

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

print( ((b-a) * (b-a) - b - a) // 2)
a,b,k=map(int,input().split())
if (a,b)==(0,0):
  print(0,0)
  exit(0)
if(a-k<0):
  print (0,max(0,k-(b-a))
else:
        print(a-k,b)


### FIXED CODE ###

a, b, k = map(int, input().split())
if (a, b) == (0, 0):
    print(0, 0)
    exit(0)
if a - k < 0:
    print(0, max(0, b - (k-a)))
else:
    print(a-k, b)
def sum(N):
  N=str(N)
  return sum(list(map(int,N)))

t=0
n,a,b=map(int,input().split())
for i in range(n+1):
  if a<=sum(i)<=b:t+=i
print(t)

### FIXED CODE ###

def SUM(N):
  N=str(N)
  return sum(list(map(int,N)))

t=0
n,a,b=map(int, input().split())
for i in range(n+1):
  if a<=SUM(i)<=b:t+=i
print(t)
MOD = 1000000007
N, K = map(int, input().split())
edge = {}
for _ in range(N - 1):
    a, b = map(int, input().split())
    if a not in edge:
        edge[a] = set()
    edge[a].add(b)
    if b not in edge:
        edge[b] = set()
    edge[b].add(a)


def dig(par, parpar=None, depth=1):
    global ans
    children = edge[par] - set([parpar])
    if depth == 1:
        start = K - 1
    else:
        start = K - 2
    for i in range(len(children)):
        ans *= start - i
        ans %= MOD
    for c in children:
        dig(c, par, depth + 1)

ans = K
dig(1)
print(ans)


### FIXED CODE ###

MOD = 1000000007
N, K = map(int, input().split())
edge = {}
for _ in range(N - 1):
    a, b = map(int, input().split())
    if a not in edge:
        edge[a] = set()
    edge[a].add(b)
    if b not in edge:
        edge[b] = set()
    edge[b].add(a)


ans = K
q = [(1, None, 1)]
while len(q) > 0:
    par, parpar, depth = q.pop()
    if par not in edge:
        continue
    children = edge[par] - set([parpar])
    if len(children) == 0:
        continue
    if depth == 1:
        start = K - 1
    else:
        start = K - 2
    for i in range(len(children)):
        if start - i <= 0:
            ans = 0
            print(0)
            exit()
        else:
            ans *= start - i
        ans %= MOD
    for c in children:
        q.append((c, par, depth + 1))

print(ans)
a,b,q = map(int, input().split())

s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]

import bisect

for i in range(q):
    qq = int(input())
    sp = bisect.bisect(s,qq)
    tp = bisect.bisect(t,qq)
    s1 = s[sp-1]
    if sp <a:
        s2 = s[sp]

    t1 = t[tp-1]
    if tp <b:
        t2 = t[tp]
    print(min(abs(qq-s1)+abs(s1-t1),abs(qq-s1)+abs(s1-t2),
              abs(qq-s2)+abs(s2-t1),abs(qq-s2)+abs(s2-t2),
              abs(qq-t1)+abs(t1-s1),abs(qq-t1)+abs(t1-s2),
              abs(qq-t2)+abs(t2-s1),abs(qq-t2)+abs(t2-s2)))

### FIXED CODE ###

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

s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]

import bisect

for i in range(q):
    s2 = 10**12
    t2 = 10**12
    qq = int(input())
    sp = bisect.bisect(s,qq)
    tp = bisect.bisect(t,qq)
    s1 = s[sp-1]
    if sp <a:
        s2 = s[sp]

    t1 = t[tp-1]
    if tp <b:
        t2 = t[tp]
    print(min(abs(qq-s1)+abs(s1-t1),abs(qq-s1)+abs(s1-t2),
              abs(qq-s2)+abs(s2-t1),abs(qq-s2)+abs(s2-t2),
              abs(qq-t1)+abs(t1-s1),abs(qq-t1)+abs(t1-s2),
              abs(qq-t2)+abs(t2-s1),abs(qq-t2)+abs(t2-s2)))
d,g = map(int, input().split())
pd = [[int(i) for i in input().split()] for _ in range(d)]

ans = inf
for mask in range(1 << d):
  tmp = 0
  tmp1 = 0
  for j in range(d):
    if 1 << j & mask:
      tmp += pd[j][1]
      tmp += pd[j][0] * 100 * (j + 1)
      tmp1 += pd[j][0]
  for j in range(d-1,-1,-1):
    if not(1 << j & mask):
      if tmp + pd[j][0] * 100 * (j + 1) >= g:
        tmp = g
        tmp1 += (g - tmp) // (100 * (j + 1))
        break
      tmp1 += pd[j][0]
      tmp += pd[j][0] * 100 * (j + 1)
  if tmp >= g:
    ans = min(ans, tmp1)
print(ans)

### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    d, g = LI()
    pc = LIR(d)
    ans = float("INF")
    tokumono = list(itertools.product((0, 1), repeat=d))
    #print(tokumono)
    for toku in tokumono:
        #print(toku)
        ansa = 0
        ansb = 0
        for i in range(len(toku)):
            if toku[i] == 1:
                ansa += pc[i][0]
                ansb += pc[i][0] * (i + 1) * 100 + pc[i][1]
        for k in range(len(toku) - 1, -1, -1):
            if toku[k] == 0:
                for i in range(pc[k][0] + 1):
                    #print(ans, ansb, ansa)
                    if i == pc[k][0]:
                        ansb += pc[k][1]
                    if ansb >= g:
                        ans = min(ans, ansa)
                        break
                    ansa += 1
                    ansb += (k+1) * 100
                break

        

    print(ans)
            

    return

#D
def D():
    N, X = LI()
    def dfs(n, x):
        #print(n, x)
        if x == 1 and n > 0:
            return 0 
        elif x < 2 ** (n + 1) - 1:
            return dfs(n - 1, x - 1)
        elif x == 2 ** (n + 1) - 1:
            return 2 ** n 
        elif x == 2 ** (n + 2) - 3:
            return 2 ** (n + 1) - 1
        else:
            return dfs(n - 1, x - 2 ** (n + 1) + 1) + 2 ** n 
    a = dfs(N, X)
    print(a)
        
    return


#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()
import bisect
n,m=map(int,input().split())
def enum_dif(n):
    ret=[]
    i=1
    while i*i<=n:
        if(n%i==0):
            ret.append(i);
            if(i!=1 and i*i != n):
                ret.append(n//i)
        i+=1
    return ret
enum=enum_dif(m)
enum.sort()
# print(enum)
ind=bisect.bisect_left(enum,m//n)
if(enum[ind]==m//n):
    print(enum[ind])
elif(ind==0):
    print(enum[ind])
else:
    print(enum[ind-1])

### FIXED CODE ###

# import bisect
n,m=map(int,input().split())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

div=make_divisors(m)
ans=1
for i in range(len(div)):
    if(div[i]>m/n):
        break
    ans=max(div[i],ans)
print(ans)
# coding: UTF-8
from collections import deque
visited = set()
d = {}
arrow = {}
raw = input().split()
N = int(raw[0])
M = int(raw[1])

for i in range(1,N+1):
  arrow[i] = deque()
  d[i] = None

for i in range(M):
  raw = list(map(int,input().split()))
  L = raw[0]
  R = raw[1]
  D = raw[2]
  arrow[L].append((R,D))
  arrow[R].append((L,-D))

def dfsl(v):
  #矛盾が見つかればFalseを返す
  visited.add(v)
  while arrow[v]:
    w,cost = arrow[v].pop()
    
    if w not in visited:
      d[w] = d[v] + cost
      #print("not visited")
      #print([d[v],d[w],cost])
      return dfsl(w)
    else:
      if d[w] != d[v] + cost:
        #print("visited")
        #print([d[v],d[w],cost])
        return False
  return True

ans = True
for u in range(1,N+1):
  if u not in visited:
    d[u] = 0
    ans = dfsl(u)
    if not ans:
      break
    else:
      continue

if ans:
  print("Yes")
else:
  print("No")     
      

### FIXED CODE ###

# coding: UTF-8
from collections import deque
N,M = map(int,input().split())
link = [ [] for _ in range(N+1)]
value = [ -1 for _ in range(N+1)]

for _ in range(M):
  L,R,D = map(int,input().split())
  link[L].append((R,D))
  link[R].append((L,-D))

searched = set()
queue = deque()
for u in range(N+1):
  if u not in searched:
    queue.append(u)
    searched.add(u)
    value[u] = 0
    while queue:
      v = queue.popleft()
      for w,d in link[v]:
        if w not in searched:
          value[w] = value[v] + d
          queue.append(w)
          searched.add(w)

#verification
for v in range(N+1):
  for w,d in link[v]:
    if value[w] != value[v] + d:
      print("No")
      exit()
print("Yes")
t = int(input()):

if 30 <= t <=40 :
 print("Yes")
if -40 <= t < 30:
  print("No")
  

### FIXED CODE ###

t = int(input())

if 30 <= t <=40 :
	print("Yes")
if -40 <= t < 30 :
	print("No")
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

result = 0

hasuu = [item % 10 for item in [A, B, C, D, E] if item % 10 != 0]

for item in [A, B, C, D, E]:
  if item % 10 == 0:
    result += item 
  else:
    result += (item // 10 + 1) * 10
    
result = int(result - 10 + min(hasuu))
print(result)

### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

result = 0

hasuu = [item % 10 for item in [A, B, C, D, E] if item % 10 != 0]

for item in [A, B, C, D, E]:
  if item % 10 == 0:
    result += item 
  else:
    result += (item // 10 + 1) * 10
    
if hasuu != []:
  result = int(result - 10 + min(hasuu))

print(result)
S = input()
RD = weather.count('R')
if RD < 2:
    print(RD)
else:
    if S[1] == 'R':
        print(RD)
    else:
        print(1)

### FIXED CODE ###

weather = input()
rainyDay = weather.count('R')
if rainyDay < 2:
    print(rainyDay)
else:
    if weather[1] == 'R':
        print(rainyDay)
    else:
        print(1)
N=int(input())
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
dp=[1]*(ma+1)
ans=0

for i in range(N-1):
  p=dp[i]
  if dp[i]==1:
    for q in range(ma//p+1):
      dp[p*q]=0
    if dp[i]!=dp[i+1]:
      ans+=1
if dp[ma]==1:
  ans+=1
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()                  #エラトステネスの篩にかけるためソート
Amax = A[-1]
dp = [1]*(Amax+1)         #Aの最大値までのエラトステネスの篩を作る。
ans = 0
for i in range(len(A)-1):
  p = A[i]
  if dp[p] == 1:          #A[i]がA[j]の倍数でないかをエラトステネスの篩でチェック
    for q in range(Amax//p+1):
      dp[p*q] = 0         #A[i]の倍数をすべて0にする
    if A[i] != A[i+1]: 
      ans += 1            #A[i]が重複していなければカウント
if dp[Amax] == 1:         #重複チェック時にレンジオーバーするためAmaxだけ別で判定 
  ans += 1
print(ans)
def main ():
  N = int(input())
  A = list(map(int,input().split()))
  prod = 1 
  
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
    print(-1)
    return
  
  print(prod) 
 
main()

### FIXED CODE ###

def main ():
  N = int(input())
  A = list(map(int,input().split()))
  prod = 1 
  A.sort()
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  
  print(prod) 
 
main()
N = map(int, input().split())
if N%10 == 2 or N%10 == 4 or N%2== 5 or N%10 == 7 or N%10 == 9:
  print("hon")
elif N%10 == 0 or N%10 == 1 or N%10 == 6 or N%10 == 8:
  print("pon")
elif N%10 == 3:
  print("bon")

### FIXED CODE ###

N = int(input())
a = N % 10
if a == 2 or a == 4 or a == 5 or a == 7 or a == 9 :
  print ("hon")
elif a == 0 or a == 1 or a == 6 or a == 8 :
  print ("pon")
else :
  print ("bon")
a,b=map(int,input().split())
lst={0:0,1:300000,2:200000,3:100000}
if a>4:
    x=0
else:
    x=a
if b>4:
    y=0
else:
    y=b
if x==1 and y==1:
    ans=1000000
else :
    ans=lst[x]+lst[y]


print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
lst={0:0,1:300000,2:200000,3:100000}
if a>3:
    x=0
else:
    x=a
if b>3:
    y=0
else:
    y=b
if x==1 and y==1:
    ans=1000000
else :
    ans=lst[x]+lst[y]


print(ans)
n = int(input())
p = []
for i in range(n):
  p[i]= int(input())
p.sort()
print(p[-1]//2 + sum(p[:-2]))

### FIXED CODE ###

n = int(input())
p = [0] * n
for i in range(n):
  p[i]= int(input())
p.sort()
print(p[-1]//2 + sum(p[:-1]))
S, T = input().split()
A, B = map(int, input().split())
U = int(input())

if S == U:
  print (str(A-1)+" "+str(B))
else:
  print (str(A)+" "+str(B-1))

### FIXED CODE ###

S, T = input().split()
A, B = map(int, input().split())
U = input()
 
if S == U:
  print (str(A-1)+" "+str(B))
else:
  print (str(A)+" "+str(B-1))
# using dp with memoization, TLE
from sys import stdin
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)
next_dp = [0] * (W + 1)
for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w >= s[n - 1][0]:
            next_dp[w] = max(next_dp[w], dp[w - s[n - 1][0]] + s[n - 1][1])
    dp = next_dp.copy()
print(dp[W])


### FIXED CODE ###

# using dp with memoization, TLE
from sys import stdin
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

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

for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w == 0:
            dp[n][0] = 0
            continue
        if w < s[n - 1][0]:
            dp[n][w] = dp[n - 1][w]
        else:
            dp[n][w] = max(dp[n - 1][w],
                           dp[n - 1][w - s[n - 1][0]] + s[n - 1][1])

print(dp[N][W])
# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit = 10**6

INF = 10**10

n = int(input())
a = list(int(x) for x in input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    #print(dp)
    #print('now',now)
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        #print('i',i)
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * (n+1)
dfs(0,-1)
for a in ans:
    print(a)

### FIXED CODE ###

# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit(10**7)

INF = 10**18

n = int(input())
a = list(int(x) for x in input().split())
g = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * n
dfs(0, -1)
for a in ans:
    print(a)
#! -*- coding:utf-8 -*-

def search(values,hp,vp,fruit):
	if not (0<=hp<len(values)): return
	if not (0<=vp<len(values[hp])): return
	if fruit!=values[hp][vp]: return
	values[hp][vp]=0
	search(values,hp-1,vp,fruit)
	search(values,hp+1,vp,fruit)
	search(values,hp,vp-1,fruit)
	search(values,hp,vp+1,fruit)

def solve(values):
	count=0
	for i in range(len(values)):
		for j in range(len(values[i])):
			if values[i][j] in ['@','#','*']:
				search(values,i,j,values[i][j])
				count+=1
	return count

def main():
	line,values=input(),list()
	while line!='0 0':
		H,W = list(map(int,line.strip().split(' ')))
		value = list()
		for _ in range(H):
			value.append([x for x in input().strip()])
		values.append(value)
		line = input()
	for value in values:
		print(solve(value))

if __name__=='__main__':
	main()

### FIXED CODE ###

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

import sys
sys.setrecursionlimit(10**6)

def search(field,hp,vp,item):
	if not (0<=hp<len(field)): return
	if not (0<=vp<len(field[hp])): return
	if item!=field[hp][vp]: return
	field[hp][vp]=True
	for dh,dv in [[0,1],[0,-1],[1,0],[-1,0]]:
		search(field,hp+dh,vp+dv,item)
#	search(field,hp-1,vp,item)
#	search(field,hp+1,vp,item)
#	search(field,hp,vp-1,item)
#	search(field,hp,vp+1,item)

def solve(field):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(field)):
		for j in range(len(field[i])):
			if field[i][j] in valid_items:
				search(field,i,j,field[i][j])
				count+=1
	return count

def main():
	line = input().strip()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		field = list()
		for _ in range(H):
			field.append(list(input().strip()))
		print(solve(field))
		line = input().strip()

if __name__=='__main__':
	main()
import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
		if t > M:
			flg2 = 1
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		while (A[t] == k):
			ans = ans*r%1000000007
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
	else:
		print(0)
main()

### FIXED CODE ###

import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
		if t > M:
			flg = 1
			break
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		if flg == 1:
			break
		while (A[t] == k):
			ans = ans*r%1000000007
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
	else:
		print(0)
main()
N=int(input())
if N>81:
    print("No")
else: 
    if N in (1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,28,30,32,35,36,40,42,45,48,49,54,56,63,64,72,81):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

A,B=map(int, input().split())
if A>9 or A<1:
    print("{}".format(-1))
else:
    if B>9 or B<1:
        print("{}".format(-1))
    else:
        print("{}".format(A*B))
N = int(input())
ans = 0
for i in range(1, N+1):
    head, tail = str(i)[0], str(i)[-1]
    if tail == "0":
        continue
    if head == tail:
        ans += 1
    if int(tail + head) <= N:
        ans += 1
    if len(str(N))-2 >= 1 or head == tail:
        num = len(str(N))-2
        if int(tail + "9"*(len(str(N))-2) + head) <= N:
            j = int("9"*(len(str(N))-2))
        else:
            j = int(str(N)[1:-1])
        ans += int(j) + 1
        if num > 1:
            ans += int((num - 1) * "1") * 10
                    
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N+1):
    head, tail = str(i)[0], str(i)[-1]
    if tail == "0":
        continue
    if head == tail:
        ans += 1
    if int(tail + head) <= N:
        ans += 1
    if len(str(N))-2 >= 1 or head == tail:
        num = len(str(N))-2
        if int(tail) <= int(str(N)[0]) and num > 0:
            if int(tail + "9"*(len(str(N))-2) + head) <= N:
                j = int("9"*(len(str(N))-2))
            else:
                if int(tail + str(N)[1:-1] + head) <= N:
                    j = int(str(N)[1:-1])
                else:
                    j = int(str(N)[1:-1]) - 1
            ans += int(j) + 1
        if num > 1:
            ans += int((num - 1) * "1") * 10
    # print(i, ans)
                    
print(ans)
from copy import deepcopy

nk = input().split()
n = int(nk[0])
k = int(nk[1])
ajs = input().split()
ajs = np.array([int(aj) for aj in ajs])

ak_current = ajs[:k].cumprod()[-1]

for i in range(k, n):
  ak_tmp = deepcopy(ak_current)
  ak_tmp = ak_tmp * ajs[i] / ajs[i-k]
  
  if ak_tmp > ak_current:
    print('Yes')
  else:
    print('No')
    
  ak_current = ak_tmp

### FIXED CODE ###

from copy import deepcopy
import numpy as np


nk = input().split()
n = int(nk[0])
k = int(nk[1])
ajs = input().split()
ajs = np.log([int(aj) for aj in ajs])
ajs = ajs / ajs.max()

ak_current = ajs[:k].cumsum()[-1]

for i in range(k, n):
  ak_tmp = deepcopy(ak_current)

  ak_tmp =  ak_tmp - (ajs[i-k]) + (ajs[i])
  
  if ak_tmp > ak_current:
    print('Yes')
  else:
    print('No')
    
  ak_current = ak_tmp
import sys
input=sys.stdin.readline
h,w,d=map(int,input().split())
nums=[[0 for s in range(w)] for i in range(h)]
gya=[[0,0] for i in range(h*w)]
for i in range(h):
    nums[i]=list(map(int,input().split()))
    for j in range(w):
        gya[nums[i][j]-1]=[i,j]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    m=(r-l)//d
    ans=0
    for j in range(1,m+1):
        ans+=abs(gya[l+j*d-1][0]-gya[l+d*(j-1)-1][0])+abs(gya[l+j*d-1][1]-gya[l+d*(j-1)-1][1])
    print(ans)


### FIXED CODE ###

print(int(input())//3)
H, N = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())
INF = 10**10


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

for b in range(1, INF):
    for i in range(1, N+1):
        if b - B[i-1] > 0:
            dp[i][b] = max(dp[i][b - B[i-1]] + A[i-1], dp[i - 1][b])
        else:
            dp[i][b] = max(dp[i-1], A[i-1])
    if dp[-1][b] >= H
        print(b)
        break

### FIXED CODE ###

H, N = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())

dp = [[10**10] * (H + 1) for _ in range(N+1)]

for i in range(1, N+1):
    for h in range(1, H+1):
        if h - A[i-1] <= 0:
            dp[i][h] = min(dp[i-1][h], B[i-1])
        else:
            dp[i][h] = min(dp[i-1][h], dp[i][h-A[i-1]] + B[i-1])

print(dp[-1][-1])