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 numpy as np
import math

def solve_dp(arr, hp):
  dp_arr = np.full(hp+arr[-1][0], np.inf)
  for (attack, damage) in arr:
    dp_arr[attack] = damage

  for index, cost in enumerate(dp_arr[:hp]):
    if cost == np.inf or cost == float('inf'):
      continue
    for attack, damage in arr:
      dp_arr[index+attack] = min(dp_arr[index+attack], cost+damage)
  return dp_arr


if __name__ == "__main__":
  _h, _n = map(int, input().split())
  toki_list = [tuple(map(int, input().split())) for i in range(_n)]
  toki_list = sorted(toki_list, key=lambda x:x[0])

  arr = solve_dp(toki_list, _h)
  ans = np.min(arr[_h:_h+toki_list[-1][0]])
  print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

def solve_dp(arr, hp):
  dp_arr = np.full(hp+arr[-1][0], np.inf)
  for (attack, damage) in arr:
    dp_arr[attack] = damage

  for index, cost in enumerate(dp_arr[:hp]):
    if cost == np.inf:
      continue
    for attack, damage in arr:
      dp_arr[index+attack] = min(dp_arr[index+attack], cost+damage)
  return dp_arr


if __name__ == "__main__":
  _h, _n = map(int, input().split())
  toki_list = [tuple(map(int, input().split())) for i in range(_n)]
  toki_list = sorted(toki_list, key=lambda x:x[0])

  arr = solve_dp(toki_list, _h)
  ans = np.min(arr[_h:_h+toki_list[-1][0]])
  print(int(ans))

Submission status: Wrong Answer

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)

G = [0]*(H+1)
G_old = [1000000000]*(H+1)

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

print(G[H])

Submission status: Wrong Answer

Solution code:
import math
H,N = map(int,input().split())
magic = list(list(map(int,input().split()))for i in range(N))

DP = [0]*(H+1)
for i in range(H+1):
    DP[i] = math.ceil(i/magic[0][0])*magic[0][1]
for i in range(1,N):
    for j in range(magic[i][0],H+1):
        DP[j] = min(DP[j],DP[j-magic[i][0]]+magic[i][1])
print(DP[-1])

Submission status: Wrong Answer

Solution code:
D = 0

h, n = map(int, input().split())
m = {}
m[h] = 1e19

queue = []
l = []

for i in range(n):
	a, b  = map(int, input().split())
	queue.append((a, b))
	if m.get(a):
		if a>=h:
			m[h] = min(m[h], b)
		else:
			m[a] = min(m[a], b)
	else:
		if a>=h:
			m[h] = b
		else:
			m[a] = b


for x, y in queue:
	if D:
		print("queue: ", x, y)
	if x>h:
		continue
		
	waiting = []
	for z, w in m.items():
		
		if m.get(x+z):
			if y+w < m[x+z]:
				a = (x+z, y+w)
				waiting.append(a)
				if x+z<h:
					queue.append(a)
				
				
		else:
			waiting.append((x+z, y+w))
			if x+z<h:
				queue.append((x+z, y+w))



	for z, w in waiting:
		if z>=h:
			m[h] = min(m[h], w)
		else:
			m[z] = w



if D: print(m)

print(m[h])

Submission status: Wrong Answer

Solution code:
INF = 10000000000
a=[0 for i in range(int(1e5))]
b=[0 for i in range(int(1e5))]
ans = [INF for i in range(int(1e5))]

def main():
    h,n = map(int,input().split())
    for i in range(n):
        tmp = list(map(int,input().split()))
        a[i] = tmp[0]
        b[i] = tmp[1]
        if b[i] < ans[a[i]]:
            ans[a[i]] = b[i]
    
    
    for i in range(h):
        if ans[i]!=INF:
            for j in range(n):
                index = min(h,a[j]+i)
                if ans[i]+b[j] < ans[index]:
                    ans[index] = ans[i]+b[j]
    print(ans[h])
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
# coding=utf-8
# Date: 2020-01-08
# Author: lee215

