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: Wrong Answer

Solution code:
import bisect

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

ab.sort()

dp = [[float("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])
        if ab[i][0] <= j:
            dp[i+1][j] = min(dp[i][j-ab[i][0]]+ab[i][1], dp[i+1][j])

            t = dp[i+1][j]
            for k in range(j+ab[i][0], h+1, ab[i][0]):
                t += ab[i][1]
                dp[i+1][k] = min(t, dp[i+1][k])

if dp[n][h] != float("inf"):
    print(dp[n][h])
else:
    d = 0
    for i in reversed(range(h)):
        if dp[n][i] != float("inf"):
            d = i
            break

    index = bisect.bisect_left(ab, [h-d, float("inf")])
    ans = dp[n][d] + ab[index][1]
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    AB.sort(reverse=True)
    max_A = max(a for a, _ in AB)
    inf = 10 ** 7
    dp = [inf] * (H + max_A + 1)
    dp[0] = 0
    for a, b in AB:
        for i in range(H):
            if dp[i] == inf:
                continue
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    AB.sort()
    max_A = max(a for a, _ in AB)
    inf = 10 ** 7
    dp = [inf] * (H + max_A + 1)
    dp[0] = 0
    for a, b in AB:
        for i in range(H):
            if dp[i] == inf:
                continue
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    max_A = max(a for a, _ in AB)
    inf = 10 ** 7
    dp = [inf] * (H + max_A + 1)
    dp[0] = 0
    for a, b in AB:
        for i in range(H):
            if dp[i] == inf:
                continue
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    max_A = max(a for a, _ in AB)
    inf = 10 ** 7
    dp = [inf] * (H + max_A + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == inf:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()

Submission status: Wrong Answer

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

m_list = sorted(m_list, key=lambda a: a[2], reverse=True)
e = m_list[0]
h_cp = h
c = 0
while True:
    if h_cp-e[0] <= 0:
        break
    h_cp -= e[0]
    c += e[1]

for a in sorted(m_list, key=lambda a: a[1]):
    if h_cp - a[0] <=0:
        c += a[1]
        break
print(c)

Submission status: Wrong Answer

Solution code:
# 解き直し
H, N = map(int, input().split())
A_to_minB = {}
dp = [float("inf")] * (H + N)
dp[0] = 0
max_A = -1
for i in range(N):
    a, b = map(int, input().split())
    max_A = max(max_A, a)
    if a not in set(A_to_minB.keys()):
        A_to_minB[a] = b
    else:
        A_to_minB[a] = min(A_to_minB[a], b)
for i in range(1, H+N):
    tmp = [dp[i-a]+b for a, b in A_to_minB.items() if a<=i]
    if tmp:
        dp[i] = min(tmp)
print(min(dp[H:H+max_A]))

Submission status: Wrong Answer

Solution code:
# import sys

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

maxsize = 99999999

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

# 各ダメージ段階の最小値を求める
for i in range(H):
    if dp[i] == maxsize:
        continue
    # 各魔法を使って最小値なら更新
    for j in range(N):
        a = min(i + AB[j][0], H)
        b = dp[i] + AB[j][1]
        if dp[a] > b:
            dp[a] = b

print(dp[H])

Submission status: Wrong Answer

Solution code:
import sys

H, N = list(map(int, input().split()))
AB = []
for n in range(N):
    AB.append(list(map(int, input().split())))

dp = [sys.maxsize for i in range(H+1)]
dp[0] = 0

# 各ダメージ段階の最小値を求める
for i in range(H):
    if dp[i] == sys.maxsize:
        continue
    # 各魔法を使って最小値なら更新
    for j in range(N):
        a = min(i + AB[j][0], H)
        b = dp[i] + AB[j][1]
        if dp[a] > b:
            dp[a] = b

min_mp = dp[H]

Submission status: Wrong Answer

Solution code:
import time

def main():
    h, n = map(int, input().split())
    INF = 10 ** 9
    magic = []

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

    t = time.time()

    magic.sort(reverse=True, key=lambda x: x[0])

    dp = [INF] * (h + 10 ** 4)
    dp[0] = 0

    for a, b in magic:
        for i in range(h):
            if dp[i] != INF:
                tmp = dp[i] + b
                if tmp < dp[i + a]:
                    dp[i + a] = tmp

    ans = min(dp[h:])

    print(ans)
    print(time.time() - t)

main()

Submission status: Wrong Answer

Solution code:
import time

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

INF = 10 ** 20

dp = [INF] * (h + 10 ** 4)
dp[0] = 0

magic = []

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


magic.sort(key=lambda x: x[0], reverse=True)

for a, b in magic:
    for i in range(h - a + 2):
        if dp[i] != INF:
            dam = i + a
            if dp[dam] > dp[i] + b:
                dp[dam] = dp[i] + b

ans = min(dp[h:])

print(ans)

Submission status: Wrong Answer

Solution code:
import time

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

INF = 10 ** 20


dp = [INF] * (h + 10 ** 4)
dp[0] = 0

magic = []

for i in range(n):
    magic.append(list(map(int, input().split())))

magic.sort(key=lambda x: x[0], reverse=True)

for a, b in magic:
    for i in range(h - a + 1):
        if dp[i] == INF:
            continue
        dam = i + a
        if dp[dam] > dp[i] + b:
            dp[dam] = dp[i] + b

ans = min(dp[h:])

print(ans)

Submission status: Wrong Answer

Solution code:
import time

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

INF = 10 ** 20


dp = [INF] * (h + 10 ** 4)
dp[0] = 0

magic = []

for i in range(n):
    magic.append(list(map(int, input().split())))

magic.sort(key=lambda x: x[0])

for a, b in magic:
    for i in range(h - a + 1):
        if dp[i] == INF:
            continue
        dam = i + a
        if dp[dam] > dp[i] + b:
            dp[dam] = dp[i] + b

ans = min(dp[h:])

print(ans)

Submission status: Wrong Answer

Solution code:
import time

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

INF = 10 ** 20


dp = [INF] * (h + 10 ** 4)
dp[0] = 0

magic = []

for i in range(n):
    magic.append(list(map(int, input().split())))

magic.sort(key=lambda x: x[1])

for a, b in magic:
    for i in range(h - a + 1):
        if dp[i] == INF:
            continue
        dam = i + a
        if dp[dam] > dp[i] + b:
            dp[dam] = dp[i] + b

ans = min(dp[h:])

print(ans)

Submission status: Wrong Answer

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)
    if a>H:
        DP[H]=b
    else:
        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+1):
        temp.append(DP[j]+DP[i-j])
    DP[i]=min(temp)

print(DP[H])

Submission status: Wrong Answer

Solution code:
# E - Crested Ibis vs Monster
def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = [1 << 30] * (H + 1)  # 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()

Submission status: Wrong Answer

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

#dp[v]:体力をv減らす時の最小魔力
dp=[10**20 for i in range(h+1)]
dp[0]=0

for i in range(h+1):
    for j in range(n):
        if x[j][0]<=i:
            dp[i]=min(dp[i],dp[i-x[j][0]]+x[j][1])
print(dp[-1])

Submission status: Wrong Answer

Solution code:

     

import math



H,N = map(int,input().split())
Damage = []
Cost = []


DP = [0] + [pow(10,9)] * (H+1)



for i in range(N):
    a,b = map(int,input().split())
    Damage.append(a)
    Cost.append(b)
    
#print(DP)


# DP[i] = min magic points to do i damage

for i in range(1,len(DP)):
    for spell in range(N):
        DP[i] = min(DP[i],DP[max(0,i-Damage[spell])]+Cost[spell])

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
atk = []
mp = []
for i in range(n):
  tmp_a, tmp_b = map(int, input().split())
  atk.append(tmp_a)
  mp.append(tmp_b)
  
dp = [0] * (h+1)
max_atk = 0
for i in range(1,h+1):
  min_dp = 9999999999999
  tmp_atk = [0] * n
  for j in range(n):
    if i <= max_atk:
      dp[i] = dp[i-1]
    elif i <= atk[j]:
      dp[i] = mp[j]
      tmp_atk[j] = atk[j]
    else:
      dp[i] = dp[i-1] + mp[j]
      tmp_atk[j] = max_atk + atk[j]
    if dp[i] < min_dp:
      min_dp = dp[i]
      ind = j
  max_atk = tmp_atk[ind]
  dp[i] = min_dp
print(dp[h])

Submission status: Wrong Answer

Solution code:
inf = 10**10
H, N = map(int, input().split())
A = []
B = []
for n in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
dp = [inf] * (H + 10 ** 4)
for n in range(N):
    for h in range(H):
        if dp[h] == inf:
            continue
        dp[h + A[n]] = min(dp[h + A[n]], dp[h] + B[n])
print(min(dp[H:]))

Submission status: Wrong Answer

Solution code:
import numpy as np

h, n = map(int, input().strip().split())
AB = [list(map(int, input().split())) for i in range(n)]

dp=[np.inf]*(h+1)

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10
MAX_LEN = 2*10**4
 
h, n = [int(item) for item in input().split()]
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
dp = [INF] * MAX_LEN
dp[0] = 0
for i in range(1, n+1):
    v, w = ab[i-1]
    for j in range(h+1):
        if dp[j] > dp[j-v] + w:
            dp[j] = dp[j-v] + w
ans = min(dp[h:])
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10
MAX_LEN = 2*10**4

h, n = [int(item) for item in input().split()]
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
dp = [INF] * (MAX_LEN * (n + 1))
dp[0] = 0
ans = INF
for i in range(1, n+1):
    v, w = ab[i-1]
    offset = i * MAX_LEN
    offset_before = offset - MAX_LEN
    for j in range(h+1):
        if j < v:
            dp[offset+j] = dp[offset_before+j]
        elif dp[offset_before+j] > dp[offset+j-v] + w:
            if j >= h and ans > dp[offset+j-v] + w:
                ans = dp[offset+j-v] + w
            else:
                dp[offset+j] = dp[offset+j-v] + w
        else:
            dp[offset+j] = dp[offset_before+j]
print(ans)

Submission status: Wrong Answer

Solution code:
'''input
9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
'''
from sys import stdin
input = stdin.readline
import math
import sys, resource
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x100000)


def mp(first, second):
	return str(first) + ' '  + str(second)


def brute(arr, h, dp):
	if h <= 0:
		return 0
	if h in dp:
		return dp[h]

	first = float('inf')
	for i in range(len(arr)):
		if arr[i][0] > h:
			break
		first = min(first, arr[i][1] + brute(arr, h - arr[i][0], dp))
		
	dp[h] = first
	return first

	
# main starts
h, n = list(map(int, input().split()))
arr = []

for _ in range(n):
	a, b = list(map(int, input().split()))
	arr.append([a, b])
arr.sort(key = lambda x: x[0])

dp = dict()
print(brute(arr, h, dp))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

h, n = [int(item) for item in input().split()]
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
dp = [[INF] * (2 * 10**4) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(0, n):
    v, w = ab[i-1]
    for j in range(h+1):
        if dp[i+1][j] > dp[i][j]:
            dp[i+1][j] = dp[i][j]
        dp[i+1][j+v] = dp[i+1][j] + w
ans = min(dp[n][h:])
print(ans)

Submission status: Wrong Answer

Solution code:
h, n = [int(v) for v in input().split()]

inf = 10 ** 10
magic = []
max_a = 0

for i in range(n):
    ab = [int(v) for v in input().split()]
    max_a = max(ab[0], max_a)
    magic.append(ab)

dp = [inf] * (h + max_a)

min_a = inf
for (a, b) in magic:
    dp[a] = b
    min_a = min(min_a, a)

for i in range(min_a, h):
    v = dp[i]
    if v == inf:
        continue
    for (a, b) in magic:
        dp[i+a] = min(dp[i+a], v+b)

min_dp = None
for i in range(h, h+max_a):
    if min_dp is None:
        min_dp = dp[i]
    else:
        min_dp = min(min_dp, dp[i])

print(min_dp)

Submission status: Wrong Answer

Solution code:
h, n = [int(v) for v in input().split()]

inf = float('inf')
magic = []
max_a = 0

for i in range(n):
    ab = [int(v) for v in input().split()]
    max_a = max(ab[0], max_a)
    magic.append(ab)

dp = [0] * (h + max_a)

min_a = inf
for (a, b) in magic:
    dp[a] = b
    min_a = min(min_a, a)

for i in range(min_a, h):
    v = dp[i]
    if v == 0:
        continue

    for (a, b) in magic:
        if dp[i+a] == 0:
            dp[i+a] = v + b
        else:
            dp[i+a] = min(dp[i+a], v+b)

min_dp = None
for i in range(h, h+max_a):
    if dp[i] == 0:
        continue
    if min_dp is None:
        min_dp = dp[i]
    else:
        min_dp = min(min_dp, dp[i])

print(min_dp)

Submission status: Wrong Answer

Solution code:
H,N=map(int,input().split())
L=[]
m=0
for i in range(N):
    T=[0,0]
    T[0],T[1]=map(int,input().split())
    L.append(T)
    m=max(m,T[0])
L=sorted(L)
L.insert(0,[0,0])
DP=[[10**10 for i in range(H+1+m)] for j in range(N+1)]
DP[0][0]=0


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

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read

H, N, *AB = map(int, read().split())

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

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, H + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
        if i >= H - a:
            r = min(r, dp[i] + b)

print(min(r, dp[-1]))

Submission status: Wrong Answer

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

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

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

dp = [[10**12] * (H+1) for _ in range(N+1)]

# dp[i][0]はコスト0
for i in range(N+1):
    dp[i][0] = 0

# i個の魔法
for i in range(N):
    # hの体力
    for h in range(H+1):
        # 魔法の攻撃力が足らない
        if h < A[i]:
            dp[i+1][h] = dp[i][h]
        # 最後に倒すとき
        elif h == H:
            # 攻撃力がHを超える時
            if A[i] > H:
                dp[i+1][h] = min(dp[i][h], B[i])
            # 超えてない時
            else:
                m = min(dp[i+1][h-A[i]:h])
                dp[i+1][h] = min(dp[i][h], m + B[i])
        # 通常時
        else:
            dp[i+1][h] = min(dp[i][h], dp[i+1][h-A[i]] + B[i])


print(dp[N][H])

Submission status: Wrong Answer

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):
        if j - damage[i] >= 0:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - damage[i]] + mp[i])
        else:
            dp[i + 1][j] = dp[i][j]

