Harryxun/stf_run huggingface dataset:
import numpy as np

N = int(input())

a_b_c_list = []

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

dp = [[0 for i in range(3)] for j in range(100)]

for i in range(N):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            if dp[i+1][k] < dp[i][j] + a_b_c_list[i][k]:
                dp[i+1][k] = dp[i][j] + a_b_c_list[i][k]

print(max(dp[N]))

### FIXED CODE ###

N = int(input())

a_b_c_list = []

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

dp = [[0 for i in range(3)] for j in range(100010)]

for i in range(N):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            if dp[i+1][k] < dp[i][j] + a_b_c_list[i][k]:
                dp[i+1][k] = dp[i][j] + a_b_c_list[i][k]

print(max(dp[N]))
def main():
    n = int(iuput())
    for x in range(1, n + 1):
        s = int(input())
        a = [] #answer
        for _ in range(10):
            s = "{0:08d}".format(s ** 2)
            s = list(s)
            hoge = ""
            for y in range(2, 6):
                hoge += s[y]
            s = int(hoge)
            a.append(s)
        else:
            print("Case", x,end = "")
            print(":")
            for y in a:
                print(y)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    d = int(input())
    a = []
    for _ in range(d):
        a.append(int(input()))

    for x in range(len(a)):
        print("Case ",end = "")
        print(x+1, end = "")
        print(":")
        for _ in range(10):
            a[x] = str("{0:08d}".format(a[x] ** 2))
            hoge = ""
            for y in range(2, 6):
                hoge += a[x][y]
            hoge = int(hoge)
            a[x] = hoge
            print(a[x])


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

min_val = 10000

for i in range(len(H)):
    tmp = T - H[i] * 0.006
    sub = abs(tmp - A)
    if min_val > sub:
        ans = i
        min_val = sub2


print(ans+1)


### FIXED CODE ###

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

min_val = 10000

for i in range(len(H)):
    tmp = T - H[i] * 0.006
    sub = abs(tmp - A)
    if min_val > sub:
        ans = i
        min_val = sub


print(ans+1)
import fractions
n = int(input())
A = list(map(int, input().split())))
work = A[0]
for i in range(1, N):
    work = fractions.gcd(work, A[i])
print(work)

### FIXED CODE ###

import fractions
n = int(input())
A = list(map(int, input().split()))
work = A[0]
for i in range(1, n):
    work = fractions.gcd(work, A[i])
print(work)
N = int(input())
*A, = map(int, input().split())
mod = 10**9 + 7

col = [0, 0, 0]
ans = 1
for a in A:
    ans = ans * col.count(a) % mod
    col[col.index(a)] += 1

print(ans)


### FIXED CODE ###

N = int(input())
*A, = map(int, input().split())
mod = 10**9 + 7

col = [0, 0, 0]
ans = 1
for a in A:
    if a not in col:
        print(0)
        break
    ans = ans * col.count(a) % mod
    col[col.index(a)] += 1
else:
    print(ans)
a,b,c = map(int,input().split())
bis = 1
money = 0
d = [0]*a
if b >= c:
        bis = bis*a + 1
        print(bis)
else:
        for i in range(a):
                if money == 0 :
                        if bis < b:
                                bis += 1
                                d[i] = bis
                        else:
                                money += 1
                                bis -= b
                                d[i] = bis
                else:
                        bis += c
                        money -= 1
                        d[i] = bis
        if d[-1] > d[-2] :
                print(d[-1])
        else:
                print(d[-2]+1)

### FIXED CODE ###

a,b,c = map(int,input().split())
kaisuu = int((a-(b-1))/2)
amari = (a-(b-1))%2
if b >= (c-2):
        print(a+1)
else:
        if amari == 1:
                print(kaisuu*(c-b)+1+b)
        else:
                print(kaisuu*(c-b)+b)
import sys

def main(lines):
    n, m, s = map(int,lines[0].split())
    adj = [[] for _ in range(n)]
    for i in range(m):
        a,b,d = map(int,lines[i+1].split())
        adj[a].append((b,d))
    from heapq import heappush, heappop
    inf = 10**9
    node = []
    dist = [inf]*n
    done = [False]*n
    dist[s] = 0
    heappush(node,(0,s))
    while node:
        cost, v = heappop(node)
        if not done[v]:
            for e in adj[v]:
                if dist[e[0]] > dist[v]+e[1]:
                    dist[e[0]] = dist[v] + e[1]
                    heappush(node, (dist[e[0]],e[0]))
        done[v] = True
    for el in dist:
        if el == inf:
            print('INF') 
        else:
            print(el)       