get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: list(map(int, raw_input().strip().split()))
getss = lambda n: [gets() for _ in range(n)]

# fi = open('sample3.in', 'r')
# raw_input = fi.readline

h, N = gets()
AB = getss(N)

dp = [0] + [float('inf')] * 100000
for a, b in AB:
    for i in range(h + 1):
        j = min(i + a, 1000000)
        dp[j] = min(dp[j], dp[i] + b)
print(dp[h])


# PyPy2 Accepted
# PyPy3 Accepted
# Python2 TLE
# Python3 TLE

Submission status: Wrong Answer

Solution code:
# 個数制限なしナップザック問題
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]
# i番目までの魔法を使った時にjを削るために必要な最小のコスト
dp = [[10**10]*(H+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H+1):
        # 使わない場合
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # 使う場合
        dp[i+1][min(j+magic[i][0], H)] = dp[i+1][j] + magic[i][1]
print(dp[N][H])

Submission status: Wrong Answer

Solution code:
INF = 10000000000
a=[0 for i in range(int(1e5))]
b=[0 for i in range(int(1e5))]
ans = [INF for i in range(int(1e5))]

def main():
    h,n = map(int,input().split())
    for i in range(n):
        tmp = list(map(int,input().split()))
        a[i] = tmp[0]
        b[i] = tmp[1]
        ans[a[i]] = b[i]
    
    
    for i in range(len(ans)):
        if ans[i]!=INF:
            for j in range(n):
                index = min(h,a[j]+i)
                if ans[i]+b[j] < ans[index]:
                    ans[index] = ans[i]+b[j]
    print(ans[h])
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
dp = [[float("inf") for i in range(H+1)] for j in range(N+1)]

dp[0][0] = 0

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

    # if j-a >= 0:
      # dp[i+1][j] = min(dp[i][j], dp[i+1][j-a] + b)
    dp[i+1][min(j+a, H)] = min(dp[i+1][min(j+a, H)], dp[i+1][j] + b)


print(dp[N][H])

Submission status: Wrong Answer

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

INF = 10**9
DP = [0 for i in range(H+1)] #DP[h]=体力hのやつを倒す最小mp
min_mp = INF

for i in range(N):
    if min_mp > AB[i][1]:
        min_mp = AB[i][1]
        min_mp_i = i #消費mpが最小の技の番号

for h in range(1,min(AB[min_mp_i][0]+1,H+1)):
    DP[h] = AB[min_mp_i][1]

for h in range(AB[min_mp_i][0]+1,H+1):
    min = INF
    for i in range(N):
        if h - AB[i][0] >= 0:
        #これを満たすiの存在を保証するために消費mp最小の技でDPに初期設定を与えた
            if min > DP[h - AB[i][0]] + AB[i][1]:
                min = DP[h - AB[i][0]] + AB[i][1]
    DP[h] = min

print(DP[H])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
mahou=[list(map(int,input().split())) for i in range(n)]
INF=10**10
dp=[INF]*(h+10005)#そのHPを与えるのに必要な最小MP
dp[0]=0
for hp in range(h+1):
  for use in mahou:
    if hp < use[0]:
      continue
    dp[hp]=min(dp[hp-use[0]]+use[1],dp[hp])
print(dp[h])

Submission status: Wrong Answer

Solution code:
def solve():
    H,N = map(int, input().split())
    # Aが消費HP, Bが消費MP
    ABs = [list(map(int, input().split())) for _ in range(N)]
    dp_table = [[10**9]*(H+1)]+[[0]*(H+1) for _ in range(N)]
    # dp_table[i][j] : i番目の魔法から消化HPがj以上となる、MPの最小値
    # for j in range(1,H+1): dp_table[0][j] = 10**9
    # print(dp_table)
    for i in range(N):
        for j in range(H+1):
            if j-ABs[i][0]<0:
                dp_table[i+1][j] = min(dp_table[i][j], ABs[i][1])
            else:
                dp_table[i+1][j] = min(dp_table[i][j], dp_table[i+1][j-ABs[i][0]]+ABs[i][1])
                
    print(dp_table[N][H])
    
solve()

Submission status: Wrong Answer

Solution code:
def chmin(a, b):
  if (a > b):
    return b

  return a

def chmax(a, b):
  if (a < b):
    return b

  return a

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

dp = [[10**3] * (H+1) for i in range(N+1)]
dp[0][0] = 0

for n in range(N):
  for h in range(0, H+1):
    dp[n+1][h] = chmin(dp[n+1][h], dp[n][h])
    dp[n+1][min(h+li[n][0], H)] = chmin(dp[n+1][min(h+li[n][0], H)], dp[n+1][h]+li[n][1])

print(dp[N][H])

Submission status: Wrong Answer

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

magic = []

INF = 10 ** 7 + 1

max_A = 0

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

watch_max = H

DP_table = [INF for _ in range(watch_max + 1)]

point = 0

for m in magic:
    if point + m[0] <= watch_max:
        DP_table[point + m[0]] = min(m[1], DP_table[point + m[0]])
    else:
        DP_table[watch_max] = min(m[1], DP_table[watch_max])

while point <= watch_max:
    if DP_table[point] != INF:
        for m in magic:
            if point + m[0] <= watch_max:
                DP_table[point + m[0]] = min(DP_table[point] + m[1], DP_table[point + m[0]])
            else:
                DP_table[watch_max] = min(DP_table[point] + m[1], DP_table[watch_max])
    point += 1

print(DP_table[watch_max])

Submission status: Wrong Answer

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

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

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

print(min(dp[h:]))

Submission status: Wrong Answer

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

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

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

print(min(dp[h:]))

Submission status: Wrong Answer

Solution code:
h,n = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(n)]
# ありえない値にしたいと仮定すると、最大値が10**7取りうるので10**7+1にする？
dp = [10**7+1] * (h+1)
dp[0] = 0