for i, row in enumerate(dp):
    if i == 0:
        continue
    buf = float("inf")
    for j in range(H + 1):
        if row[H - j] > buf:
            row[H - j] = buf
        buf = row[H - j]

print(dp[N][H])

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
H,N=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
#AB=sorted(AB,key=lambda x:x[1])

dp=[10**9 for i in range(H+10**4+1)]
dp[0]=0
for a,b in AB:
    for i in range(1,H*2):
        if i>=a:
            dp[i]=min(dp[i-a]+b,dp[i])

print(min(dp[H:]))

Submission status: Wrong Answer

Solution code:

#import numpy as np

H,N=map(int,input().split())
weights=[list(map(int,input().split())) for _ in range(N)]
INF=10010011
#print(weight)
#print(value)

#print(weights)
dp=[INF]*(H+1)
for i in range(H+1):
    if i==0:
        dp[i]=0
    else:
        for j in weights:
            a=j[0]
            b=j[1]
            piv=max(0,i-a)  #use i-a's dp[] value as a pivot (if not exits(i-a<0), return dp[0])
            dp[i]=min(dp[i],dp[piv]+b) #the part which forcely treated as piv=0, returns min([weights]), other is treated as normal dp
    #print(dp)

print(dp[H])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10

h, n = [int(item) for item in input().split()]
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
dp = [[INF] * (2 * 10**4) for _ in range(n + 1)]
dp[0][0] = 0
dp[1][0] = 0
for i in range(n):
    v, w = ab[i]
    for j in range(10**4):
        if dp[i][j] == INF:
            continue
        dp[i][j+v] = dp[i][j] + w
        dp[i+1][j + v] = dp[i][j] + w
        if dp[i+1][j] > dp[i][j]:
            dp[i+1][j] = dp[i][j]