if __name__ == '__main__':
    lines = []
    for l in sys.stdin:
        lines.append(l.rstrip('\r\n'))
    main(lines)


### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()
import math

n, m = map(int, input().split())

diff = abs(n - m)

if diff > 1:
    print(0)
elif diff == 1:
    print(math.factorial(a) * math.factorial(b) % (10 ** 9 + 7))
else:
    print(math.factorial(a) * math.factorial(b) * 2 % (10 ** 9 + 7))


### FIXED CODE ###

import math

n, m = map(int, input().split())

if abs(n - m) > 1:
    print(0)
    exit()

a = max(n, m)
b = min(n, m)


if a - b == 1:
    print(math.factorial(a) * math.factorial(b) % (10 ** 9 + 7))
else:
    print(math.factorial(a) * math.factorial(b) * 2 % (10 ** 9 + 7))
N = int(input())
LR = [list(map(int,input().split())) for _ in range(N)]

ML = max(LR)[0]
mR = min(LR,key=lambda x:x[1])[1]

if ML > mR:
    LR.sort(key=lambda x:[x[1],x[0]])
    L = [LR[i][0] for i in range(N)]
    for i in range(N):
        r = LR[i][1]
        if ML <= r:
            break

    L_ = [0]*N
    for j in range(N):
        L_[j] = max(L[j],L_[j-1])

    ans = LR[i][1]-ML+1
    for j in range(max(i,1),N):
        ans = max(ans,LR[j][1]-ML+1+max(mR-L_[j-1]+1,0))

else:
    l,r = min(LR,key=lambda x:x[1])
    LR.sort()
    R = [LR[i][1] for i in range(N)]
    for i in range(N):
        if LR[i][0] > l:
            break

    R_ = [0]*N
    R_[-1] = R[-1]
    for j in range(N-2,i-1,-1):
        R_[j] = min(R[j],R_[j+1])

    ans = mR-LR[i-1][0]+1
    for j in range(i-1,N-2):
        ans = max(ans,mR-L[j]+1+R_[j+1]-ML+1)

print(ans)

### FIXED CODE ###

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

LR.sort(key=lambda x:[-x[0],x[1]])
ML = LR[0][0]
MR = LR[0][1]
LR.sort(key=lambda x:[x[1],-x[0]])
mR = LR[0][1]
mL = LR[0][0]

ans = max(mR-ML+1,0)
for i in range(N):
    if LR[i] not in [[ML,MR],[mL,mR]]:
        ans = max(ans,max(mR-ML+1,0)+max(LR[i][1]-LR[i][0]+1,0))

LR.sort(key=lambda x:[x[1],x[0]])

L_ = [0]*N
for i in range(N):
    L_[i] = max(LR[i][0],L_[i-1])

for i in range(1,N):
    ans = max(ans,max(LR[i][1]-ML+1,0)+max(mR-L_[i-1]+1,0))

print(ans)
from collections import Counter

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

