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:
import sys
input = sys.stdin.buffer.readline

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

    # max_a = max(np_ab[:, 0])
 
    # dp[i]: モンスターの体力を i 減らすための消耗の最小値
    # 素朴にはh(体力)だけでよさそうだが，オーバーキルの可能性がある
    # →max_a(魔法の強さの最大値)も足しておく
    # dp = [0]*(h+max_a)
    dp = [0]*(h+1)
 
    for i in range(1, h+1):
            dp[i] = min(dp[i-a] + b for a,b in ab)
 
    # 体力を削りきった中で最小の消耗を出力
    # print(min(dp[h:]))
    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
import numpy as np

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

    np_ab = np.array(ab)
    # max_a = max(np_ab[:, 0])
 
    # dp[i]: モンスターの体力を i 減らすための消耗の最小値
    # 素朴にはh(体力)だけでよさそうだが，オーバーキルの可能性がある
    # →max_a(魔法の強さの最大値)も足しておく
    # dp = [0]*(h+max_a)
    dp = [0]*(h+1)
 
    for i in range(1, h+1):
            dp[i] = min(dp[i-a] + b for a,b in np_ab)
 
    # 体力を削りきった中で最小の消耗を出力
    # print(min(dp[h:]))
    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
INF = 10 ** 10


def main():
    H, N = map(int, readline().rstrip().split())
    dp = [INF] * (H + 1)  # HPを減らすのに必要な最小のMP
    dp[0] = 0

    for _ in range(N):
        hp, mp = map(int, readline().rstrip().split())

        for i in range(hp):
            dp[i] = min(dp[i], mp)

        for i in range(hp, H+1):
            dp[i] = min(dp[i-hp] + mp, dp[i])

    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
h,n= map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)] 
m = 10**4
dp = [0]*(h+m+1)
for i in range(m+1,h+m+1):
  dp[i] = min(dp[i-a] + b for a,b in p)
print(dp[h+m+])

Submission status: Runtime Error

Solution code:
h,n= map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)] 
i = 10**4
dp = [0]*(h+i)
for i in range(i,h+i+1):
  dp[i] = min(dp[i-a] + b for a,b in p)
print(dp[h])

Submission status: Runtime Error

Solution code:
import numpy as np


H, N, *AB = map(int, open(0).read().split())
A = np.array(AB[::2])
B = np.array(AB[1::2])
max_A = A.max()

dp = np.zeros(H, dtype=np.int64)
for h in range(H):
    dp[h] = np.min(dp[h - A] + B)

print(dp[-1])

Submission status: Runtime Error

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

dp = [0]*(H+1)
for i in range(1, H+1):
  for j in range(N):
    if j == 0:
      dp[i] = dp[i-ls[j][0]] + ls[j][1]
    else:
      if ls[j][0] <= i:
        dp[i] = min([dp[i], dp[i-ls[j][0]] + ls[j][1]])
      else:
        dp[i] = min([dp[i], ls[j][1]])
        
print(dp[H])

Submission status: Runtime Error

