Buggy python submission (verdict: Time Limit Exceeded):
# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        min_bsum = min(min_bsum,bsum[max(0,i-a[atk])]+b[atk])
    bsum.append(min_bsum)
 
#指定のHのコストを表示
print(bsum[h])

Fixed submission:
# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum = np.zeros(h+1)
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        min_bsum = min(min_bsum,bsum[max(0,i-a[atk])]+b[atk])
    bsum[i] = min_bsum

#指定のHのコストを表示
print(int(bsum[h]))


Fixed submission:
# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum = np.zeros(10**4+1)
bsum[0] = 0
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        min_bsum = min(min_bsum,bsum[max(0,i-a[atk])]+b[atk])
    bsum[i] = min_bsum

#指定のHのコストを表示
print(int(bsum[h]))


Fixed submission:
# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])

Buggy python submission (verdict: Time Limit Exceeded):
# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])


Fixed submission:
# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])

Buggy python submission (verdict: Time Limit Exceeded):
# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,10**4+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])


Fixed submission:
# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])

Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter
import sys

# スペース区切りの整数入力
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())

e = []
for i in range(n):
    e.append([i,a[i]/b[i],a[i],b[i]])

e.sort(key=itemgetter(1),reverse=True)
mea = e[0][1]
asum = 0
bsum = 0
min_bsum = 9999999999999999999

path = [0]*(10**4+1)
#path = [0]*(40)

depth = 0
while 1:
    #攻撃番号を得る
    anum = path[depth]

    #有効な攻撃か確認
    if anum > n-1:
        #攻撃ネタ切れなので１つ戻る
        path[depth] = 0
        depth -= 1
        if depth < 0: #深さ０に候補無しなので終了
            break
        anum = path[depth]
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
        continue

    #攻撃実施
    asum = asum + e[anum][2]
    bsum = bsum + e[anum][3]
#    print("途中",h,asum,bsum,min_bsum,path[:depth])

    #攻撃後の状況チェック
    if asum >= h:
        if bsum < min_bsum:
            min_bsum = bsum
            #print("min更新",h,asum,bsum,min_bsum,path[:depth])
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
#    elif bsum >= min_bsum:    #積めないので 次の攻撃に行く
    elif (h-asum)/mea + bsum >= min_bsum:    #最大効率で積んだとしてオーバーなので次の攻撃に行く
        #print("オーバー",h,asum,bsum,min_bsum,path[:depth])
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] = 0
        depth -= 1
        if depth < 0: #深さ０に候補無しなので終了
            break
        anum = path[depth]
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
        '''
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
        continue
        '''
        continue
    else:
        depth += 1

print(min_bsum)

Fixed submission:
# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])

Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter
import sys

# スペース区切りの整数入力
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())

e = []
for i in range(n):
    e.append([i,a[i]/b[i],a[i],b[i]])

e.sort(key=itemgetter(1),reverse=True)
mea = e[0][1]
asum = 0
bsum = 0
min_bsum = 9999999999999999999

path = [0]*(10**4+1)
#path = [0]*(40)

depth = 0
while 1:
    #攻撃番号を得る
    anum = path[depth]

    #有効な攻撃か確認
    if anum > n-1:
        #攻撃ネタ切れなので１つ戻る
        path[depth] = 0
        depth -= 1
        if depth < 0: #深さ０に候補無しなので終了
            break
        anum = path[depth]
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
        continue

    #攻撃実施
    asum = asum + e[anum][2]
    bsum = bsum + e[anum][3]
#    print("途中",h,asum,bsum,min_bsum,path[:depth])

    #攻撃後の状況チェック
    if asum >= h:
        if bsum < min_bsum:
            min_bsum = bsum
#            print("min更新",h,asum,bsum,min_bsum,path[:depth])
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
#    elif bsum >= min_bsum:    #積めないので 次の攻撃に行く
    elif (h-asum)/mea + bsum >= min_bsum:    #最大効率で積んだとしてオーバーなので次の攻撃に行く
#        print("オーバー",h,asum,bsum,min_bsum,path[:depth])
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
        continue
    else:
        depth += 1

print(min_bsum)

Fixed submission:
# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])

Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter
import sys

# スペース区切りの整数入力
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())

e = []
for i in range(n):
    e.append([i,a[i]/b[i],a[i],b[i]])

e.sort(key=itemgetter(1),reverse=True)
mea = e[0][1]
asum = 0
bsum = 0
min_bsum = 9999999999999999999

path = [0]*(10**4+1)
#path = [0]*(40)

depth = 0
while 1:
    #攻撃番号を得る
    anum = path[depth]

    #有効な攻撃か確認
    if anum > n-1:
        #攻撃ネタ切れなので１つ戻る
        path[depth] = 0
        depth -= 1
        if depth < 0: #深さ０に候補無しなので終了
            break
        anum = path[depth]
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
        continue

    #攻撃実施
    asum = asum + e[anum][2]
    bsum = bsum + e[anum][3]
#    print("途中",h,asum,bsum,min_bsum,path[:depth])

    #攻撃後の状況チェック
    if asum >= h:
        if bsum < min_bsum:
            min_bsum = bsum
#            print("min更新",h,asum,bsum,min_bsum,path[:depth])
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
#    elif bsum >= min_bsum:    #積めないので 次の攻撃に行く
    elif (h-asum)/mea + bsum >= min_bsum:    #最大効率で積んだとしてオーバーなので次の攻撃に行く
#        print("オーバー",h,asum,bsum,min_bsum,path[:depth])
        asum = asum - e[anum][2]
        bsum = bsum - e[anum][3]
        path[depth] += 1
        continue
    else:
        depth += 1

print(min_bsum)

Fixed submission:
# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])