dct = dict(Counter(a))
for v, num in dct.items():
  print(f"{v} x {num})
  



### FIXED CODE ###

N = int(input())
s = [input() for i in range(N)]
for v in ['AC', 'WA', 'TLE', 'RE']:
    print('{} x {}'.format(v, s.count(v)))
A, B = list(map(int,input()))
def button(A, B):
  if A > B:
    result = A
    return([A - 1, B, result])
  elif A = B:
    result = A
    return([A - 1, B, result])
  else:
    result = B
    return([A, B - 1, result])

A, B, result_1 = button(A, B)
A, B, result_2 = button(A, B)

print(result_1 + result_2)

### FIXED CODE ###

A, B = list(map(int,input().split()))
def button(A, B):
  if A > B:
    result = A
    return([A - 1, B, result])
  elif A == B:
    result = A
    return([A - 1, B, result])
  else:
    result = B
    return([A, B - 1, result])
 
A, B, result_1 = button(A, B)
A, B, result_2 = button(A, B)
 
print(result_1 + result_2)
n,k = map(int,input().split())

arra = list(input())
arr = arra[:]
count = []
count0 = 0
for i in range(len(arr)-1):
    if arr[i]==arr[i+1]:
        count0+=1
count.append(count0)

        
for _ in range(k):
    whl = [i for i, x in enumerate(arr) if x == 'L']
    whr = [i for i, x in enumerate(arr) if x == 'R']
    suma=[]
    for i in range(1,len(whl)-1):
        suma.append(whl[i+1]-whl[i-1])
    
    sumb=[]
    for i in range(1,len(whr)-1):
        sumb.append(whr[i+1]-whr[i-1])

    
    if len(suma)==0:
        suma = [0]
    if len(sumb)==0:
        sumb = [0]
        
    
    if max(suma) > max(sumb):
        na = suma.index(max(suma))
        
        arr[whl[na]+1:whl[na+2]] = arr[whl[na]+1:whl[na+2]][::-1]
        for i in range(whl[na]+1,whl[na+2]):
            if arr[i] == "L":
                arr[i] = "R"
            else:
                arr[i] = "L"

    
    else:
        nb = sumb.index(max(sumb))
        
        arr[whr[nb]+1:whr[nb+2]-1] = arr[whr[nb]+1:whr[nb+2]-1][::-1]
        for i in range(whr[nb]+1,whr[nb+2]):
            if arr[i] == "L":
                arr[i] = "R"
            else:
                arr[i] = "L"

    count0 = 0
    for i in range(len(arr)-1):
        if arr[i]==arr[i+1]:
            count0+=1
    count.append(count0)

print(max(count))

### FIXED CODE ###

n,k=map(int,input().split())
arr = input()

ans = 0
for i in range(n-1):
    if arr[i] == arr[i+1]:
        ans +=1

ans +=k*2

if ans>n-1:
    ans = n-1

print(ans)
s = input()
q = int(input())

rev = False
head = []
tail = []

for _ in range(q):
    query = input()
    if query == "1":
        rev = not rev
    else:
        _, f, c = query.split()
        if (not rev and f == "1") or (rev and f == "2"):
            head.append(c)
        else:
            tail.append(c)

if not rev:
    print(*head[::-1], s, *tail, sep="")
else:
    print(*tail[::-1], s, *head, sep="")


### FIXED CODE ###

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

rev = False
head = []
tail = []

for i in range(q):
    query = input()
    if query == "1":
        rev = not rev
    else:
        _, f, c = query.split()
        if (not rev and f == "1") or (rev and f == "2"):
            head.append(c)
        else:
            tail.append(c)

if not rev:
    res = head[::-1] + s + tail
else:
    res = tail[::-1] + s[::-1] + head

print(*res, sep="")
n, l = map(int, input().split())
a = sort([input() for i in range(n)])
print(*s, sep="")

### FIXED CODE ###

n, l = map(int, input().split())
s = sorted([input() for i in range(n)])
print(*s, sep="")
N = int(input())
li = list(map(int,input().split()))	
count = 0

while:
	for i in range(N):
		if li[i]%2!=0:
			break
	count += 1
print(count)

### FIXED CODE ###

N = int(input())
li = list(map(int,input().split()))	
count = 0
flag = True

while flag==True:
	for i in range(N):
		if li[i]%2!=0:
			flag=False
		else:
			li[i] = li[i] // 2
	if flag==True:
		count += 1
print(count)
# 最初に入れておくとinputが早くなる
import sys
import math
input = sys.stdin.readline

a, b, c, d = map(int, input().split())
# warikireru = set()
# for i in range(b//c+1):
#    for j in range(b // d+1):
#        k = c ** i * d ** j
#        if(a <= k <= b):
#            warikireru.add(k)
# print(warikireru)
# print(b-a+1-len(warikireru))

k = c * d / math.gcd(c, d)

print(b-a-b//c+a//c-b//d+b//k+a//d-a//k)

### FIXED CODE ###

from fractions import gcd

a,b,c,d=map(int,input().split())
lcm=int(c*d/gcd(c,d))
A=a-1
x1=A-A//c-A//d+A//lcm
x2=b-b//c-b//d+b//lcm
print(x2-x1)
MOD = 1000000007

N = int(input())
S = []
for i in range(2):
    S.append(input())
    

# make XYline
xy = ""
for i in range(len(S[0])):
    if S[0][i] == S[1][i]:
        xy += "X"
    elif S[0][i] == S[0][i+1]:
        xy += "Y"

# proceed
if xy[0] == "X":
    ans = 3
else:
    ans = 6

if len(xy)==1:
    pass
else:
    for i in range(1,len(xy)):
        if xy[i-1] == "X" and xy[i] == "X":
            ans *= 2
        elif xy[i-1] == "X" and xy[i] == "Y":
            ans *= 2
        elif xy[i-1] == "Y" and xy[i] == "X":
            ans *= 1
        elif xy[i-1] == "Y" and xy[i] == "Y":
            ans *= 3

        ans = ans%MOD

    
print(ans)


### FIXED CODE ###

MOD = 1000000007

N = int(input())
S = []
for i in range(2):
    S.append(input())
    

# make XYline
xy = ""
for i in range(len(S[0])):
    if S[0][i] == S[1][i]:
        xy += "X"
    elif i==len(S[0])-1:
        break
    elif S[0][i] == S[0][i+1]:
        xy += "Y"

# proceed
if xy[0] == "X":
    ans = 3
else:
    ans = 6

if len(xy)==1:
    pass
else:
    for i in range(1,len(xy)):
        if xy[i-1] == "X" and xy[i] == "X":
            ans *= 2
        elif xy[i-1] == "X" and xy[i] == "Y":
            ans *= 2
        elif xy[i-1] == "Y" and xy[i] == "X":
            ans *= 1
        elif xy[i-1] == "Y" and xy[i] == "Y":
            ans *= 3

        ans = ans%MOD
print(ans)
n = int(input())
ans = [0]*(n+1) #ans[k]:入力値kでの答え
#初期値３、４、５
ans[3] = 1
ans[4] = 1
ans[5] = 1

for i in range(6,n+1):
  start = 3
  stop = i-3
  s = 1
  for j in range(start,stop+1):
    s = (s+ans[j]) % (10**9+7)
    
  ans[i] = s
  
print(ans[-1])  

### FIXED CODE ###

n = int(input())
s = n // 3

def cmb2(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10**9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


total = 0
for i in range(s):
  y = n - 3*(i+1)
  x = cmb2(y+i,i,p)
  total = (total + x) % (10**9+7)
  
print(total)
pi = 3.14159265358979323846
k = int(input())
print(pi*k**2,pi*k*2)


### FIXED CODE ###

from math import pi
k = float(input())
print(pi*k**2,pi*k*2)
D = input()
dic = {22:'Christmas Eve Eve Eve', 23:'Christmas Eve Eve', 24:'Christmas Eve', 25:'Christmas'}
print(dic[D])

### FIXED CODE ###

D = int(input())
dic = {22:'Christmas Eve Eve Eve', 23:'Christmas Eve Eve', 24:'Christmas Eve', 25:'Christmas'}
print(dic[D])
# coding:utf-8
import readline
import datetime

get_time = int(input())
get_minute = int(input())
sleep_time = int(input())
sleep_minute = int(input())
study = int(input())

a = (sleep_time - get_time) * 60 + sleep_minute - get_minute
print(a - study)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline

h1, m1, h2, m2, k = map(int, readline().split())
print(60 * (h2 - h1) + m2 - m1 - k)
while True:
    (m, f, r) = [int(i) for i in input().split()]
     if m == f == r == -1:
        break
    total = m + f
    if m == -1 or f == -1 or total < 30:
       print('F')
    elif total < 50 and r < 50:
       print('D')
    elif total < 65:
       print('C')
    elif total < 80:
       print('B')
    else:
        print('A')
          

### FIXED CODE ###

while True:
    (m, f, r) = [int(i) for i in input().split()]
    if m == f == r == -1:
        break
 
    s = m + f
 
    if m == -1 or f == -1 or s < 30:
        print('F')
    elif s < 50 and r < 50:
        print('D')
    elif s < 65:
        print('C')
    elif s < 80:
        print('B')
    else:
        print('A')
A, B, C, D = map(int,input().split())

if A <= B:
    train = A
else:
    train = B
if C <= D:
    bus = C
else:
    bus = D
    
answer = train + bus
print(answer)

### FIXED CODE ###

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

if A <= B:
    train = A
else:
    train = B
if C <= D:
    bus = C
else:
    bus = D

answer = (train + bus)
print(answer)
import numpy as np
n=int(input())
s=[chr(i) for i in range(97, 97+26)]
 
aa_cij=np.array([[s.index(i)+1  for i in list(input())] for _ in range(n)],dtype='int8')

ans=0
for i in range(n):
  aa_cij=np.concatenate( [ aa_cij[1:,:], aa_cij[[0],:] ], axis=0)
  if np.allclose(aa_cij 、aa_cij.T):
    ans+=1 
print(ans*n)


### FIXED CODE ###

import numpy as np
n=int(input())
s=[chr(i) for i in range(97, 97+26)]
 
aa_cij=np.array([[s.index(i)+1  for i in list(input())] for _ in range(n)],dtype='int8')
z=np.zeros((n,n),dtype='int8')
ans=0
for i in range(n):
  aa_cij=np.concatenate( [ aa_cij[1:,:], aa_cij[[0],:] ], axis=0)
  if np.allclose(aa_cij - aa_cij.T, z ):
    ans+=1 
print(ans*n)
import sys
input = sys.stdin.readline
N, A, B, C, D = map(int, input().split())
S = list(input())[: -1]
dp = [0] * (N + 1)
dp[B] = 1
for i in range(B, N + 1):
  if dp[i] == 0: continue
  if i + 1 <= N:
    if S[i] == ".":
      dp[i + 1] = 1
  if i + 2 <= N:
    if S[i + 1] == ".":
      dp[i + 2] = 1
if dp[D] == 0:
  print("No")
  exit(0)
S[D] = "#"
dp = [0] * (N + 1)
dp[A] = 1
for i in range(A, N + 1):
  if dp[i] == 0: continue
  if i + 1 <= N:
    if S[i] == ".":
      dp[i + 1] = 1
  if i + 2 <= N:
    if S[i + 1] == ".":
      dp[i + 2] = 1
#print(dp)
if dp[C]:
  print("Yes")
else: print("No")

### FIXED CODE ###

inputa = list(map(int, input().split()))
inputb = list(input())
#double mountain
mountain = 0
for i in range(min(inputa[1], inputa[2]) - 1, max(inputa[3], inputa[4])):
  if inputb[i] == "#":
    if mountain == 1:
      mountain = 2
      break
    mountain = 1
  else:
    mountain = 0

if mountain == 2:
  print("No")
  exit()
    
#need oikoshi
oikoshi = 0
if inputa[3] > inputa[4]:
  oikoshi = 1

#triple step
triplestep = 0
for i in range(inputa[2] - 1, inputa[4]):
  if oikoshi == 0:
    break
  if inputb[i - 1] == ".":
    if inputb[i] == ".":
      if inputb[i + 1] == ".":
        triplestep = 1
        break

if oikoshi == 0:
  print("Yes")
else:
  if triplestep == 1:
    print("Yes")
  else:
    print("No")
S = input()
n = len(S)
a = [0]*n
l = [0]*2019

a[0] = int(S)
l[a[0]%2019] += 1

for i in range(n):
    a[i+1] = a[i] - int(S[i])*pow(10, n-i-1)
    l[a[i+1]%2019] += 1

print(sum(map(lambda x: x*(x-1)//2, l)))


### FIXED CODE ###

import sys

input = sys.stdin.readline

S = input().rstrip()
n = len(S)
l = [0]*2019
d = 10

t = int(S[n-1])
l[t%2019] += 1

l[0] += 1

for i in range(n-2, -1, -1):
    t += int(S[i])*d%2019
    l[t%2019] += 1 
    d *= 10
    d %= 2019

ans = 0

for i in l:
    ans += i*(i-1)//2

print(ans)
n,x=map(int,input().split())
pos=list(map(int,input().split()))
pos2=[abs(p-x) for p in pos]
def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)
 
        return divisor_list

if n==1: ans=pos2[0]
else:
    minpos= min(pos2)
    divs=make_divisor_list(minpos)[::-1]
    if divs[0]==1:ans=1
        else:
            for j in divs:
            if all(x%j==0 for x in pos2):
                ans=j
                break
print(ans)

### FIXED CODE ###

n,x=map(int,input().split())
pos=list(map(int,input().split()))
pos2=[abs(p-x) for p in pos]
def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)
 
        return divisor_list

if n==1: ans=pos2[0]
else:
    minpos= min(pos2)
    divs=make_divisor_list(minpos)[::-1]
    if divs[0]==1:ans=1
    else:
        for j in divs:
            if all(x%j==0 for x in pos2):
                ans=j
                break
print(ans)
h,w=map(int,input().split())
lis=[list(input()) for i in range(h)]

fin=[]
ans=[]

for l in lis:
  if l.count(".") != w:
    fin.append(l)
  else:  
    h=h-1

tr = []
for i in range(w):
    tr_row = []
    for vector in fin:
        tr_row.append(vector[i])
    tr.append(tr_row)
    
for t in tr:
  if t.count(".") != h:
    ans.append(t)
  else:  
    w=w-1
    
for i in range(w):
    tr_row = []
    for vector in ans:
        tr_row.append(vector[i])
    print(*tr_row)


### FIXED CODE ###

h,w=map(int,input().split())
lis=[list(input()) for i in range(h)]

fin=[]
num=[0]*w

for l in lis:
  if l.count(".") != w:
    fin.append(l)
  for i in range(w):
    if l[i]==".":
      num[i]+=1

for f in fin:
  ans=[]
  for i in range(len(num)):
    if num[i]!=h:
      ans.append(f[i])
  print(*ans,sep='')
N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1]

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
point = [list(map(int,input().split())) for i in range(Q)]
ac_list = [0]*(N+1)
 
for i in range(N):
  if S[i:i+2] == 'AC':
    ac_list[i+1] = ac_list[i] + 1
  else:
    ac_list[i+1] = ac_list[i]
 
 
for i in range(Q):
  print(ac_list[point[i][1]-1] - ac_list[point[i][0]-1])
N = int(input())
l = [None]*N
s = []
for i in range(N):
    k = list(map(int,input().split()))
    if k[0]==k[1]:
        s.append(k)
    else:
        l[i] = k

if len(s)>1:
    print("No")
else:
    l = sorted(l, key=lambda x: x[1])
    cnt = 0
    if len(s)==1:
        cnt += s[0][1]

    flag = True
    for j in l:
        if j==None:
            continue
        else:
            cnt += j[0]
        if cnt>j[1]:
            print("No")
            flag = False
            break
    if flag:
        print("Yes")

### FIXED CODE ###

N = int(input())
l = [None]*N
s = []
for i in range(N):
    k = list(map(int,input().split()))
    if k[0]==k[1]:
        s.append(k)
        l[i] = [0,0]
    else:
        l[i] = k

if len(s)>1:
    print("No")
else:
    l = sorted(l, key=lambda x: x[1])
    cnt = 0
    if len(s)==1:
        cnt += s[0][1]

    flag = True
    for j in l:
        if j==[0,0]:
            continue
        else:
            cnt += j[0]
        if cnt>j[1]:
            print("No")
            flag = False
            break
    if flag:
        print("Yes")
import math

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

dp=[[[float('INF'),0] for _ in range(H+1)]for i in range(N+1)]
dp[0]=[[0,0]for _ in range(H+1)]
for i in range(1,N+1):
  a = ab[i-1][0]
  b = ab[i-1][1]
  for j in range(1,H+1):
    limit = math.floor(j/a)+2
    for k in range(limit):
        mana = dp[i-1][j-(a*k)][0]+b*k
        damage = dp[i-1][j-(a*k)][1]+(a*k)
        if damage >= j:
            if dp[i][j][0] > mana:
                dp[i][j]=[mana,damage]

print(dp[N][H])

### FIXED CODE ###

#モンスターの体力は H
#トキはN種類の魔法が使え、
#i番目の魔法を使うと、モンスターの体力を Ai減らすことができますが、
#トキの魔力を Bi消耗します。

#dp[i] = モンスターの体力を i 減らすため消耗する魔力の最小値
#dp[i+1] = min(dp[i-Ai]+Bi,dp[i])
#dp[0]=0

import numpy as np
 
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab = np.array(ab)
 
a = ab[:, 0]
b = ab[:, 1]
 
dp = np.zeros(100001, dtype=np.int)
for i in range(1, h+1):
    dp[i] = (dp[i-a]+b).min()
print(dp[h])