Solution code:
def main():
    h,n = map(int,input().split())
    dp = [0 for i in range(h)]
    mahou = {}
    for i in range(n):
        a,b = map(int,input().split())
        if a not in mahou.keys():
            mahou[a] = b
        else:
            if mahou[a] > b:
                mahou[a] = b
    keys = sorted(mahou.keys())
    for i in range(n):
        if i == 0:
            for j in range(keys[i]):
                dp[j] = mahou[keys[i]]
        else:
            for j in range(keys[i-1],keys[i]):
                d = [mahou[keys[i]]] + [dp[j-keys[k]]+mahou[keys[k]] for k in range(i)]
                d = min(d)
                dp[j] = d

    print(dp[h-1])
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    h,n = map(int,input().split())
    dp = [0 for i in range(h)]
    mahou = {}
    for i in range(n):
        a,b = map(int,input().split())
        if a not in mahou.keys():
            mahou[a] = b
        else:
            if mahou[a] > b:
                mahou[a] = b
    keys = sorted(mahou.keys())
    for i in range(n):
        if i == 0:
            for j in range(keys[i]):
                dp[j] = mahou[keys[i]]
        else:
            for j in range(keys[i-1],keys[i]):
                d = [mahou[keys[i]]] + [dp[j-keys[k]]+mahou[keys[k]] for k in range(i)]
                d = min(d)
                dp[j] = d
    for i in range(keys[n-1],h):
        dp[i] = min([dp[i-keys[j]]+mahou[keys[j]] for j in range(n)])
    print(dp[h-1])
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    h,n = map(int,input().split())
    dp = [0 for i in range(h)]
    mahou = {}
    for i in range(n):
        a,b = map(int,input().split())
        if a not in mahou.keys():
            mahou[a] = b
        else:
            if mahou[a] > b:
                mahou[a] = b
    keys = sorted(mahou.keys())
    for i in range(n):
        if i == 0:
            for j in range(keys[i]):
                dp[j] = mahou[keys[i]]
        else:
            for j in range(keys[i-1],keys[i]):
                d = [mahou[keys[i]]] + [dp[j-keys[k-1]]+mahou[keys[k-1]] for k in range(1,i)]
                d = min(d)
                dp[j] = d
    for i in range(keys[n-1],h):
        dp[i] = min([dp[i-keys[j]]+mahou[keys[j]] for j in range(n)])
    print(dp[h-1])
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
readline= sys.stdin.readline
h,n=map(int,input().split())
li=[]
for i in range(n):
    li.append(list(map(int,readline().split())))
dp=np.zeros((n,h+1),dtype=int)
for i in range(h+1):
    if i%li[0][0]==0:
        dp[0][i]=((i//li[0][0])*li[0][1]
    else:
        dp[0][i]=(i//li[0][0]+1)*li[0][1]
for i in range(1,n):
    for j in range(h+1):
        if j==0:
            dp[i][j]=0
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][max(j-li[i][0],0)]+li[i][1])
print(dp[n-1][h])

Submission status: Runtime Error

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

dp = [0] * (h+1)

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

Submission status: Runtime Error

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

#dp[i][j] := i番目までの物でjの価値を実現するのに必要な最小コスト
dp = [[0] * 1001 for _ in range(n+1)]
for j in range(1, 1001):
    dp[0][j] = float("inf")

for i in range(n):
    for j in range(1001):
        if j < items[i][0]:
            dp[i+1][j] = min(dp[i][j], items[i][1])
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-items[i][0]] + items[i][1])

print(dp[n][h])

Submission status: Runtime Error

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

#dp[i][j] := i番目までの物ででjまでのコストで実現できる最大値
dp = [[0] * 100000001 for _ in range(n+1)]

for i in range(n):
    for j in range(1001):
        if j < items[i][1]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-items[i][1]] + items[i][0])

m = 0
while True:
    if dp[n][m] >= h:
        print(m)
        exit()
    m += 1

Submission status: Runtime Error

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

#dp[i][j] := i番目までの物ででjまでのコストで実現できる最大値
dp = [[0] * 1001 for _ in range(n+1)]

for i in range(n):
    for j in range(1001):
        if j < items[i][1]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-items[i][1]] + items[i][0])

m = 0
while True:
    if dp[n][m] >= h:
        print(m)
        exit()
    m += 1

Submission status: Runtime Error

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

dp = [10**8]*(2*H+1)
dp[0] = 0
for h in range(H+1):
    for ab in abl:
        a,b = ab
        dp[h+a] = min(dp[h+a], dp[h]+b)

print(min( dp[H:] ))

Submission status: Runtime Error

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

dp = [10**8]*(2*H)
dp[0] = 0
for h in range(H+1):
    for ab in abl:
        a,b = ab
        dp[h+a] = min(dp[h+a], dp[h]+b)