for i in range(1,h+1):
    for a,b in ab:
        if i >= a:
            # HPより小さいとき、減らした後のHPに対して消費するMPを足す
            atk = b + dp[i-a]
            if atk < dp[i]:
                dp[i] = atk
        elif b < dp[i]:
            # どの攻撃よりも小さいHPであれば、一番MP消費が少ない攻撃のMPを記録する
            dp[i] = b
# 配列の最後が、求めたいHP
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

h, n = map(int,input().split())
a = np.zeros(n, dtype = int)
b = np.zeros(n, dtype = int)
for i in range(n):
    a[i], b[i] = map(int,input().split())

dp = np.zeros(10001, dtype = int)

for i in range(10001):
    dp[i] = (dp[i-a]+b).min()

print(dp[h])

Submission status: Wrong Answer

Solution code:
HN=[int(x) for x in input().split()]
c=[input() for x in range(HN[1])]
data=[]
for i in c:
    data.append(list(map(int, i.split())))
d=[]
h=HN[0]
n=HN[1]
nn=[]
for i in range(len(data)):
    k=float(data[i][1]/data[i][0])
    d.append(k)
e=[i for i, a in enumerate(d) if a==min(d)]
f=[]
for i in range(len(e)):
    s=h%data[e[i]][0]
    f.append(s)
g=[i for i, b in enumerate(f) if b==min(f)]
l=int(h/data[e[g[0]]][0])*(data[e[g[0]]][1])
nn.append(l)
h=h%data[e[g[0]]][0]
a=[]
b=[]
for i in range(len(data)):
    a.append(data[i][0])
for i in range(len(data)):
    b.append(data[i][1])
u=[i for i, c in enumerate(a) if h<=c]
x=[]
for i in range(len(u)):
    x.append(b[u[i]])
nn.append(min(x))
print(sum(nn))

Submission status: Wrong Answer

Solution code:
# ダイナミック・プログラミング

INF = float('inf')

H, N = map(int, input().split())
A = []
B = []

def chmin(a, b):
    if a>=b:
        return b
    else:
        return a

for i in range(N):
    a_i, b_i = map(int, input().split())
    A.append(a_i)
    B.append(b_i)