ans = min(dp[n][h:])
print(ans)

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
H,N=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
#AB=sorted(AB,key=lambda x:x[1])

dp=[10**9 for i in range(H*2)]
dp[0]=0
for a,b in AB:
    for i in range(1,H*2):
        if i>=a:
            dp[i]=min(dp[i-a]+b,dp[i])

print(min(dp[H:]))

Submission status: Wrong Answer

Solution code:
# coding:utf-8

H, N = map(int, input().split(' '))
ab_list = []
for _ in range(N):
    a, b = map(int, input().split(' '))
    ab_list.append([a, b])
dp = [0] * (H + 1)

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

print(dp[H])

Submission status: Wrong Answer

Solution code:
# coding:utf-8

H, N = map(int, input().split(' '))
ab_list = []
for _ in range(N):
    a, b = map(int, input().split(' '))
    ab_list.append([a, b])
dp = [0] * (H + 1)

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

print(dp[H])

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
inf =10*10
dp = [inf for _ in range(H+1)]

# min_cost = np.inf
dp[0]=0
for n in range(N):
    a,b =  map(int, input().split())
    for h in range(H):
        nj = min(h+a,H)
        dp[nj] = min([dp[nj],dp[h]+b])
        
print(int(dp[H]))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

MAGIC = []
for _ in range(N):
    a, b = map(int, input().split())
    MAGIC.append((a, b))