print(min( dp[H:] ))

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    H,N = [int(x) for x in input().split()]
    A,B = [],[]
    for _ in range(N):
        a,b = [int(x) for x in input().split()]
        A.append(a)
        B.append(b)

    dp = np.full((N+1,H+1),10 ** 18)
    dp[0][0] = 0
    for i in range(N):
        for j in range(H+1):
            # print(i,j)
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][min(j+A[i],H)] = min(dp[i+1][j]+B[i], dp[i+1][min(j+A[i],H)])
            # print(dp)
    print(int(dp[N][H]))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    H,N = map(int,input().split())
    A,B = [],[]
    for _ in range(N):
        a,b = map(int,input().split())
        A.append(a)
        B.append(b)

    tp = 10**4
    dp = [INF] * tp
    dp[0] = 0
    for h in range(tp):
        minim = INF
        for i in range(N):
            dp_i = h-A[i]
            if dp_i >= 0 and dp[dp_i] != INF:
                minim = min(minim,dp[dp_i]+B[i])
                # print(dp[h-A[i]]+B[i])

        if minim != INF:
            dp[h] = minim
            if h >= H:
                # print(dp[h],h,dp)
                print(dp[h])
                exit()


    assert False


if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。

# = map(int,input().split())

# = list(map(int,input().split()))

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


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

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

dp = [[float("inf") for _ in range(h+1)] for _ in range(n+1)]
#dp[i][j]はi番目のものを選んだ時かつダメージ送料がjだったときの最小MP、


for i in range(1,n+1):
    dp[i][0] = 0
    for j in range(h+1):
        a = ab[i-1][0]
        b = ab[i-1][1]
        elif j+a <= h:
            dp[i][j+a] = min(dp[i][j] + b, dp[i-1][j+a], dp[i][j+a])
        elif j+a > h:
            dp[i][h] = min(dp[i][j] + b, dp[i-1][h], dp[i][h])
            continue

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

Submission status: Runtime Error

Solution code:
#個数が無制限のナップザックの問題(ただし、上限に注意)です(どの魔法を順番に選べば良いなどの制約がないのでナップザックDPを選択しました。)。
#dpの配列にはi番目の要素にモンスターの体力をi減らすために必要な最小の魔力を保存します。
#この配列は個数制限がないことに注意してinfではない要素のみを順に更新していけば良いです。
#また、最終的にモンスターの体力を最小の魔力で0以下にすれば良いので、モンスターの体力をh以上減らせる最小の魔力を求めれば良いです。

h,n=map(int,input().split())
a,b=[],[]
for i in range(n):
    a_sub,b_sub=map(int,input().split())
    a.append(a_sub)
    b.append(b_sub)
inf=10000000000000
ma=max(a)#ダメージの最大値

dp=[inf]*(h+ma)#与えるダメージの最大値を考慮したDP
dp[0]=0#初期値

for i in range(h+1+ma):# 与えるダメージ合計：0ーH+1+maまで
    if dp[i] == inf:#更新してきて、ダメージiになる組み合わせが存在しない場合は飛ばす
        continue
    for j in range(n):    #N個の魔法を試す
        ni = i + a[j] #今の状態から新しく与えた場合のダメージ合計
        if ni<h+ma:#オーバーキルの範囲を超えるなら、無視
            dp[ni] = min(dp[ni], dp[i] + b[j])        #ダメージniを与えるのにより小さい魔力で実現できる場合は更新
print(min(dp[h:]))

Submission status: Runtime Error

