CodeEff/ECCO huggingface dataset:
# Original solution
a,b,c=list(map(str,input().split('/')))
d=int(a+b+c)
if d<=20190430:
    print('Heisei')
else:
    print('TBD')

# Optimized solution
a,b,c=list(map(str,input().split('/')))
d=int(a+b+c)
if d>20190430:
    print('TBD')
else:
    print('Heisei')
# Original solution
import datetime
y,m,d=list(map(int,input().split('/')))
print(('Heisei' if datetime.datetime(y, m, d, 0, 0) <= datetime.datetime(2019, 4, 30, 0, 0) else 'TBD'))

# Optimized solution
print(('Heisei' if '20190430' >= ''.join(input().split('/')) else 'TBD'))
# Original solution
y,m,d = input().split('/')
if int(y)<=2019 and (int(m)<=4 and int(d)<=30):
    print("Heisei")
else:
    print("TBD")

# Optimized solution
y,m,d = input().split('/')
if int(y)<=2019 and int(m)<=4 and int(d)<=30: print("Heisei")
else: print("TBD")
# Original solution
#n = int(input())
a,b,c=list(map(int,input().split("/"))) #横並び
#x=[int(input()) for i in range(3)] #縦に並んだのを配列に
#y=list(map(int,input().split())) #横に並んだのを配列に
if b<4 :print("Heisei")
elif b==4 and c<=30 :print("Heisei")
else :print("TBD")
#print('YNEOS'[1::2])


# Optimized solution
a,b,c=list(map(int,input().split("/")))
if b<4 :print("Heisei")
elif b==4 and c<=30 :print("Heisei")
else :print("TBD")
# Original solution
import datetime
if '2019-04-30' >= input().replace('/','-'):
    print('Heisei')
else:
    print('TBD')

# Optimized solution
if '2019-04-30' >= input().replace('/','-'):
    print('Heisei')
else:
    print('TBD')
# Original solution
s=input();print("Heisei") if s[5:7]<="04" else print("TBD")


# Optimized solution
print("Heisei") if input()[5:7]<="04" else print("TBD")
# Original solution
import datetime
y,m,d=list(map(int, input().split("/")))
print(("Heisei" if datetime.date(y, m, d)<=datetime.date(2019, 4, 30) else "TBD"))


# Optimized solution
import datetime
*s, = list(map(int, input().split("/")))

ref = datetime.datetime(2019, 4, 30)

print(("Heisei" if datetime.datetime(s[0], s[1], s[2]) <= ref else "TBD"))
# Original solution
import sys

rr = lambda: sys.stdin.readline().rstrip()

s = rr()
if int(s[5:7]) > 4:
  print('TBD')
else:
  print('Heisei')

# Optimized solution
import sys

rr = lambda: sys.stdin.readline().rstrip()

s = rr()
if s[5:7] > '04':
  print('TBD')
else:
  print('Heisei')
# Original solution
d=int(input().replace("/",""))
print(("Heisei" if 20190430 - d >= 0 else "TBD"))

# Optimized solution
print(("Heisei" if 20190430 - int(input().replace("/","")) >= 0 else "TBD"))
# Original solution
H, N = list(map(int, input().split()))
A = []
for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)

INF = float('INF')
MAX_J = (10 ** 4 + 1) * 2

# DP[i][j]: i番目までの魔法を使って、ダメージの総和をjにする魔力の最小値
DP = [INF] * MAX_J
DP[0] = 0

for i in range(N):
    for j in range(MAX_J):
        nj = min(j+A[i][0], H)
        DP[nj] = min(DP[nj], DP[j] + A[i][1])

print((DP[H]))

# Optimized solution
H, N = list(map(int, input().split()))
A = []
for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)

INF = float('INF')
# MAX_J = (10 ** 4 + 1) * 2
MAX_J = 10 ** 4 + 1

# DP[i][j]: i番目までの魔法を使って、ダメージの総和をjにする魔力の最小値
DP = [INF] * MAX_J
DP[0] = 0