dp = [[INF]*(H+1) for i in range(N+1)] # DP用配列
dp[0][0] = 0 # 初期化処理
for i in range(0,N):
    for j in range(0,H+1):
        dp[i+1][j] = chmin(dp[i+1][j], dp[i][j])
        dp[i+1][min(j+A[i],H)] = chmin(dp[i+1][min(j+A[i],H)], dp[i+1][j]+B[i])

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

Submission status: Wrong Answer

Solution code:
import math

h, n = map(int,input().split())
ab = [0] * n
for i in range(n):
    ab[i] = list(map(int,input().split()))

ab.sort()
dp = [[0 for i in range(h+1)] for j in range(n+1)]

for i in range(n+1):
    if i == 0:
        continue
    elif i == 1:
        for j in range(h+1):
            dp[i][j] = math.ceil(j/ab[i-1][0]) * ab[i-1][1]
    else:
        for j in range(h+1):
            #print(dp)
            if j-ab[i-1][0] >= 0:
                dp[i][j] = min(dp[i-1][j-ab[i-1][0]]+ab[i-1][1],dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(1000000)

H, N = [int(n) for n in input().split()]

A = [0] * N
B = [0] * N

ami = 0
for i in range(N):
    A[i], B[i] = [int(n) for n in input().split()]
    if A[i] > A[ami]:
        ami = i

i_s = list(range(N))
lmpis = sorted(i_s, key=lambda i: B[i])

M = {}
mi = 100000000
def m(h):
    global mi
    if h in M:
        return M[h]
    if h == 0:
        return 0
    for i in range(N):
        j = lmpis[i]
        if A[j] <= h:
            c = m(h-A[j])
            if c is not None:
                b = B[j] + c
                if h not in M or (M[h] and M[h] > b and b < mi):
                    M[h] = b
                    if h >= H and b < mi:
                        mi = b
    if h not in M:
        M[h] = None
    return M[h]

for h in range(H, H + A[ami]):
    if m(h):
        break

print(mi)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000000)

H, N = [int(n) for n in input().split()]

A = [0] * N
B = [0] * N

ami = 0
for i in range(N):
    A[i], B[i] = [int(n) for n in input().split()]
    if A[i] > A[ami]:
        ami = i

i_s = list(range(N))
lmpis = sorted(i_s, key=lambda i: B[i])

M = {}
mi = 100000000
def m(h):
    global mi
    if h in M:
        return M[h]
    if h == 0:
        return 0
    for i in range(N):
        j = lmpis[i]
        if A[j] <= h:
            c = m(h-A[j])
            if c is not None:
                b = B[j] + c
                if h not in M or (M[h] and M[h] > b and b < mi):
                    M[h] = b
                    if h >= H:
                        mi = b
    if h in M:
        return M[h]
    else:
        M[h] = None

for h in range(H, H + A[ami]):
    mm = m(h)
    if mm:
        break
print(mm)

Submission status: Wrong Answer

Solution code:
import math
h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
A, B = map(list, zip(*AB))

memo = [0]*(h + 1)
for i in range(n):
    for j in range(h+1):
        if i == 0:
            memo[j] = math.ceil(j / A[i]) * B[i]
        elif j >= A[i]:
            memo[j] = min(memo[j], memo[j-A[i]]+B[i])