Solution code:
#n=int(input())
h,n=map(int,input().split())
#a=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n)]
#l=[list(input().split()) for i in range(n)]


        
ldp=[[0 for j in range(h)]for i in range(n)]
for i in range(n):
    for j in range(h):
        if i==0:
            ldp[i][j]=-(-(j+1)//l[i][0])*l[i][1]
        else:
            if j>=l[i][0]:
                ldp[i][j]=min(ldp[i-1][j],ldp[i][j-l[i][0]]+l[i][1])
            else:
                ldp[i][j]=min(ldp[i-1][j],l[i][1])
print(min(ldp[-1][-1]))

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


sys.setrecursionlimit(10**5)


def main():
    h, n = geta(int)
    a, b = [0] * (n + 1), [0] * (n + 1)
    for i in range(n):
        a[i + 1], b[i + 1] = geta(int)

    INF = 10**9
    dp = [[INF] * (h + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(0, a[i] + 1):
            dp[i][j] = min(b[i], dp[i - 1][j])

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

    print(dp[n][h])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
c = [a[i]/b[i] for i in range(n)]
d = sorted(c, reverse=True)

usedA = 0
usedB = 0
for j in range(n):

    if a[j]/b[j] == d[0]:
        usedA = a[j]
        usedB = b[j]

print(((h-1)//usedA)*usedB +min(b))

Submission status: Runtime Error

Solution code:
c = [a[i]/b[i] for i in range(n)]
d = sorted(c, reverse=True)

usedA = 0
j=0
while j < n:
    if a[j]/b[j] == d[0]:
        usedA = a[j]

print((h-1)//usedA +1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
#from pprint import pprint

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

#dp = [10000] * (H + 1) # あるhpの相手を倒すための最小魔力数を保持する
#dp[0] = 0
#print(A, B)

def constant_factory(value):
    return lambda: value

dp = defaultdict(constant_factory(10000))
dp[0] = 0

def updateDP(hp, hit):
    if hit < dp[hp]:
        dp[hp] = hit
    return dp[hp]

def calcDP(hp):
    if hp < 0:
        return 0
    if dp[hp] == 10000:
        hits = []
        for i in range(N):
            if A[i] > hp:
                hits.append(B[i])
            else:
                updateDP(A[i], B[i])
                hits.append(calcDP(hp-A[i]) + B[i])
        return updateDP(hp, min(hits))
    else:
        return dp[hp]
calcDP(H)
#print(dp)
print(dp[H])

Submission status: Runtime Error

Solution code:
H, N = list(map(int, input().split()))
A, B = [], []
for i in range(N):
    x, y = list(map(int, input().split()))
    A.append(x)
    B.append(y)

dp = [10000] * (H + 1) # あるhpの相手を倒すための最小魔力数を保持する
dp[0] = 0
#print(A, B)

def updateDP(hp, hit):
    if hit < dp[hp]:
        dp[hp] = hit
    return dp[hp]

def calcDP(hp):
    if hp < 0:
        return 0
    if dp[hp] == 10000:
        hits = []
        for i in range(N):
            if A[i] > hp:
                hits.append(B[i])
            else:
                updateDP(A[i], B[i])
                hits.append(calcDP(hp-A[i]) + B[i])
        return updateDP(hp, min(hits))
    else:
        return dp[hp]

calcDP(H)
#print(dp)
print(dp[H])

Submission status: Runtime Error

Solution code:
H, N = list(map(int, input().split()))
A, B = [], []
for i in range(N):
    x, y = list(map(int, input().split()))
    A.append(x)
    B.append(y)

dp = [10000] * (H + 1) # あるhpの相手を倒すための最小魔力数を保持する
dp[0] = 0
#print(A, B)

def updateDP(hp, hit):
    if hit < dp[hp]:
        dp[hp] = hit
    return dp[hp]

def calcDP(hp):
    if hp < 0:
        return 0
    if dp[hp] == 10000:
        hits = []
        for i in range(N):
            if A[i] > hp:
                hits.append(B[i])
            else:
                hits.append(calcDP(hp-A[i]) + B[i])
        return updateDP(hp, min(hits))
    else:
        return dp[hp]

for i in range(N):
    updateDP(A[i], B[i])

calcDP(H)
#print(dp)
print(dp[H])

Submission status: Runtime Error

Solution code:
H, N = list(map(int, input().split()))
A, B = [], []
for i in range(N):
    x, y = list(map(int, input().split()))
    A.append(x)
    B.append(y)

dp = [10000] * (H + 1) # あるhpの相手を倒すための最小魔力数を保持する
dp[0] = 0
#print(A, B)

def updateDP(hp, hit):
    if hit < dp[hp]:
        dp[hp] = hit
        #print("update:", hp, hit)
    return dp[hp]

def calcDP(hp):
    if hp < 0:
        return 0
    if dp[hp] == 10000:
        hits = []
        for i in range(N):
            if A[i] > hp:
                #updateDP(0, B[i])
                hits.append(B[i])
            else:
                #print("*", A[i], B[i])
                updateDP(A[i], B[i])
                #print("$", hp-A[i], calcDP(hp-A[i]))
                hits.append(calcDP(hp-A[i]) + B[i])
        #print(hits)
        #print(dp)
        return updateDP(hp, min(hits))
    else:
        return dp[hp]

calcDP(H)
#print(dp)
print(dp[H])

Submission status: Runtime Error

Solution code:
H, N = list(map(int, input().split()))
A, B = [], []
for i in range(N):
    x, y = list(map(int, input().split()))
    A.append(x)
    B.append(y)

dp = [10000] * (H + 1) # あるhpの相手を倒すための最小魔力数を保持する
dp[0] = 0
#print(A, B)

def updateDP(hp, hit):
    if hit < dp[hp]:
        dp[hp] = hit
        #print("update:", hp, hit)
    return dp[hp]

def calcDP(hp):
    if hp < 0:
        return 0
    if dp[hp] == 10000:
        hits = []
        for i in range(N):
            if A[i] > hp:
                #updateDP(0, B[i])
                hits.append(B[i])
            else:
                #print("*", A[i], B[i])
                updateDP(A[i], B[i])
                #print("$", hp-A[i], calcDP(hp-A[i]))
                hits.append(calcDP(hp-A[i]) + B[i])
        #print(hits)
        #print(dp)
        return updateDP(hp, min(hits))
    else:
        return dp[hp]

calcDP(H)
print(dp)
print(dp[H])

Submission status: Runtime Error

Solution code:
Magic = [list(map(int, input().split())) for i in range(N)]
MAX_COST = max(Magic)[1]


dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)
 
print(dp[-1])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
dmg = []
cost = []

for i in range(m):
    a, b = map(int, input().split())
    dmg.append(a)
    cost.append(b)

inf = 10**9
dp = [inf] * 10001
dp[0] = 0

for i in range(m):
    for j in range(n):
        if dp[j] != inf:
            dp[j + dmg[i]] = min(dp[j + dmg[i]], dp[j] + cost[i])
print(min(dp[n:]))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
dmg = []
cost = []

for i in range(m):
    a, b = map(int, input().split())
    dmg.append(a)
    cost.append(b)

inf = 10**9
dp = [inf] * 2 * n
dp[0] = 0

for i in range(m):
    for j in range(n):
        if dp[j] != inf:
            dp[j + dmg[i]] = min(dp[j + dmg[i]], dp[j] + cost[i])
print(min(dp[n:]))

Submission status: Runtime Error

Solution code:
import pandas as pd

H, N = map(int, input().split())
A_list = []
B_list = []

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

df = pd.DataFrame({'A':A_list, 'B':B_list})
# df['C'] = df['A'] - df['B']
df['C'] = df['A'] / df['B']
df = df.sort_values(['C', 'B'], ascending=[False, True])
df = df.reset_index()

hp = H
bp = 0
for i in range(N):
    if hp // df['A'][i] == 0:
        continue
    bp += (hp // df['A'][i]) * df['B'][i]
    hp -= (hp // df['A'][i]) * df['A'][i]

answer = 0
if hp <= 0:
    answer = bp
else:
    answer = bp + df['B'].min()
    
print(answer)

Submission status: Runtime Error

Solution code:
#初見じゃ無理だった。DPを使う
#標準入力
import numpy as np
H, N = map(int, input().split())
AB = []
max_A = 0
for i in range(N):
    ab = list(map(int, input().split()))
    if max_A < ab[0] :
        max_A = ab[0]
    AB.append(ab)

 #DP
DP = [0] * (H + max_A)
for i in range(1, H + max_A ): #DP[i] の最小値を求めていく
    tmp_mini = 10 ** 8
    for j in range(N):
        if i - AB[j][0] >= 0:
            tmp = DP[i - AB[j][0]] + AB[j][1]
            if tmp_mini > tmp:
                tmp_mini = tmp
    DP[i] = tmp_mini
print(min(DP[H: H + max_A]))

Submission status: Runtime Error

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

ab=[]
dp=[10**9]*(10**4)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    ab.append((a,b))
    dp[a]=b
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)

Submission status: Runtime Error

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

ab=[]
dp=[10**9]*(h*2)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    ab.append((a,b))
    dp[a]=b
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)

Submission status: Runtime Error

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

ab=[]
dp=[0]*(263)

for _ in range(n):
    a,b=map(int,input().split())
    ab.append((a,b))
    dp[b]=a

#dp[b]は、自分がダメージをｂ受けた時の、相手に与えたダメージ
i=1
while 1:

    dp[i]=max(dp[i],dp[i-1])
    for k in range((i-1)//2+2):
        dp[i]=max(dp[i],dp[k]+dp[i-k])
    
    #print(dp)
    if dp[i]>=h:
        print(i)
        exit()
    i+=1

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    a_max=np.max(lis[:,0])
    dp=np.full(h+a_max+1,10**10)
    dp[0]=0
    for l in lis:
        dp[i:i+l[0]+1]=np.minimum(dp[i:i+l[0]+1],dp[i]+l[1])
    print(dp)
    print(dp[h])

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
h,n = map(int,input().split())
ab = []
for i in range(n):
    a,b = map(int,input().split())
    ab.append([a,b])

INF = 10**7
dp = []
for i in range(n+1):
    dp.append([0])
    for _ in range(h):
        dp[i].append(INF)

for j in range(1,h+1):
    for i in range(1,n+1):
        atk = ab[i-1][0]
        mag = ab[i-1][1]
        print
        if j - atk >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i][j-atk]+mag)
        else:
            dp[i][j] = dp[i-1][j]

if dp[n][h] != INF:
    print(dp[n][h])
else:
    for i in range(h,0,-1):
        if dp[n][i] != INF:
            ans = dp[n][i]
            break
    ab.sort(key=lambda x: x[1])
    ans += ab[0][1]
    print(ans)

Submission status: Runtime Error

Solution code:
h,n = map(int,input().split())
ab = []
for i in range(n):
    a,b = map(int,input().split())
    ab.append([a,b])

INF = 10**7
dp = []
for i in range(n+1):
    dp.append([0])
    for _ in range(h):
        dp[i].append(INF)

for j in range(1,h+1):
    for i in range(1,n+1):
        atk = ab[i-1][0]
        mag = ab[i-1][1]
        print
        if j - atk >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i][j-atk]+mag)
        else:
            dp[i][j] = dp[i-1][j]
for i in range(n+1):
    print(dp[i])

if dp[n][h] != INF:
    print(dp[n+1][h+1])
else:
    for i in range(h,0,-1):
        if dp[n][i] != INF:
            ans = dp[n][i]
            break
    ab.sort(key=lambda x: x[1])
    ans += ab[0][1]
    print(ans)

Submission status: Runtime Error

Solution code:
H, N = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N)]
dp = [float('inf')] * 10**4
dp[0] = 0
for a, b in AB:
    for i in range(10**4 - a):
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[H:]))

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    a_max=np.max(lis[:,0])
    dp=np.zeros(h+a_max+1,int)
    for i in range(1,h+1):
        dp[i+lis[:,0]]=np.min(dp[i+lis[:,0]],dp[i]+lis[:,1])
    print(dp[h])

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    dp=np.zeros(h+1,int)
    dp[0]=0
    for l in lis:
        dp[1:l[0]+1]=np.minimum(dp[1:l[0]+1],l[1])
    for i in range(1,h+1):
        dp[i]=np.min(dp[i-lis[:,0]]+lis[:,1])
    print(dp[h])

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    n=int(input())
    A=list(map(int,input().split()))
    X,Y=[0]*n,[0]*n
    for i in range(n):
        X[i]=i+A[i]
        Y[i]=i-A[i]
    set_x=set(X)
    yc=Counter(Y)
    xc=Counter(X)
    ans=0
    for x in set_x:
        ans+=xc[x]*yc[x]
    print(ans)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