for i in range(N):
    for j in range(MAX_J):
        # nj: 求める添字
        # nj: i番目の魔法を使った後のダメージの総和（Hがmax）
        nj = min(j+A[i][0], H)
        # DP[nj]はすでに入っている値か、i番目の魔法を使った場合か
        DP[nj] = min(DP[nj], DP[j] + A[i][1])
    # print(i, DP)

print((DP[H]))
# Original solution
H, N = list(map(int, input().split()))
A = []
for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)

INF = float('INF')
# MAX_J = (10 ** 4 + 1) * 2
MAX_J = 10 ** 4 + 1

# DP[i][j]: i番目までの魔法を使って、ダメージの総和をjにする魔力の最小値
DP = [INF] * MAX_J
DP[0] = 0

for i in range(N):
    for j in range(MAX_J):
        # nj: 求める添字
        # nj: i番目の魔法を使った後のダメージの総和（Hがmax）
        nj = min(j+A[i][0], H)
        # DP[nj]はすでに入っている値か、i番目の魔法を使った場合か
        DP[nj] = min(DP[nj], DP[j] + A[i][1])
    # print(i, DP)

print((DP[H]))

# Optimized solution
"""
https://atcoder.jp/contests/abc153/tasks/abc153_e

個数制限なしDP
一次元の配列を使うパターン。
"""

H, N = list(map(int, input().split()))
A = []
B = []
for i in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

INF = float('INF')
MAX_J = 10 ** 4 + 1

# DP[j]: ダメージの総和をjにする魔力の最小値
DP = [INF] * MAX_J
DP[0] = 0

# 計算済みのDP[j]にA[i]の魔法を使った場合を計算して、もしそれが最少だったら更新していく

for i in range(N):
    for j in range(MAX_J):
        # nj: 求める添字
        # nj: i番目の魔法を使った後のダメージの総和（Hがmax）
        nj = min(j+A[i], H)
        # DP[nj]はすでに入っている値か、i番目の魔法を使った場合か
        DP[nj] = min(DP[nj], DP[j] + B[i])

print((DP[H]))
# Original solution
h,n=list(map(int,input().split()))
MAX_NUM=9999999999
ab=[]
for _ in range(n):
    ab.append(list(map(int,input().split())))
dp=[MAX_NUM for _ in range(h+1)]
dp[0]=0

for i in range(h):
    if(dp[i]!=MAX_NUM):
        for j in range(n):
            a,b=ab[j]
            ind = i+a if i+a<h else -1
            dp[ind]=min(dp[ind],dp[i]+b)
print((dp[-1]))



# Optimized solution
h,n=list(map(int,input().split()))
ab=[]
for _ in range(n):
    ab.append(list(map(int,input().split())))
max_a=max([a for a,b in ab])
dp=[0 for _ in range(h+max_a)]

for i in range(1,len(dp)):
    dp[i]=min(dp[i-a]+b for a,b in ab)
print((min(dp[h:])))


#
# MAX_NUM=9999999999
# ab=[]
# for _ in range(n):
#     ab.append(list(map(int,input().split())))
# dp=[MAX_NUM for _ in range(h+1)]
# dp[0]=0
#
# for i in range(h):
#     if(dp[i]!=MAX_NUM):
#         for j in range(n):
#             a,b=ab[j]
#             ind = i+a if i+a<h else -1
#             dp[ind]=min(dp[ind],dp[i]+b)
# print(dp[-1])
# Original solution
import math
import copy

def main():
    H,N=list(map(int,input().split()))

    #inf=float('inf')
    dp=[0]+[1e8]*H

    for i in range(N):
        A,B=list(map(int,input().split()))
        if A>=H:
            dp[-1]=min(B,dp[-1])
        else:
            for j in range(A,H+1):
                dp[j]=min(dp[j-A]+B,dp[j])

                if j > H-A:
                    dp[-1]=min(dp[-1],dp[j]+B)


    print((dp[-1]))