dp = [[10**20] * (20000) for _ in range(N+1)]

for i in range(N+1):
    dp[i][0] = 0


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


print(dp[N][H])

Submission status: Wrong Answer

Solution code:
import numpy as np

s = input().split()
H = int(s[0])
N = int(s[1])

m = np.array([list(map(int, input().split())) for i in range(N)])

def func(H, m):
    A = m[:, 0]
    B = m[:, 1]
    i = np.argmax(A / B)
    
    if H < A[i]:
        if len(A) == 1:
            return B[i]
        else:
            temp = func(H, np.delete(m, i, 0))
            return B[i] if B[i] < temp else temp
    else:
        if len(A) == 1:
            return -(-H // A[i]) * B[i]
        else:
            if H % A[i] == 0:   
                return (H // A[i]) * B[i]
            else:
                return (H // A[i]) * B[i] + func(H - (H // A[i]) * B[i], np.delete(m, i, 0))

print(func(H, m))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

MAGIC = []
for _ in range(N):
    a, b = map(int, input().split())
    MAGIC.append((a, b))

dp = [[10**20] * (H+1) for _ in range(N+1)]

for i in range(N+1):
    dp[i][0] = 0


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


print(dp[N][H])

Submission status: Wrong Answer

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

# dp[i][h] := i-1 番目の魔法の中から，減らす体力が h を達成するように選んだ時の魔法の最小値
# DP テーブル
max_h = H + max(A)
dp = [[float("inf")] * (H + 1) for _ in range(N+1)]
dp[0][0] = 0

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

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
l={}
ans=0
for i in range(n):
    a,b=map(int,input().split())
    if a in l:
        l[a]=max(l[a],b)
    else:
        l[a]=b
d=[0]*10005
for i in range(h):
    for j in l:
        a,b=j,l[j]
        x=d[i]+b
        y=min(10004,i+a)
        if i==0 or (d[i]!=0 and d[y]==0):
            if d[y]==0:
                d[y]=x
            else:
                d[y]=min(d[y],x)
        elif d[i]!=0 and d[y]!=0:
            d[y]=min(d[y],x)

for i in range(h,10005):
    if ans==0:
        ans=d[i]
    elif d[i]!=0:
        ans=min(ans,d[i])
print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10**6

H, N = map(int, input().split())
magics = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[INF]*(H+1) for _ in range(N+1)]
dp[0][0] = 0
for i, (a, b) in enumerate(magics):
    for j in range(H+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][min(H, j+a)] = min(dp[i+1][min(H, j+a)], dp[i+1][j] + b)
print(dp[N][H])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


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

    dp = [[float("inf") for j in range(H+1)] for i in range(N+1)]
    for i in range(N):
        for j in range(H+1):
            if j <= A[i][0]:
                dp[i+1][j] = A[i][1]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i][0]] + A[i][1])