H, N = map(int, input().split())

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

for i in range(N):
    a, b = map(int, input().split())
    dp[1:a+1] = np.minimum(dp[1:a+1], b)
    dp[a+1:] = np.minimum(dp[a+1:], dp[:-a+1]+b)
print(int(dp[-1]))

Submission status: Runtime Error

Solution code:
import numpy as np
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
np_ab = np.array(ab)
max_a = max(np_ab[:, 0])
dp = np.full(H+max_a, np.inf)
dp[:max_a] = 0
for i in range(max_a, H+max_a):
    for a, b in ab:
        dp[i] = min(dp[i], dp[i-a] + b)
print(int(dp[-1]))

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    INF = 1 << 30

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

    dp = [INF] * (H * 2 + 1)
    dp[0] = 0

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

dp = [10**7 for i in range(h+100)]
dp[0] = 0
magic = []
for i in range(n):
	a, b = map(int, input().split())
	magic.append([a,b])
	dp[a] = b
#print (dp)


for i in range(h+100):
	for j in range(n):
		if i - magic[j][0] <= 0 or dp[i-magic[j][0]] == 10**7:
			continue
		else:
			dp[i] = min(dp[i],dp[i-magic[j][0]] + magic[j][1])

if dp[h] == 10**7:
	for i in dp[h:]:
		if i != 10**7:
			ans = i
			break
	print (ans)
