Problem:


Score : 500 points

Problem Statement

Ibis is fighting with a monster.

The health of the monster is H.

Ibis can cast N kinds of spells. Casting the i-th spell decreases the monster's health by A_i, at the cost of B_i Magic Points.

The same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.

Ibis wins when the health of the monster becomes 0 or below.

Find the minimum total Magic Points that have to be consumed before winning.

Constraints

1 \leq H \leq 10^4

1 \leq N \leq 10^3

1 \leq A_i \leq 10^4

1 \leq B_i \leq 10^4

All values in input are integers.

Input

Input is given from Standard Input in the following format:

H N
A_1 B_1
:
A_N B_N

Output

Print the minimum total Magic Points that have to be consumed before winning.

Sample Input 1

9 3
8 3
4 2
2 1

Sample Output 1

4

First, let us cast the first spell to decrease the monster's health by 8, at the cost of 3 Magic Points. The monster's health is now 1.

Then, cast the third spell to decrease the monster's health by 2, at the cost of 1 Magic Point. The monster's health is now -1.

In this way, we can win at the total cost of 4 Magic Points.

Sample Input 2

100 6
1 1
2 3
3 9
4 27
5 81
6 243

Sample Output 2

100

It is optimal to cast the first spell 100 times.

Sample Input 3

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461

Sample Output 3

139815



Sample input:
9 3
8 3
4 2
2 1


Sample output:
4

Submission status: Runtime Error

Solution code:
h, n = map(int, input().split())

S = []
for _ in range(n):
    D = list(map(int, input().split()))
    S.append(D)

dic={}

def rec(magic, nokori,sum_mp):

    if str(magic)+"_"+str(nokori) in dic:
        return dic[str(magic)+"_"+str(nokori)]

    if nokori<=0:
        return sum_mp
    if magic >= len(S):
        return 10**9

    dmg = S[magic][0]
    mp  = S[magic][1]

    min_mp = min(
        rec(magic  ,nokori-dmg,sum_mp+mp), # use this magic, and check this magic again
        rec(magic+1,nokori-dmg,sum_mp+mp), # use this magic, and check next magic                    rec(magic+1,nokori,sum_mp       ), # don't use this magic, and check next magic
        )

    dic[str(magic)+"_"+str(nokori)] = min_mp
    return min_mp

print(rec(0,h,0))

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split())
damage = []
mp = []

for i in range(N):
    a, b = map(int, input().split())
    damage.append(a)
    mp.append(b)

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

for j in range(1, H + 1):
    if j % damage[0] == 0:
        x = j // damage[0]
    else:
        x = j // damage[0] + 1 
    dp[1][j] = x * mp[0]

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

Submission status: Runtime Error

Solution code:
h, n = map(int, input().split())

S = []
for _ in range(n):
    D = list(map(int, input().split()))
    S.append(D)

print(S)

dic={}


def rec(magic, nokori,sum_mp):

    if str(magic)+"_"+str(nokori) in dic:
        return dic[str(magic)+"_"+str(nokori)]

    if nokori<=0:
        return sum_mp
    if magic >= len(S):
        return 10**9

    dmg = S[magic][0]
    mp  = S[magic][1]

    min_mp = min(
        rec(magic  ,nokori-dmg,sum_mp+mp), # use this magic, and check this magic again
        rec(magic+1,nokori-dmg,sum_mp+mp), # use this magic, and check next magic                    rec(magic+1,nokori,sum_mp       ), # don't use this magic, and check next magic
        )

    dic[str(magic)+"_"+str(nokori)] = min_mp
    return min_mp

print(rec(0,h,0))

Submission status: Runtime Error

Solution code:
import sys
h, n = map(int,input().split())
AB = [list(map(int, input().split())) for a in range(n)]


ans=sys.maxsize
cnt=0
def fun(H, c,j):
    global ans
    if H <=0:
        if c<ans:
            ans=c

    else:
        for i in range(j,n):
            fun(H-AB[i][0],c+AB[i][1],i)

fun(h,cnt,0)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

def saisho_ko_baisu(A, B):
    # A < B
    if A > B:
        A,B = B,A
    x = A*B
    r = B%A
    while r!=0:
        B = A
        A = r
        r = B%A
    saisho_ko_baisu = x//A
    return saisho_ko_baisu

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

skb = saisho_ko_baisu(As[0], As[1])
for i in range(2,N):
    skb = saisho_ko_baisu(skb, As[i])