main()

# Optimized solution
import math

def main():
    H,N=list(map(int,input().split()))

    inf=float('inf')
    dp=[0]+[inf]*H

    for i in range(N):
        A,B=list(map(int,input().split()))
        if A>=H:
            #dp[-1]=min(B,dp[-1])
            if B < dp[-1]:
                dp[-1]=B
        else:
            for j in range(A,H+1):
                #dp[j]=min(dp[j-A]+B,dp[j])
                if dp[j-A]+B<dp[j]:
                    dp[j]=dp[j-A]+B

                if j > H-A:
                    #dp[-1]=min(dp[-1],dp[j]+B)
                    if dp[j]+B < dp[-1]:
                        dp[-1]=dp[j]+B

    print((dp[-1]))

main()
# Original solution

def main():

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

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

    INF = float("inf")
    dp = [[INF for _ in range(H+1)] for _ in range(N+1)]
    dp[0][0] = 0


    for i in range(1, N+1):
        for h in range(H+1):
            aaa = h-ab[i-1][0] if h-ab[i-1][0] >= 0 else 0
            tmp = dp[i][aaa] if dp[i][aaa] != INF else 0
            dp[i][h] = min(dp[i-1][h], tmp + ab[i-1][1])

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


if __name__ == "__main__":
    main()

# Optimized solution


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

INF = float("inf")
dp = [[INF for _ in range(H+1)] for _ in range(N+1)]
dp[0][0] = 0

# 個数制限なしナップザック
for i in range(N):
    for j in range(H+1):
        if A[i] > j:
            # オーバーキルも可能なので。
            dp[i+1][j] = min(dp[i][j], B[i])
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j - A[i]] + B[i])

print((dp[-1][-1]))
# Original solution
h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(n)]

# 最強の魔法の特定
a_max = max(a for a, b in ab)
# 動的計画法用の配列の定義及び初期化
dp = [0]*(h + a_max)

for i in range(h + a_max):
	if i > 0:
		dp[i] = min(dp[i - a] + b for a, b in ab)

print((min(dp[h:])))

# Optimized solution
h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(n)]

# 最強の魔法の特定
a_max = max(a for a, b in ab)
# 動的計画法用の配列の定義及び初期化
dp = [0]*(h + a_max)

for i in range(1, h + a_max):
	dp[i] = min(dp[i - a] + b for a, b in ab)

print((min(dp[h:])))
# Original solution
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import defaultdict
# import math
# from itertools import product, accumulate, combinations, product
# import bisect# lower_bound etc
#import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba

def run():
    H, N = list(map(int, sysread().split()))
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]

    INF = float('inf')
    dp = [[INF] * (2*H+2) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(2*H+2):
            tmp = j - A[i]
            if tmp >= 0:
                dp[i+1][j] = min([dp[i][j], dp[i+1][tmp] + B[i]])
            elif j == H and tmp < 0:
                dp[i + 1][H] = min(dp[i][H], dp[i + 1][0] + B[i])
            else:
                dp[i+1][j] = dp[i][j]
    ret = min(dp[N][H:])
    print(ret)



if __name__ == "__main__":
    run()

# Optimized solution
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import defaultdict
# import math
# from itertools import product, accumulate, combinations, product
# import bisect# lower_bound etc
#import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba

def run():
    H, N = list(map(int, sysread().split()))
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    Amax = max(A)

    INF = float('inf')
    dp = [[INF] * (H+Amax+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H+Amax+1):
            tmp = j - A[i]
            if tmp >= 0:
                dp[i+1][j] = min([dp[i][j], dp[i+1][tmp] + B[i]])
            elif j == H and tmp < 0:
                dp[i + 1][H] = min(dp[i][H], dp[i + 1][0] + B[i])
            else:
                dp[i+1][j] = dp[i][j]
    ret = min(dp[N][H:])
    print(ret)



if __name__ == "__main__":
    run()
# Original solution
h,n=list(map(int,input().split()))
INF=10**15
a=[]
b=[]
for i in range(n):
    A,B=list(map(int,input().split()))
    a.append(A)
    b.append(B)
dp=[INF]*20010
dp[0]=0
for i in range(20010):
    for j in range(n):
        if i>=a[j]:
            dp[i]=min(dp[i],dp[i-a[j]]+b[j])
ans=min(dp[h:])
print(ans)


# Optimized solution
h,n=list(map(int,input().split()))
INF=10**12
a=[]
b=[]
for i in range(n):
    A,B=list(map(int,input().split()))
    a.append(A)
    b.append(B)
dp=[INF]*20010
dp[0]=0
for i in range(20010):
    for j in range(n):
        if i>=a[j]:
            dp[i]=min(dp[i],dp[i-a[j]]+b[j])
ans=min(dp[h:])
print(ans)
# Original solution
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10
 
h, n = [int(item) for item in input().split()]
MAX_LEN = h + 10**4 + 1
dp = [INF] * MAX_LEN
dp[0] = 0
for i in range(n):
    v, w = list(map(int, input().split()))
    for j in range(h+1):
        if dp[j] != INF and dp[j] + w < dp[j+v]:
            dp[j+v] = dp[j] + w
ans = min(dp[h:])
print(ans)

# Optimized solution
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 + 1
    dp = [0] + [INF] * MAX_LEN
    for _ in range(n):
        v, w = list(map(int, input().split()))
        for j in range(h+1):
            tmp = dp[j] + w
            if dp[j] != INF and tmp < dp[j+v]:
                dp[j+v] = tmp
    ans = min(dp[h:])
    print(ans)

if __name__ == "__main__":
    main()
# Original solution
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 + 1
    dp = [0] + [INF] * MAX_LEN
    for _ in range(n):
        v, w = list(map(int, input().split()))
        for j in range(h+1):
            tmp = dp[j] + w
            if dp[j] != INF and tmp < dp[j+v]:
                dp[j+v] = tmp
    ans = min(dp[h:])
    print(ans)

if __name__ == "__main__":
    main()

# Optimized solution
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 + 1
    dp = [0] + [INF] * MAX_LEN
    for _ in range(n):
        v, w = list(map(int, input().split()))
        for j in range(h+1):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    ans = min(dp[h:])
    print(ans)

if __name__ == "__main__":
    main()
# Original solution
H, N = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(N)]

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

for i in range(N):
    for j in range(H + 1):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][min(j + X[i][0], H)] = min(dp[i + 1][min(j + X[i][0], H)],
                                             dp[i][j] + X[i][1],
                                             dp[i + 1][j] + X[i][1])
        
print((dp[-1][-1]))


# Optimized solution

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

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

for i in range(N):
    for j in range(H + 1):
        dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])

        dp[i + 1][min(j + X[i][0], H)] = min(dp[i + 1][min(j + X[i][0], H)],
                                             dp[i + 1][j] + X[i][1])

print((dp[-1][-1]))
# Original solution
import sys
input = sys.stdin.buffer.readline
from copy import deepcopy
from collections import deque
def main():
    h, n = list(map(int, input().split()))
    a = deque()
    b = deque()
    aa = a.append
    ba = b.append
    for _ in range(n):
        numa, numb = list(map(int, input().split()))
        aa(numa)
        ba(numb)
    dp = [10**9] * (h + 1)
    dp[0] = 0
    while a:
        dp_c = deepcopy(dp)
        at = a.popleft()
        bt = b.popleft()
        for i1 in range(h + 1):
            if i1 <= at:
                dp[i1] = min(bt, dp_c[i1])
            else:
                dp[i1] = min(dp[i1], dp[i1 - at] + bt)
    print((dp[h]))

if __name__ == '__main__':
    main()