else:
	print (dp[h])

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split(' '))
magic = [[0 for _ in range(3)] for j in range(N)]
for i in range(N):
  temp_a, temp_b = map(int, input().split())
  magic[i][0] = temp_a
  magic[i][1] = temp_b

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

start = float('inf')
minimum = float('inf')
for i in range(N):
  start = min(start, magic[i][0])
  minimum = min(minimum, magic[i][1])

for i in range(1, start + 1):
  dp[i] = minimum

for i in range(start + 1, H + 1):
  for j in range(N):
    if i >= magic[j][0]:
      dp[i] = min(dp[i - magic[j][0]] + magic[j][1], dp[i])
    else:
      dp[i] = min(magic[j][1], dp[i])

print(dp[H])

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split(' '))
magic = [[0 for _ in range(3)] for j in range(N)]
for i in range(N):
  temp_a, temp_b = map(int, input().split())
  magic[i][0] = temp_a
  magic[i][1] = temp_b
#   magic[i][2] = temp_a / temp_b

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

start = float('inf')
minimum = float('inf')
for i in range(N):
  start = min(start, magic[i][0])
  minimum = min(minimum, magic[i][1])

for i in range(1, start + 1):
  dp[i] = minimum

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

print(dp[H])

Submission status: Runtime Error

Solution code:
from math import ceil

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for i in range(N)] for j in range(H+1)]