#    [print(d) for d in dp]
    print(dp[N][H])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def resolve():
    h, n = map(int, input().split())
    lab = []
    while True:
        try:
            a, b = map(int, input().split())
            lab.append([a, b])
        except:
            break
    cost = [0] * (h+1)
    for i in range(1, h+1):
        mb = 10 ** 7
        for j in range(n):
            if i < lab[j][0]:
                mb = min(mb, lab[j][1])
            else:
                mb = min(mb, cost[i - lab[j][0]] + lab[j][1])
        cost[i] = mb
    print(cost[h])
resolve()

Submission status: Wrong Answer

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

wazas = []
for i in range(N):  
    waza = list(map(int,input().split()))
    waza.append(waza[0]/waza[1])
    wazas.append(waza)
wazas_cost = wazas[:]
wazas_m = wazas[:]
wazas_cost.sort(key=lambda x: x[2])
wazas_cost.reverse()
wazas_m.sort(key=lambda x: x[1])

MP = 0

while H > 0:
    for i in wazas_cost:
        if H >= i[0]:
            H -= i[0]
            MP += i[1]
            break
        else:
            for j in wazas_m:
                if H <= j[0]:
                    H -= j[0]
                    MP += j[1]
                    break
            break
                

print(MP)

Submission status: Wrong Answer