most_eff = 100000000
most_eff_id = -1
for i in range(N):
    tmp = (skb // As[i])*Bs[i]
    if most_eff > tmp:
        most_eff = tmp
        most_eff_id = i

cost = (H//skb)*(skb//As[most_eff_id])*Bs[most_eff_id]
H -= (H//skb)*skb

if H == 0:
    print(cost)
    exit()

dp = np.full((N+1, H+1), np.inf)
dp[:, 0] = 0

for r in range(1,N+1):
    for c in range(1,H+1):
        if c >= As[r-1]:
            dp[r, c] = min(dp[r-1, c], dp[r, c-As[r-1]] + Bs[r-1])
        else:
            dp[r, c] = min(dp[r-1, c], Bs[r-1])

# print(dp)
print(cost + int(dp[-1, -1]))

Submission status: Runtime Error

Solution code:
import math
line = input().split(' ')
H = int(line[0])
N = int(line[1])
min_m = 100000
t = 0
As = []
Ms = []
mins = 100000
for i in range(N):
  line = input().split(' ')
  As.append(int(line[0]))
  Ms.append(int(line[1]))
  if min_m > Ms[i]/As[i]:
    min_m = Ms[i]/As[i]
    t = i
for i in range(t,N):
  if min_m == Ms[i]/As[i] and Ms[i] < Ms[t]:
      t = i
ans = math.floor(H/As[t])*Ms[t]
k = H%As[t]
if k == 0:
  print(ans)
else:
  while k > 0:
    p = []
    for i in range(N):
      if Ms[i] >= Ms[t]:
        continue
      elif As[i] < k:
        p.append(k)
        continue
      else:
        t = i
    for i in p:
      if Ms[i]/As[i] < Ms[t]/As[t] and math.ceil(k/As[i])*Ms[i] < math.ceil(k/Ms[t])*Ms[t]:
        t = i
    ans += math.floor(H/As[t])*Ms[t]
    k = H%As[t]
  print(ans)

Submission status: Runtime Error

Solution code:
H,N = map(int,input().split(" "))
lis = []
lis_append = lis.append
dp = [10**8+1 for _ in range(H+1)]
for i in range(N):
    a,b = map(int,input().split(" "))
    dp[a] = b
    lis_append([a,b])


for i in range(H+1):
    for a,b in lis:
        if i + a <= H:
            dp[i+a] = min(dp[i+a],dp[i]+b)
        else:
            dp[-1] = min(dp[-1],dp[i]+b)
print(dp[-1])

Submission status: Runtime Error

Solution code:
H,N=map(int,input().split())
ar=[list(map(int, input().split())) for k in range(N)]
count=0
ans=0
for i in range(N):
    rate=ar[i][1]/ar[i][0]
    ar[i].append(rate)
ar.sort(key=lambda x: x[2])
#print(ar)

while H>0:
    if H>=ar[count][0]:
        H-=ar[count][0]
        ans+=ar[count][1]
    """if len(ar)==1:
        while H>0:
            H-ar[count][0]
            count+=1"""
    elif ar[count][0]>H and H>0:
        while H/ar[count][1]>ar[count+1][2]:
                count+=1

print(ans)

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split())
A = [0] * N # damage
B = [0] * N # MP
# H = 9
# N = 3
# A = [8,4,2]
# B = [3,2,1]

ans = 0

# ------------------------------------------------
ansAmari = float("inf")
def saiki(damage, consumedMP):
    global ansAmari
    if damage >= Hamari:
        ansAmari = min(ansAmari, consumedMP)
        return
        
    for j in range(N):
        saiki(damage+A[j], consumedMP+B[j])
# ------------------------------------------------

cospa = 0
cospaList = []
for x in range(N):
    cospaList.append(A[x]/B[x])
    cospa = max(A[x]/B[x], cospa)
# print(cospa)
# print(cospaList)

cospaBanchi = []
for x in range(N):
    if cospaList[x] == cospa:
        cospaBanchi.append(x)
        
saisyoDamage = 0
saisyoConsumeMP = float("inf")
for y in cospaBanchi:
    saisyoConsumeMP = min(saisyoConsumeMP, B[y])
    if saisyoConsumeMP == B[y]:
        saisyoDamage = A[y]
        
# shou = H // saisyoConsumeMP
# print(shou)
ans += (H // saisyoDamage)*saisyoConsumeMP

Hamari = H % saisyoDamage
# print(amari)
if Hamari == 0:
    print(ans)
else:
    saiki(0,0)
    print(ans+ansAmari)

Submission status: Runtime Error

Solution code:
h,n=map(int,input().split())
a=[0]*n
b=[0]*n
inf=10**10
for i in range(n):
    a[i],b[i]=map(int,input().split())
dp = [[inf for i in range(h+2)] for j in range(n+1)]
for i in range(n):
    cnt=1
    for j in range(h+1):
            if j-a[i]<0:
                dp[i+1][j]=min(dp[i][j],dp[i][j-a[i]]+b[i],b[i]*cnt)
            else:
                dp[i+1][j]=min(dp[i][j],dp[i+1][j-a[i]]+b[i],dp[i][j-a[i]]+b[i],b[i]*cnt)
                cnt+=1
"""
for i in range(1,n+1):
    for j in range(h+1):
        if j+a[i]<=h:
            dp[i+1][j+a[i]]=min(dp[i+1][a[i]],dp[i][j]+b[i])"""
print(dp[n][h])
#print(dp)

Submission status: Runtime Error

Solution code:
H,N=map(int,input().split())

A=[]
B=[]
DP=[10000000000]*(H+1)
DP[0]=0
for i in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
    DP[a]=b



minA=A[A.index(min(A))]
minB=B[B.index(min(B))]

for i in range(1,A.index(min(A))):
    DP[i]=minB

for i in range(A.index(min(A)),H+1):
    temp=[]
    for j in range(i//2+1):
        temp.append(DP[j]+DP[i-j])
    DP[i]=min(temp)

print(DP[H])

Submission status: Runtime Error

Solution code:
h,n=map(int, input().split())
AB=[input().split() for _ in range(n)]
print(AB)

sortedAB = sorted(AB, key=lambda x:x[0])
C = {ab[0] - ab[1]: index for index, ab in enumerate(AB)}

sortedC = sorted(C.items(), key=lambda x:x[0], reverse=True)

count = 0
while True:
  selected = sortedC[0][1]
  if (h <= 0):
    break
  if (h < AB[selected][0]):
    diff = abs(h - AB[selected][0])
    targetList = [ab[1] for index, ab in enumerate(sortedAB) if sortedAB[index][0] >= h or sortedAB[index][0] <= diff]
    count += min(targetList)
    break
  else:
    h = h - AB[selected][0]
    count += AB[selected][1]

print(count)

Submission status: Runtime Error

Solution code:
from functools import lru_cache


@lru_cache(maxsize=1000)
def attack(h, mp):
    """
    毎回Nパターン選択肢がある
    最小値を返す
    """
    min_mp = 999999
    for a, b in sorted_ab_list:
        new_h = h - a
        new_mp = mp + b

        if new_mp >= min_mp:
            # 既に最小値超えてたら中断
            continue

        if new_h > 0:
            min_mp = min(min_mp, attack(new_h, new_mp))
        else:
            min_mp = min(min_mp, new_mp)

    # 最小値をとる
    return min_mp


if __name__ == '__main__':
    H, N = list(map(int, input().split()))
    AB_list = []
    for n in range(N):
        a, b = list(map(int, input().split()))
        AB_list.append([a, b])

    sorted_ab_list = sorted(AB_list, key=lambda x: x[0]/x[1], reverse=True)

    print(attack(H, 0))

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split())
A= [(list(map(int, input().split()))) for _ in range(N)]
total_point = 0
 
while H > 0:
	B= [a[0]/a[1] for a in A]
	index = B.index(max(B))
 
	num = H//A[index][0]
	H = H%A[index][0]
 	used_point = A[index][1]
    damage = A[index][0]
	A = [a for a in A if a[0]<damage and a[1]<used_point]
	if len(A) == 0:
		num += 1
		H = 0
	total_point += num*used_point
print(total_point)

Submission status: Runtime Error

Solution code:
#E再変更
#上から必要なものを順に呼び出していく一度使ったものは再利用
#入力
H,N=map(int,input().split())
M=[list(map(int,input().split())) for i in range(N)]#[攻撃,魔力]
#処理
As=sorted(M,key=lambda x:x[0])
Bs=sorted(M,key=lambda x:x[1])
X=[-1 for i in range(H+1)]#計算していないものについては　-1を代入。
#それ以外にはその点での最小消費を代入
def E(h):#体力hの相手に対して最も最小の魔力消費
    if h<=0:
        return 0
    if X[h]>=0:#計算済み
        return X[h]
    else:#未計算
        
        X[h]=min([E(h-M[i][0]) +M[i][1] for i in range(N)])
        return X[h]
        
print(E(H))

Submission status: Runtime Error

Solution code:
h, n = list(map(int, input().split()))
A = []
B = []
for _ in range(n):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)
d = {}

def toki(h, n):
    if (h, n) in d.keys():
        return d[(h, n)]
    else:
        if h <= 0:
            d[(h, n)] = 0
            return d[(h, n)]
        elif n == 1:
            d[(h, n)] = toki(h - A[0], 1) + B[0]
            return d[(h, n)]
        else:
            d[(h, n)] = min(toki(h, n - 1), toki(h - A[n-1], n) + B[n-1])
            return d[(h, n)]

print(toki(h, n))

Submission status: Runtime Error

Solution code:
h,n=map(int, input().split())
AB = [input().split() for _ in range(n)]
# AB[i][0] = Ai, AB[i][1] = Bi

sortedAB = sorted(AB, key=lambda x:x[0])
C = {ab[0] - ab[1]: index for index, ab in enumerate(AB)}

sortedC = sorted(C.items(), key=lambda x:x[0], reverse=True)

count = 0
while True:
  selected = sortedC[0][1]
  if (h <= 0):
    break
  if (h < AB[selected][0]):
    diff = abs(h - AB[selected][0])
    targetList = [ab[1] for index, ab in enumerate(sortedAB) if sortedAB[index][0] >= h or sortedAB[index][0] <= diff]
    count += min(targetList)
    break
  else:
    h = h - AB[selected][0]
    count += AB[selected][1]

print(count)

Submission status: Runtime Error

Solution code:
h, n = map(int, input().split())

S = []
for _ in range(n):
    D = list(map(int, input().split()))
    S.append(D)

print(S)

dic={}


def rec(magic, nokori,sum_mp):
    if nokori<=0:
        return sum_mp
    if magic >= len(S):
        return 10**9

    dmg = S[magic][0]
    mp  = S[magic][1]

    return min(
        rec(magic  ,nokori-dmg,sum_mp+mp), # use this magic, and check this magic again
        rec(magic+1,nokori-dmg,sum_mp+mp), # use this magic, and check next magic                    rec(magic+1,nokori,sum_mp       ), # don't use this magic, and check next magic
        )

print(rec(0,h,0))

Submission status: Runtime Error

Solution code:
H,N=map(int,input().split())
ar=[list(map(int, input().split())) for k in range(N)]
count=0
ans=0
for i in range(N):
    rate=ar[i][1]/ar[i][0]
    ar[i].append(rate)
ar.sort(key=lambda x: x[2])
#print(ar)

while H>0:
    if H>=ar[count][0]:
        H-=ar[count][0]
        ans+=ar[count][1]
    """if len(ar)==1:
        while H>0:
            H-ar[count][0]
            count+=1"""
    if H/ar[count][1]>ar[count+1][2]:
            count+=1

print(ans)

Submission status: Runtime Error

Solution code:
H,N = map(int,input().split(" "))
lis = []
lis_append = lis.append
dp = [10**10 for _ in range(H+1)]
for i in range(N):
    a,b = map(int,input().split(" "))
    dp[a] = b
    lis_append([a,b])


for i in range(H+1):
    for a,b in lis:
        if i + a <= H:
            dp[i+a] = min(dp[i+a],dp[i]+b)
        else:
            dp[-1] = min(dp[-1],dp[i]+b)
print(dp[-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
import math
import functools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

h, n = na()
a, b = [], []
for _ in range(n):
    ai, bi = na()
    a.append(ai)
    b.append(bi)
inf = 10**9
dp = [[inf]* (10**3+1) for _ in range(n+1)]
for i in range(n):
    for j in range(1, 10**3+1):
        if j < a[i]:
            dp[i+1][j] = min(dp[i][j],((j-1)//a[i]+1)*b[i])
        else:
            dp[i+1][j] = min(dp[i][j],((j-1)//a[i]+1)*b[i], dp[i+1][j - a[i]] + b[i])
print(dp[n][h])

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split())

waza = []
cospa = []

cospa = 0 # コスパのいい技計算用
cost = 0 # コスト
for i in range(N):
    a, b = map(int, input().split())
    waza.append({"A":a, "B":b})
    
    # コスパのいい技判定
    if waza[cospa]["A"]/waza[cospa]["B"] < a/b:
        cospa = i
        #print("コスパ技変更: ", waza[cospa]["A"],waza[cospa]["B"])

# Attack
for i in range(10**5):
    #print("体力:", H)
    
    # コスパ技再計算
    tmp = [n for n in range(N) if waza[n]["A"] < H]
    _cospa = min(tmp) if len(tmp) else 0
    #print("暫定コスパ:", _cospa)
    for _waza in waza:
        if waza[_cospa]["A"]/waza[_cospa]["B"] < _waza["A"]/_waza["B"] and _waza["A"] < H:
            cospa = l
            #print("コスパ技変更: ", waza[cospa]["A"],waza[cospa]["B"])
    
    # コスパの技以上の体力なら、コスパ技を出す
    if H >= waza[cospa]["A"]:
        H -= waza[cospa]["A"]
        cost += waza[cospa]["B"]
    # 体力0なら倒した
    elif H==0:
        break
    else:
        # ちょうどいい技を出す
        #最小コストで1撃
        tmp = [w for w in waza if w["A"] >= H]
        seq = [x['B'] for x in tmp]
        #print("min", min(seq))
        # 倒す
        H = 0
        cost += min(seq)
    

#print("=====")
print(cost)

Submission status: Runtime Error

Solution code:
import sys
import math
import functools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

h, n = na()
a, b = [], []
for _ in range(n):
    ai, bi = na()
    a.append(ai)
    b.append(bi)
inf = 10**9
dp = [[inf]* (10**3+1) for _ in range(n+1)]
for i in range(n):
    for j in range(1, 10**4+1):
        if j < a[i]:
            dp[i+1][j] = min(dp[i][j],((j-1)//a[i]+1)*b[i])
        else:
            dp[i+1][j] = min(dp[i][j],((j-1)//a[i]+1)*b[i], dp[i+1][j - a[i]] + b[i])
print(dp[n][h])

Submission status: Runtime Error

Solution code:
import math
line = input().split(' ')
H = int(line[0])
N = int(line[1])
min_m = 100000
t = 0
As = []
Ms = []
mins = 100000
for i in range(N):
  line = input().split(' ')
  As.append(int(line[0]))
  Ms.append(int(line[1]))
  if min_m > Ms[i]/As[i]:
    min_m = Ms[i]/As[i]
    t = i
for i in range(t,N):
  if min_m == Ms[i]/As[i] and Ms[i] < Ms[t]:
      t = i
ans = math.floor(H/As[t])*Ms[t]
k = H%As[t]
if k == 0:
  print(ans)
else:
  while k > 0:
    p = []
    for i in range(N):
      if Ms[i] >= Ms[t]:
        continue
      elif As[i] < k:
        p.append(k)
        continue
      else:
        t = i
    for i in p:
      if Ms[i]/As[i] < Ms[t]/As[t] and math.ceil(k/As[i])*Ms[i] < math.ceil(k/Ms[t])*Ms[t]:
        t = i
    ans += Ms[t]
    k -= As[i]
  print(ans)

Submission status: Runtime Error

Solution code:
h,n = map(int,input().split())

x = []
y = []

for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)

def knapsack(N,W,weight,value):
  inf=float("inf")
  dp=[[inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=inf

  for i in range(N):
    for w in range(W+1):
        p = value[i]
        q = weight[i]
        while w >= q:
            p += value[i]
            q += weight[i]
        dp[i+1][w]=min(dp[i][w-weight[i]]+value[i], p,dp[i][w])
  return dp[N][W]

k = knapsack(n,h,x,y)
print(k)

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split())
A= [(list(map(int, input().split()))) for _ in range(N)]
total_point = 0
 
while H > 0:
	B= [a[0]/a[1] for a in A]
	index = B.index(max(B))
 
	num = H//A[index][0]
	H = H%A[index][0]
 	used_point = A[index][1]
	A = [a for a in A if a[0]<A[index][0] and a[1]<used_point]
	if len(A) == 0:
		num += 1
		H = 0
	total_point += num*used_point
print(total_point)

Submission status: Runtime Error

Solution code:
H,N = map(int, input().strip().split())
M = [list(map(int, input().strip().split())) for _ in range(N)]

tb = [float('inf')]*(H+1)
tb[0] = 0
for a,b in M:
  for i in range(1,a+1):
    tb[i] = min(tb[i], b)
  for i in range(H+1-a):
    tb[i+a] = min(tb[i+a], tb[i]+b)
  #print(tb)

print(tb[-1])

Submission status: Runtime Error

Solution code:
#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int h, n;
    scanf("%d %d", &h, &n);
    int L[1000][2];
    for (int i=0; i<n; i++) {
        scanf("%d %d", &L[i][0], &L[i][1]);
    }
    vector<int> dp(h+1);

    for (int i=1; i<h+1; i++) {
        int tmp = 1000000;
        for (int j=0; j<n; j++) {
            int x = L[j][0] > i ? L[j][1] : dp[i-L[j][0]] + L[j][1];
            if (x < tmp) {
                tmp = x;
            }
        }
        dp[i] = tmp;
    }
    printf("%i\n", dp[h]);

    return 0;
}

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split())
A, B = [], []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    
A, B = zip(*sorted(zip(A, B)))

dp = [[0] * (H + 1)] * (N + 1)

for dmg in range(1, H + 1):
    dp[1][dmg] = -(-dmg // A[0]) * B[0]

for index in range(1, N + 1):
    a, b = A[index-1], B[index-1]
    for dmg in range(1, H + 1):
        ahead = dp[index-1][dmg] #前回
        only = dp[index][dmg - a] + b #自分だけ
        dp[index][dmg] = min(ahead, only)
print(dp[N][H])

Submission status: Runtime Error

Solution code:
inf = 10**9
H, N = map(int, input().split())
AB = [[0, 0] for i in range(N)]
for i in range(N):
    AB[i][0], AB[i][1] = map(int, input().split())
AB.sort()
T = [[inf for i in range(H+1)] for j in range(N)]
for i in range(N):
    T[i][0] = 0
    if i == 0:
        for j in range(1, H+1):
            if j % AB[i][0] > 0:
                T[i][j] = AB[0][1] * (j // AB[0][0] + 1)
            else:
                T[i][j] = AB[0][1] * (j // AB[0][0])
    else:
        for j in range(1, AB[i][0]):
            T[i][j] = min(T[i-1][j], AB[i][1])
        for j in range(AB[i][0], H+1):
            T[i][j] = min(T[i-1][j], T[i][j - AB[i][0]]+AB[i][1])
print(T[N-1][H])

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split())
A= [(list(map(int, input().split()))) for _ in range(N)]
total_point = 0
 
while H > 0:
	B= [a[0]/a[1] for a in A]
	index = B.index(max(B))
 
	num = H//A[index][0]
	H = H%A[index][0]
 	used_point = A[index][1]
	A = [a for a in A if a[0]<H and a[1]<used_point]
	if len(A) == 0:
		num += 1
		H = 0
	total_point += num*used_point

Submission status: Runtime Error

Solution code:
H,N=map(int,input().split())
L=[]
for i in range(N):
    T=[0,0,0]
    T[1],T[2]=map(int,input().split())
    T[0]=T[2]/T[1]
    L.append(T)
L=sorted(L)
n=1+H//L[0][1]
m=n*L[0][2]

def DP(MAX,minN,minM,i,T,M):
    t=T
    m=M
    if(T>=MAX):
        return M
    if(T<MAX):
        t+=L[i][1]
        m+=L[i][2]
        if(m<minM):        
            tm=DP(MAX,minN,minM,i,t,m)
            if(minM>tm):
                minM=tm
    if(len(L)-1 > i):
        t=T
        m=M
        if(m<minM):
            tm=DP(MAX,minN,minM,i+1,t,m)
            if(minN>tm):
                minM=tm
    return minM

tm=DP(H,10**10,m,0,0,0)

print(tm)

Submission status: Runtime Error

Solution code:
h, n = map(int, input().split())
ab_array = [[int(x) for x in input().split()] for x in range(n)]
min_a = min([x[0] for x in ab_array])

dp = [float("inf") for x in range(h + 1)]
for a, b in ab_array:
    dp[a] = b
for i in range(min_a, h + 2):
    for a, b in ab_array:
        if i + a >= h + 1:
            continue
        dp[i + a] = min(dp[i + a], dp[i] + b)
ans = dp[-1]
if ans == float("inf"):
    for i in reversed(range(h + 1)):
        if dp[i] != float("inf"):
            tmp = dp[i]
            amari = h - i
            break
    for i in range(amari, h):
        if dp[i] != float("inf"):
            tmp2 = dp[i]
            break
    ans = tmp2 + tmp

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
h,n=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(n)]
#i-1番目までの魔法で、j以上のだめを得与えるのに最低限必要な魔力
infi=10**12
dp=[[infi]*(h+1) for i in range(n+1)]
#shoki化
for i in range(n+1):
    dp[i][0]=0
for i in range(n):
    if AB[i][0]+1<h+1:
        for j in range(AB[i][0]+1):
            dp[i+1][j]=min(dp[i][j], AB[i][1])
        for j in range(AB[i][0]+1, h+1):
            dp[i+1][j]=min(dp[i][j], dp[i+1][j-AB[i][0]]+AB[i][1])
    else:
        for j in range(AB[i][0]+1):
            dp[i+1][j]=min(dp[i][j], AB[i][1])
print(dp[n][h])

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split())
G = [0 for i in range(N)]
for i in range(N):
    A, B = map(int, input().split())
    koritu = A / B
    G[i] = (koritu, A, B)
G.sort(reverse = True)
#print(G)
dp = [[0 for i in range(H+1)] for j in range(N)]
for i in range(1, H + 1):
    dp[0][i] = ((i - 1) // a + 1) * b
for j in range(1, N):
    k, a, b = G[j]
    for i in range(1, H+1):
        if i >= a:
            dp[j][i] = min(dp[j-1][i], dp[j][i-a] + b)
        else:
            dp[j][i] = min(dp[j-1][i],b)
print(dp[N-1][H])

Submission status: Runtime Error

Solution code:
H,N = map(int,input().split(" "))
lis = []
lis_append = lis.append
dp = [2**60 for _ in range(H+1)]
for i in range(N):
    a,b = map(int,input().split(" "))
    dp[a] = b
    lis_append([a,b])


for i in range(H+1):
    for a,b in lis:
        if i + a < H:
            dp[i+a] = min(dp[i+a],dp[i]+b)
        else:
            dp[-1] = min(dp[-1],dp[i]+b)
print(dp[-1])

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split())
A= [(list(map(int, input().split()))) for _ in range(N)]
total_point = 0
 
while H > 0:
	B= [a[0]/a[1] for a in A]
	index = B.index(max(B))

	num = H//A[index][0]
	H = H%A[index][0]

	A = [a for a in A if a[0]<H and a[1]<A[index][1]]
	if len(A) == 0:
		num += 1
		H = 0
	total_point += num*A[index][1]
print(total_point)

Submission status: Runtime Error

Solution code:

def main():

    H, N = 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):

            tmp = dp[i][h-ab[i-1][0]] if dp[i][h-ab[i-1][0]] != INF else 0
            #if ab[i-1][0] <= h:
            dp[i][h] = min(dp[i-1][h], tmp + ab[i-1][1])

            #else:
            #    dp[i][h] = dp[i-1][h]

            #if i == 3 and h == 9:
            #    print(dp[i][h-ab[i-1][0]], h, ab[i-1][0], tmp, ab[i-1][1] )

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split())
A= [(list(map(int, input().split()))) for _ in range(N)]
total_point = 0
 
while H > 0:
	B= [a[0]/a[1] for a in A]
	index = B.index(max(B))
 
	num = H//A[index][0]
	H = H%A[index][0]

	A = [a for a in A if a[0]<H and a[1]<A[index][1]]
    if len(A) == 0:
		num += 1
		H = 0
	total_point += num*A[index][1]
print(total_point)

Submission status: Runtime Error

Solution code:
i=list(map(int,input().split()))
h=i[0]
mp=0
mls=[[0,0]]*i[1]
pls=[[0,0]]*i[1]
for k in range(i[1]):
  mls[k]=list(map(int,input().split()))
  pls[k]=[float(mls[0])//mls[1],k]
pls.sort(reverse=True)
fp=mls[pls[0][1]][0]
fm=mls[pls[0][1]][1]
kaz=h//fp
h=h-(fp*(kaz))
mp=fm*kaz
v=0
for v in i[1]:
  sp=mls[v][0]
  sm=mls[v][1]
  if sp>=h and sm<fm:
    fm=sm
mp+=fm
print(mp)

Submission status: Runtime Error

Solution code:
h, n = map(int, input().split())
magic = [
    list(map(int, input().split())) for i in range(n)
]
dp = np.full((n+1, h+1), np.inf, dtype=np.int)
dp[1:, 0] = 0
dp[1][1] = magic[0][0]
for i in range(1, n+1):
    for j in range(1, h + 1):
        if i == 1:
            dp[i][j] = magic[i-1][1] * np.ceil(j/magic[i-1][0])
        elif j >= magic[i-1][0]:
            dp[i][j] = min(
                dp[i-1][j], dp[i][j-magic[i-1][0]] + magic[i-1][1],
            )
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n][h])

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split())
A= [(list(map(int, input().split()))) for _ in range(N)]
total_point = 0

while H > 0:
	B= [a[0]/a[1] for a in A]
	index = B.index(max(B))

	num = H//A[index][0]
	H = H%A[index][0]
	total_point += num*A[index][1]
	A = [a for a in A if a[0]<H]
print(total_point)

Submission status: Runtime Error

Solution code:
from math import ceil, floor

h, n = map(int, input().split())
l = []
for _ in range(n):
  l.append(list(map(int, input().split())))

if n == 1:
  print(ceil(hp/l[0][0]) * l[0][1])
  exit(0)

dp = [
  [ceil(hp/l[0][0]) * l[0][1] for hp in range(h + 1)],
  [None] * (h + 1)
  ]

for i in range(1, n):
  for hp in range(h + 1):
    if hp >= l[i][0]:
      dp[1][hp] = min([dp[0][hp], dp[1][hp - l[i][0]] + l[i][1]])
    else:
      dp[1][hp] = min([dp[0][hp], l[i][1]])

  dp[0] = dp[1]
  dp[1] = [None] * (h + 1)

print(dp[0][-1])

Submission status: Runtime Error

Solution code:
i=list(map(int,input().split()))
h=i[0]
mp=0
mls=[[0,0]]*i[1]
pls=[[0,0]]*i[1]
for k in range(i[1]):
  mls[k]=list(map(int,input().split()))
  pls[k]=[mls[0]/mls[1],k]
pls.sort(reverse=True)
fp=mls[pls[0][1]][0]
fm=mls[pls[0][1]][1]
kaz=h//fp
h=h-(fp*(kaz))
mp=fm*kaz
v=0
for v in i[1]:
  sp=mls[v][0]
  sm=mls[v][1]
  if sp>=h and sm<fm:
    fm=sm
mp+=fm
print(mp)

Submission status: Runtime Error

Solution code:
H,N = list(map(int,input().split()))
INF = 10 ** 12

magics = []
for i in range(N):
    magics.append(list(map(int,input().split())))

#どう考えてもTLEだけどとりあえず
DP = [10**9]*(H+1)
DP[0] = 0
for i in range(N):
    for j in range(magics[i][0]):
        DP[j] = min(DP[j],magics[i][1])
    for j in range(magics[i][0],H+1):
        DP[j] = min(DP[j],DP[j-magics[i][0]]+magics[i][1])

print(DP[H])

Submission status: Runtime Error

Solution code:
inf = 10**9
H, N = map(int, input().split())
AB = [[0, 0] for i in range(N)]
for i in range(N):
    AB[i][0], AB[i][1] = map(int, input().split())
AB.sort()
T = [[inf for i in range(H+1)] for j in range(N)]
for i in range(N):
    T[i][0] = 0
    if i == 0:
        for j in range(1, H+1):
            if j % AB[i][0] > 0:
                T[i][j] = AB[0][1] * (j // AB[0][0] + 1)
            else:
                T[i][j] = AB[0][1] * (j // AB[0][0])
    else:
        for j in range(1, AB[i][0]):
            T[i][j] = T[i-1][j]
        for j in range(AB[i][0], H+1):
            T[i][j] = min(T[i-1][j], T[i][j - AB[i][0]]+AB[i][1])
print(T[-1][-1])

Submission status: Runtime Error

Solution code:
H,N =map(int,input().split()) 
dp = [[0] * (H+1) for i in range(N)]
A,B = map(int,input().split()) 
for j in range(1, H+1):
    dp[0][j] = B * int((j+A-1)/A)

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

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
memo = {}
h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]

def f(n):
    if n <= 0:
        return 0
    elif n in memo:
        return memo[n]
    else:
        tmp = [f(n-a) + b for a, b in ab]
        fn = min(tmp)
        memo[n] = fn
        return fn

print(f(h))

Submission status: Runtime Error

Solution code:
import numpy as np
def main():
    H, N = map(int, input().split())
    l = []
    for _ in range(N):
        a, b = map(int, input().split())
        l.append((a,b))
    dp = np.array([[0] * N for _ in range(H)])
    for w in range(H):
        if (w+1) % l[0][0] == 0:
            dp[w][0] = l[0][1] * ((w+1)//l[0][0])
        else:
            dp[w][0] = l[0][1] * (1 + ((w+1)//l[0][0]))
    for i in range(1, N):
        for w in range(H):
            if w + 1 > l[i][0]:
                m = min(dp.T[i][w-l[i][0]:w])
                dp[w][i] = min(m + l[i][1], dp[w][i-1])
            else:
                dp[w][i] = dp[w][i-1]
    print(min(dp[-1]))
main()