for i in range(1, H+1):
    a = AB[-1][0]
    b = AB[-1][1]
    dp[i][N-1] = ceil(i / a)*b

for j in range(0, N-1)[::-1]:
    for i in range(1, H+1):
        a = AB[j][0]
        b = AB[j][1]
        x_list = []
        for k in range(0, int(ceil(i/a))+1):
            new_i = i - a*k
            x = dp[new_i][j+1] + b*k
            x_list.append(x)
        dp[i][j] = min(x_list)

print(dp[H][0])

Submission status: Runtime Error

Solution code:
h, n = map(int, input().split())
l = []
for i in range(n):
    a, b = map(int, input().split())
    l.append([a, b, a/b])

l.sort(key=lambda x: x[2] reverse=True)

ans = 0
while h >= l[0][0]:
    ans += l[0][1]
    h -= m[0][0]

if h != 0:
    dl = []
    for m in l:
        if m[0] <= h:
            tmp = 0
            while h > 0:
                tmp += m[1]
                h -= m[0]
            dl.append(tmp)
    ans += min(dl)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
h,n=map(int,input().split())
ab=np.array([list(map(int,input().split())) for _ in range(n)])
dp=np.zeros(h+1,np.int64) #dp[i]:残り体力がiのとき、倒すまでの最小魔力
dp[0]=0
for a,b in ab:
      dp[1:a+1]=np.minimum(dp[1:a+1],b)
# a:減らせる体力
# b:魔力
for i in range(1,h+1):
  dp[i]=np.min(dp[i-ab[:,0]]+ab[:,1])
print(dp[-1])

Submission status: Runtime Error

Solution code:
import math
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)
dp = [math.inf] * (H+1)

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

print(dp[-1])

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)
dp = [math.inf] * (H+1)

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

print(dp[-1])