# Optimized solution
def main():
    h, n = list(map(int, input().split()))
    ab = [tuple(map(int, input().split())) for _ in range(n)]

    large_num = 10**9
    dp = [large_num] * (h + 10**4 + 1)
    dp[0] = 0
    for abe in ab:
        a = abe[0]
        b = abe[1]
        for i1 in range(h + 1):
            if dp[i1 + a] > dp[i1] + b:
                dp[i1 + a] = dp[i1] + b
    r = min(dp[h:])

    print(r)

if __name__ == '__main__':
    main()
# Original solution
# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = list(map(int, open(0).read().split()))
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if i not in dp:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            if i + a < H:
                dp[i + a] = min(dp[i + a], dp[i] + b)
            else:
                dp[H] = min(dp[H], dp[i] + b)
    print((dp[H]))


if __name__ == "__main__":
    main()


# Optimized solution
# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30
    
    H, N, *AB = list(map(int, open(0).read().split()))
    dp = [INF] * (H + 1)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            if i + a < H:
                dp[i + a] = min(dp[i + a], dp[i] + b)
            else:
                dp[H] = min(dp[H], dp[i] + b)
    print((dp[H]))


if __name__ == "__main__":
    main()
# Original solution
# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30

    H, N, *AB = list(map(int, open(0).read().split()))
    dp = [INF] * (H + 10001)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            dp[i + a] = min(dp[i + a], dp[i] + b)
    print((min(dp[H:])))


if __name__ == "__main__":
    main()


# Optimized solution
# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30

    H, N, *AB = list(map(int, open(0).read().split()))
    dp = [INF] * (H + 10001)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print((min(dp[H:])))


if __name__ == "__main__":
    main()
# Original solution
# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30

    H, N, *AB = list(map(int, open(0).read().split()))
    dp = [INF] * (H + 10001)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        for a, b in zip(*[iter(AB)] * 2):
            dp[i + a] = min(dp[i + a], dp[i] + b)
    print((min(dp[H:])))


if __name__ == "__main__":
    main()


# Optimized solution
# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30

    H, N, *AB = list(map(int, open(0).read().split()))
    dp = [INF] * (H + 10001)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            dp[i + a] = min(dp[i + a], dp[i] + b)
    print((min(dp[H:])))


if __name__ == "__main__":
    main()
# Original solution
# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30

    H, N, *AB = list(map(int, open(0).read().split()))
    dp = [INF] * (H + 10001)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            dp[i + a] = min(dp[i + a], dp[i] + b)
    print((min(dp[H:])))


if __name__ == "__main__":
    main()


# Optimized solution
# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30

    H, N, *AB = list(map(int, open(0).read().split()))
    dp = [INF] * (H + 10001)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print((min(dp[H:])))


if __name__ == "__main__":
    main()
# Original solution
H, N = list(map(int, input().split()))
AB = [[None,None]]
for i in range(N):
  AB.append(list(map(int, input().split())))

dp = [[int(1e8) for i in range(H+1)] for j in range(N+1)] 
for n in range(N+1):
  dp[n][0] = 0

for n in range(1,N+1):
  for h in range(1,H+1):
    ionly_n = int(h/AB[n][0]) + 1
    cand = [dp[n-1][h-i_n*AB[n][0]] + AB[n][1] * i_n for i_n in range(ionly_n)] + [AB[n][1] * ionly_n]
    dp[n][h] = min(cand)
#print(dp)
print((dp[N][H]))

# Optimized solution
H, N = list(map(int, input().split()))
AB = [[None,None]]
for i in range(N):
  AB.append(list(map(int, input().split())))

dp = [int(1e8) for i in range(H+1)]
dp[0] = 0

for h in range(1,H+1):
  cand = []
  for n in range(1,N+1):
    if h - AB[n][0] < 0:
        cand.append(dp[0] + AB[n][1])
    else:
        cand.append(dp[h-AB[n][0]] + AB[n][1])
  dp[h] = min(cand)