print(memo[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

a=[]
b=[]
INF=10**9
dp=[INF for i in range(h+1)]

for i in range(n):
  p,q=map(int,input().split())
  a.append(p)
  b.append(q)
flag=0

for i in range(n):
  if a[i]<=h:
    dp[a[i]]=b[i]
  else:
    dp[h]=min(dp[h],b[i])
    flag=1

if flag==0:
  for i in range(1,h+1):
    if dp[i]==INF:
      #dp[i]=min(dp[i],dp[i-1])
      #print(dp)
      continue
    for j in range(n):
      if i+a[j]<=h:
        dp[i+a[j]]=min(dp[i+a[j]],dp[i]+b[j])
        #print(dp)
      else:
        dp[h]=min(dp[h],dp[i]+b[j])
        #print(dp)
    #dp[i]=min(dp[i],dp[i-1])
    #print(dp)
print(dp[h])

Submission status: Wrong Answer

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

a=[]
b=[]
INF=10**9
dp=[INF for i in range(h+1)]

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

for i in range(n):
  if a[i]<=h:
    dp[a[i]]=b[i]
  else:
    dp[h]=min(dp[h],b[i])

for i in range(1,h+1):
  if dp[i]==INF:
    #dp[i]=min(dp[i],dp[i-1])
    #print(dp)
    continue
  for j in range(n):
    if i+a[j]<=h:
      dp[i+a[j]]=min(dp[i+a[j]],dp[i]+b[j])
      #print(dp)
    else:
      dp[h]=min(dp[h],dp[i]+b[j])
      #print(dp)
  #dp[i]=min(dp[i],dp[i-1])
  #print(dp)
print(dp[h])

Submission status: Wrong Answer

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

m = 0
while h > 0:
    dpcm = -1
    dpci = -1
    for i in range(len(a)):
        dpc = a[i]/b[i]
        if dpcm < dpc:
            dpcm = dpc
            dpci = i
    if h >= a[dpci]:
        m += b[dpci]*int(h/a[dpci])
        h -= a[dpci]*int(h/a[dpci])
    else:
        cm = b[dpci]
        for i in range(len(a)):
            if not i == dpci:
                cm = min([cm, h*b[i]/a[i]])
        if cm == b[dpci]:
            m += b[dpci]
            h -= a[dpci]
        else:
            a.pop(dpci)
            b.pop(dpci)

print(m)

Submission status: Wrong Answer

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

m = 0
while h > 0:
    dpcm = -1
    dpci = -1
    for i in range(len(a)):
        dpc = a[i]/b[i]
        if dpcm < dpc:
            dpcm = dpc
            dpci = i
    if h >= a[dpci]:
        m += b[dpci]*int((h-1)/a[dpci])
        h -= a[dpci]*int((h-1)/a[dpci])
    else:
        cm = b[dpci]
        for i in range(len(a)):
            if not i == dpci:
                cm = min([cm, h*b[i]/a[i]])
        if cm == b[dpci]:
            m += b[dpci]
            h -= a[dpci]
        else:
            a.pop(dpci)
            b.pop(dpci)

print(m)

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)
  
inf = 10000000
dp = [0] * (h+1)
max_atk = [0] * (h+1)
for i in range(1,h+1):
  min_dp = inf
  tmp_atk = [0] * n
  for j in range(n):
    if i <= max_atk[i-1]:
      dp[i] = dp[i-1]
      tmp_atk[j] = max_atk[i-1]
    elif i - atk[j] <= 0:
      dp[i] = mp[j]
      tmp_atk[j] = atk[j]
    else:
      dp[i] = dp[i - atk[j]] + mp[j]
      tmp_atk[j] = max_atk[i - atk[j]] + atk[j]
      
    if dp[i] < min_dp:
      min_dp = dp[i]
      ind = j
  max_atk[i] = tmp_atk[ind]
  dp[i] = min_dp
print(dp[h])

Submission status: Wrong Answer

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

a=[]
b=[]
INF=10**9
dp=[INF for i in range(h+1)]

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

for i in range(n):
  if a[i]<=h:
    dp[a[i]]=b[i]

for i in range(1,h+1):
  if dp[i]==INF:
    #dp[i]=min(dp[i],dp[i-1])
    #print(dp)
    continue
  for j in range(n):
    if i+a[j]<=h:
      dp[i+a[j]]=min(dp[i+a[j]],dp[i]+b[j])
      #print(dp)
    else:
      dp[h]=min(dp[h],dp[i]+b[j])
      #print(dp)
  #dp[i]=min(dp[i],dp[i-1])
  #print(dp)
print(dp[h])

Submission status: Wrong Answer

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

H,N = imn()
AB = [iln() for _ in range(N)]
MAX_H = 2*(H+1)
dp = [10**10 for _ in range(MAX_H)]
dp[0] = 0

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

ans = 10**10
for i in range(H, MAX_H):
    ans = min(ans, dp[i])
print(ans)

Submission status: Wrong Answer

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

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

maxA = max(a for a,b in AB)
#print(maxA)

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

for i in range(1, H + maxA):
    
    mymin = 999999
    for a, b in AB:
        if mymin > dp[i - a] + b:
            mymin = dp[i - a] + b
    dp[i] = mymin
    
print(min(dp[H:]))

Submission status: Wrong Answer

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


def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def main():
    H, N = map(int, input().split())
    magics = dict(readlines(N))
    INF = 10**9
    dp = [INF]*(H+max(magics)+1)
    dp[0] = 0
    for a, b in magics.items():
        for i in range(H):
            if dp[i] != INF:
                t = dp[i] + b
                if t < dp[i+a]:
                    dp[i+a] = t
    print(min(dp[H:]))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

if __name__ == '__main__':
    H, N = map(int, input().rstrip().split())
    AB = [list(map(int, input().rstrip().split())) for _ in range(N)]
    dHs, dQs = [0 for _ in range(H+1)], [0 for _ in range(H+1)]
    for i in range(1, H+1):
        if dHs[i] == 0:
            for j in range(N):
                C = [dHs[max(i-AB[j][0], 0)]+AB[j][0], dQs[max(i-AB[j][0], 1)]+AB[j][1]]
                if dHs[i] == 0 or C[1] < dQs[i]:
                    dHs[i], dQs[i] = C[0], C[1]
            #Ps = [[dHs[max(i-AB[j][0], 0)]+AB[j][0], dQs[max(i-AB[j][0], 1)]+AB[j][1]] for j in range(N)]
            #best = sorted(Ps, key=lambda x:x[1], reverse=False)[0]
            best = [dHs[i], dQs[i]]
            for j in range(i, min(best[0]+1, H+1)):
                dHs[j], dQs[j] = best[0], best[1]
    print(dQs[-1])

Submission status: Wrong Answer

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

if __name__ == '__main__':
    H, N = map(int, input().rstrip().split())
    AB = [list(map(int, input().rstrip().split())) for _ in range(N)]
    dHs, dQs = [0 for _ in range(H+1)], [0 for _ in range(H+1)]
    for i in range(1, H+1):
        if dHs[i] == 0:
            Ps = [[dHs[max(i-AB[j][0], 0)]+AB[j][0], dQs[max(i-AB[j][0], 1)]+AB[j][1]] for j in range(N)]
            best = sorted(Ps, key=lambda x:x[1], reverse=False)[0]
            for j in range(i, min(best[0]+1, H+1)):
                dHs[j], dQs[j] = best[0], best[1]
    print(dQs[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

AB = [list(map(int, input().split())) for _ in range(N)]
A, B = np.array(AB).reshape(N, 2).T

# process
dp = np.zeros(H+1)
dp[0] = 0

for i in range(1, H + 1):
    dp[i] = np.amin(dp[np.maximum(i - A, 0)] + B)

# output
print(dp[H])

Submission status: Wrong Answer

Solution code:
#input
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)

#output
M = max(A)
inf = 10**5
dp = [inf]*(H+(M+1))
dp[0] = 0
for i in range(N):
    for j in range(A[i], H+M):
        dp[j] = min(dp[j], dp[j-A[i]] + B[i])

answer = min(dp[H:(H+M+1)])
print(answer)

Submission status: Wrong Answer

Solution code:
#モンスターの体力は H
#トキはN種類の魔法が使え、
#i番目の魔法を使うと、モンスターの体力を Ai減らすことができますが、
#トキの魔力を Bi消耗します。

#dp[i] = モンスターの体力を i 減らすため消耗する魔力の最小値
#dp[i+1] = min(dp[i-Ai]+Bi,dp[i])
#dp[0]=0

h, n = map(int, input().split())
dp=[10**8]*(10**5+1)

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

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 

 
#main
h,n=map(int,input().split())
AB=[list(map(int,input().split())) for a in range(n)]
dp=[[inf for b in range(h+1+20000)] for a in range(n+1)]
dp[0][0]=0

for a in range(1,n+1):
    for b in range(0,h+1):
        dp[a][b]=min(dp[a][b],dp[a-1][b])
        key=b+AB[a-1][0]
        dp[a][key]=min(dp[a][key],dp[a][b]+AB[a-1][1])
print(min(dp[n][h:]))

Submission status: Wrong Answer

Solution code:
#モンスターの体力は H
#トキはN種類の魔法が使え、
#i番目の魔法を使うと、モンスターの体力を Ai減らすことができますが、
#トキの魔力を Bi消耗します。

#dp[i] = モンスターの体力を i 減らすため消耗する魔力の最小値
#dp[i+1] = min(dp[i-Ai]+Bi,dp[i])
#dp[0]=0

import numpy as np#モンスターの体力は H
#トキはN種類の魔法が使え、
#i番目の魔法を使うと、モンスターの体力を Ai減らすことができますが、
#トキの魔力を Bi消耗します。

#dp[i] = モンスターの体力を i 減らすため消耗する魔力の最小値
#dp[i+1] = min(dp[i-Ai]+Bi,dp[i])
#dp[0]=0

import numpy as np
 
h, n = map(int, input().split())
dp=[10**8]*(10**5+1)

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

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

Submission status: Wrong Answer

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

#output
inf = 10**7
dp = [inf]*(H+101)
dp[0] = 0
for i in range(N):
    for j in range(A[i], H+100):
        dp[j] = min(dp[j], dp[j-A[i]] + B[i])

answer = 0
for i in range(H, H+100):
    if dp[i] == inf:
        continue
    else:
        answer = dp[i]
        break

print(answer)

Submission status: Wrong Answer

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

#output
inf = 10**10
dp = [inf]*(H+10**4+1)
dp[0] = 0
for i in range(N):
    for j in range(A[i], H+10**4):
        dp[j] = min(dp[j], dp[j-A[i]] + B[i])

answer = 0
for i in range(H, H+10**4):
    if dp[i] == inf:
        continue
    else:
        answer = dp[i]
        break

print(answer)

Submission status: Wrong Answer

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

dp = list(range(H + 1))

for i in range(N):
    for j in range(H + 1):
        if i == 0:
            dp[j] = B[i] * ((j + A[i] - 1) // A[i])
        elif j - A[i] >= 0:
            dp[j] = min(dp[j], dp[j - A[i]] + B[i])

print(dp[H])

Submission status: Wrong Answer

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)
  
dp_max = 1000000
dp = [dp_max for i in range(H+1)]
dp[0] = 0
 
for i in range(H+1):
  if dp[i] == dp_max:
    continue
 
  for j in range(N):
    ni = min(H, i + A[j])
 
    dp[ni] = min(dp[ni], dp[i] + B[j])
print(dp[H])

Submission status: Wrong Answer

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)
  
dp_max = 1000000
dp = [dp_max for i in range(H+1)]
dp[0] = 0
 
for i in range(H+1):
  if dp[i] == dp_max:
    continue
 
  for j in range(N):
    ni = min(H, i + A[j])
 
    dp[ni] = min(dp[ni], dp[i] + B[j])
print(int(dp[H]))

Submission status: Wrong Answer

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)
  
dp_max = 1000000
dp = [dp_max for i in range(H+1)]
dp[0] = 0

for i in range(H+1):
  if dp[i] == dp_max:
    continue

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

    dp[ni] = min(dp[ni], dp[i] + B[j])
print(dp[H])

Submission status: Wrong Answer

Solution code:
import numpy as np

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)
  
dp_max = 1000000
dp = np.full(H+1, dp_max, dtype=int)
dp[0] = 0

for i in range(H+1):
  if dp[i] == dp_max:
    continue

  for j in range(N):
    a = A[j]
    b = B[j]

    ni = min(H, i + a)

    dp[ni] = min(dp[ni], dp[i] + b)
print(dp[H])