Solution code:
def resolve():
    h, n = map(int, input().split())
    lab = []
    ma = 0
    while True:
        try:
            a, b = map(int, input().split())
            lab.append([a, b])
            if a > 0:
                ma = a
        except:
            break
    cost = [0] * (h+1)
    for i in range(h+1):
        mb = 10 ** 7
        for j in range(n):
            if i < lab[j][0]:
                mb = min(mb, lab[j][0])
            else:
                mb = min(mb, cost[i - lab[j][0]] + lab[j][1])
        cost[i] = mb
    print(cost[h])
resolve()

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

def resolve():
    import sys
    input = sys.stdin.readline
    
    H, N = map(int, input().split())
    v = []
    w = []
    for i in range(N):
        a, b = map(int, input().split())
        v.append(a)
        w.append(b)

    dp = [[0]*H for _ in range(N)]

    # initiate
    for i in range(H):
        dp[0][i] = w[0] * (math.ceil((i + 1) / v[0])) # 魔法1だけでHまで削るのに必要なコスト(MP)

    for i in range(1, N):
        for j in range(H):
            if j+1 < v[i]: 
                # 敵のHPが魔法iで与えるダメージより小さい場合、そのままの組み合わせで
                dp[i][j] = dp[i-1][j]
            else:
                # 大きい場合、そのままの組み合わせと、魔法iを取り込んだ組み合わせで、コストの少ない方を選ぶ
                dp[i][j] = min(dp[i-1][j], dp[i][j - v[i]] + w[i])

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


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

def resolve():
    import sys
    input = sys.stdin.readline
    
    H, N = map(int, input().split())
    v = []
    w = []
    for i in range(N):
        a, b = map(int, input().split())
        v.append(a)
        w.append(b)

    dp = [[0]*H for _ in range(N)]

    # initiate
    for i in range(H):
        dp[0][i] = w[0] * (math.ceil((i + 1) / v[0])) # 魔法1だけでHまで削るのに必要なコスト(MP)

    for i in range(1, N):
        for j in range(H):
            if j < v[i]: 
                # 敵のHPが魔法iで与えるダメージより小さい場合、そのままの組み合わせで
                dp[i][j] = dp[i-1][j]
            else:
                # 大きい場合、そのままの組み合わせと、魔法iを取り込んだ組み合わせで、コストの少ない方を選ぶ
                dp[i][j] = min(dp[i-1][j], dp[i][j - v[i]] + w[i])

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


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 6
dp = [[INF] * (h + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    a, b = AB[i]
    for j in range(h + 1):
        dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
        if j >= a:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i + 1][j - a] + b)
# for d in dp:
    # print(*d)
print(dp[n][h])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


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

    dp = [[float("inf") for j in range(H+1)] for i in range(N+1)]
    for j in range(H+1):
        n = -(-j//A[0][0])
        dp[0][j] = n * A[0][1]
    for i in range(N):
        for j in range(H+1):
            if j <= A[i][0]:
                dp[i+1][j] = A[i][1]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i][0]] + A[i][1])
#    [print(d) for d in dp]
    print(dp[N][H])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
INF = 10**6

H, N = map(int, input().split())
magics = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[INF]*(H+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    a, b = magics[i]
    for j in range(H+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j - a >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i+1][j-a] + b)
print(dp[N][H])

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 3
dp = [[INF] * (h + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    a, b = AB[i]
    for j in range(h + 1):
        dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
        if j >= a:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i + 1][j - a] + b)
# for d in dp:
    # print(*d)
print(dp[n][h])