print((dp[H]))
# Original solution
H, N = list(map(int, input().split()))
AB = [[None,None]]
for i in range(N):
  AB.append(list(map(int, input().split())))

dp = [int(1e8) for i in range(H+1)]
dp[0] = 0

for h in range(1,H+1):
  cand = [dp[0] + AB[n][1] if h - AB[n][0] < 0 else dp[h-AB[n][0]] + AB[n][1]for n in range(1,N+1) ]
  dp[h] = min(cand)
print((dp[H]))

# Optimized solution
import sys

input = sys.stdin.readline
H, N = list(map(int, input().split()))
magic = [list(map(int, input().split())) for _ in range(N)]

max_damage = max(damage for damage, cost in magic)
dp = [0] * (H + max_damage)

for x in range(1, H + max_damage):
    dp[x] = min(dp[x - damage] + cost for damage, cost in magic)

ans = min(dp[H:])

print(ans)
# Original solution
H,N=list(map(int,input().split()))
A=[]
B=[]
for i in range(N):
   a,b=list(map(int,input().split()))
   A.append(a)
   B.append(b)

DP=[[0]*(H+max(A)) for i in range(N)]
DP.insert(0,[10**8+1]*(H+max(A)))
DP[0][0]=0

for i in range(1,N+1):
   for j in range(1,H+max(A)):
      if j-A[i-1]>0:
         DP[i][j]=min(DP[i-1][j],DP[i][j-A[i-1]]+B[i-1])
      else:
         DP[i][j]=min(DP[i-1][j],B[i-1])

print((DP[N][H]))

# Optimized solution
H,N=list(map(int,input().split()))
A=[]
B=[]
for i in range(N):
   a,b=list(map(int,input().split()))
   A.append(a)
   B.append(b)

DP=[[0]*(H+max(A)) for i in range(N)]
DP.insert(0,[10**8+1]*(H+max(A)))
DP[0][0]=0

for i in range(1,N+1):
   for j in range(1,H+1):
      if j-A[i-1]>0:
         DP[i][j]=min(DP[i-1][j],DP[i][j-A[i-1]]+B[i-1])
      else:
         DP[i][j]=min(DP[i-1][j],B[i-1])

print((DP[N][H]))
# Original solution
from collections import defaultdict
def dp(H, N, a, b):
  d = defaultdict(lambda: INF)
  d[0] = 0
  max_a = max(a)
  for h in range(1, H + max_a):
    d[h] = min([d[h - a[i]] + b[i] for i in range(N)])
  return min([d[H + h] for h in range(max_a)])

INF = 10 ** 10
H, N = list(map(int, input().split()))
a = [0 for _ in range(N)]
b = [0 for _ in range(N)]
for i in range(N):
  ai, bi = list(map(int, input().split()))
  a[i] = ai
  b[i] = bi
print((dp(H, N, a, b)))

# Optimized solution
def dp(H, N, ab):
  max_a = max([ab[i][0] for i in range(N)])
  d = [INF for _ in range(H + max_a)]
  d[0] = 0
  for h in range(1, H + max_a):
    d[h] = min(d[h - a] + b for a, b in ab)
  return min(d[H:])
INF = 10 ** 10
H, N = list(map(int, input().split()))
ab = [tuple(map(int, input().split())) for _ in range(N)]
print((dp(H, N, ab)))
# Original solution
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

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

    INF = 10**12
    dp = [[INF]*(H+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H+1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][min(j+A[i],H)] = min(dp[i+1][min(j+A[i],H)],dp[i+1][j]+B[i])
    print((dp[N][H]))

if __name__ == "__main__":
    main()


# Optimized solution
#!/usr/bin/env python3

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

    #1次元DPに書き換え
    INF = 10**12
    dp = [INF] * (H+1)
    dp[0] = 0
    for i in range(N):
        for j in range(H+1):
            dp[min(j+A[i],H)] = min(dp[min(j+A[i],H)],dp[j]+B[i])
    print((dp[H]))

if __name__ == "__main__":
    main()