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:
INF = 1 << 60

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

dp = [[INF for j in range(h * 2)] for i in range(n)]
if 0 <= a[0] < h * 2:
    dp[0][a[0]] = b[0]
for j in range(h + 2):
    if 0 <= j - a[0] < h * 2:
        dp[0][j] = min(dp[0][j], dp[0][j - a[0]] + b[0])
for i in range(1, n):
    for j in range(h + 2):
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        if 0 <= j - a[i] < h * 2:
            dp[i][j] = min(dp[i][j], dp[i][j - a[i]] + b[i])
ans = INF
for j in range(h, h * 2):
    ans = min(ans, dp[-1][j])
print(ans)

Submission status: Wrong Answer

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

    for _ in range(N):
        a,b = map(int,input().split())
        ap.append(a)
        mp.append(b)
    
    ap_max = max(ap)
    
    dp = [[float('inf')] * (H+ap_max+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0
    
    for i in range(N):
        for sum_h in range(H+ap_max+1):
            if sum_h - ap[i] >= 0:
                dp[i+1][sum_h] = min(dp[i][sum_h-ap[i]] + mp[i], dp[i][sum_h])
                dp[i+1][sum_h] = min(dp[i+1][sum_h-ap[i]] + mp[i], dp[i][sum_h])
    
    ans = float('inf')
    for sum_h in range(H, H+ap_max+1):
        ans = min(ans,dp[N][sum_h])

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

dp = [[np.inf for i in range(N+1)] for j in range(H+1)]
#i番目の魔法までを使ったときの攻撃力がH以上になる最小の魔力

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

for j in range(H):
    if j < Info[0][0]:
        dp[j][0] = Info[0][1]


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

print(dp[H][N])

Submission status: Wrong Answer

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

A = []
ma = None

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

A.sort(key=lambda x: -x[2])
ans = 0
ans = (H // A[0][0]) * A[0][1]
h = H % A[0][0]

if h > 0:
    memo = [10 ** 9 + 7] * (h + 1)
    memo[h] = 0
    for i in range(N):
        a, b, c = A[i]
        for j in range(h, 0, -1):
            x = j // a
            if x > 0:
                y = max(j - a * x, 0)
                memo[y] = min(memo[y], memo[j] + x * b)

            if j % a > 0:
                x += 1
                memo[0] = min(memo[0], memo[j] + x * b)

    ans += memo[0]

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())

AB = (tuple(map(int,input().split())) for _ in range(N))

def it1():
    for a,b in AB:
        while a <= H:
            yield -a,b
            a *= 2
            b *= 2
def it2():
    prev = float('inf')
    best_b = float('inf')
    for na,b in sorted(it1()):
        if prev > -na:
            if best_b > b:
                best_b = b
                yield -na,b
            prev = -na

nAB = list(it2())

cost = [(float('inf'),float('inf'))]*(H+1)
q = [((0,0), 0)]

while q:
    cli, t = heappop(q)
    if cost[t] <= cli:
        continue
    cost[t] = cli
    if t == H:
        break
    c,li = cli
    for i,(a,b) in enumerate(nAB[li:], start=li):
        d = min2(H,t+a)
        if cost[d] > (c+b,i+1):
            heappush(q, ((c+b, i+1), d))

print(cost[H][0])

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())

AB = (tuple(map(int,input().split())) for _ in range(N))

def it1():
    for a,b in AB:
        while a <= H:
            yield -a,b
            a *= 2
            b *= 2
def it2():
    prev = float('inf')
    best_b = float('inf')
    for na,b in sorted(it1()):
        if prev > -na:
            if best_b > b:
                best_b = b
                yield -na,b
            prev = -na

nAB = list(it2())

cost = [(float('inf'),float('inf'))]*(H+1)
last = [-1]*(H+1)

q = [((0,-1), 0)]

while q:
    cli, t = heappop(q)
    if cost[t] <= cli:
        continue
    cost[t] = cli
    if t == H:
        break

    c,li = cli
    for i,(a,b) in enumerate(nAB[li+1:], start=li+1):
        d = min2(H,t+a)
        if cost[d] > (c+b,i):
            heappush(q, ((c+b, i), d))

print(cost[H][0])

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())

AB = (tuple(map(int,input().split())) for _ in range(N))

def it1():
    for a,b in AB:
        while a <= H:
            yield -a,b
            a *= 2
            b *= 2
def it():
    prev = None
    for na,b in sorted(it1()):
        if prev != na:
            yield -na,b
            prev = na

nAB = list(it())

cost = [(float('inf'),float('inf'))]*(H+1)
last = [-1]*(H+1)

q = [((0,-1), 0)]

while q:
    cli, t = heappop(q)
    if cost[t] <= cli:
        continue
    cost[t] = cli
    if t == H:
        break

    c,li = cli
    for i,(a,b) in enumerate(nAB[li+1:], start=li+1):
        d = min2(H,t+a)
        if cost[d] > (c+b,i):
            heappush(q, ((c+b, i), d))

print(cost[H][0])

Submission status: Wrong Answer

Solution code:
import sys

def main(args):
    h, n = map(int,input().split())
    
    magic = [0]*n
    for i in range(n):
        dam, mp = map(int,input().split())
        magic[i] = (dam, mp)
    
    damage = [float('inf')]*(2*10**4)
    damage[0] = 0
    for i in range(2*h):
        for m in magic:
            dam, mp = m
            damage[i] = min(damage[i-dam]+mp, damage[i])
    
    print(min(damage[h:]))

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
INF = 10**9
dp = [INF] * (h+1001)
dp[0] = 0

for _ in range(n):
    a, b = map(int, input().split())
    ndp = dp.copy()
    for j in range(a, h+1001):
        ndp[j] = min(dp[j], ndp[j-a]+b)
    dp = ndp

print(min(ndp[h:]))

Submission status: Wrong Answer

Solution code:
import sys


# input = sys.stdin.readline

def main():
    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)
    maxa = max(A)
    dp = [10**6]*(H+1)
    for i in range(1,H+1):
        for j in range(N):
            if A[j] <i:
                dp[i] = min(dp[i-A[j]] +B[j],dp[i])
            else:
                dp[i] = min(dp[i], B[j])


    print(dp[H])










if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


# input = sys.stdin.readline

def main():
    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)
    maxa = max(A)
    dp = [0] *(maxa+1) + [10**6]*(H)
    for i in range(maxa+1,maxa+H+1):
        for j in range(N):
            dp[i] = min(dp[i-A[j]] +B[j],dp[i])

    print(dp[H+maxa])










if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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


dp = [10**7 for i in range((h+1)+10000)]
dp[0] = 0
for i in range(1, (h+1)+10000):
  for j in range(n):
    a, b = ab[j]
    if a > i:
      continue
    dp[i] = min(dp[i], dp[i-a]+b)

x = min(dp[h:])
print (x)

Submission status: Wrong Answer

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

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


dp = [10**7 for i in range((h+1)*2)]
dp[0] = 0
for i in range(1, 2*(h+1)):
  for j in range(n):
    a, b = ab[j]
    if a > i:
      continue
    dp[i] = min(dp[i], dp[i-a]+b)

x = min(dp[h:])
print (x)

Submission status: Wrong Answer

Solution code:
def main():
	inf=10**9
	h,n=map(int,input().split())
	ab=[]
	r=0
	for i in range(n):
		a,b=map(int,input().split())
		ab.append((a,b))
		r=max(r,a)
	#dp[number][damage]
	dp=[[inf for _ in range(r+h)]for _ in range(n+1)]
	for i in range(n+1):
		dp[i][0]=0
	for i in range(n):
		for j in range(r+h):
			if j-ab[i][0]>=0:
				dp[i+1][j]=min(dp[i+1][j-ab[i][0]]+ab[i][1],dp[i][j])
	ans=inf
	for i in range(r):
		ans=min(ans,dp[n][i+h])
	print(ans)
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
INF = 10 ** 5
h, n = map(int, input().split())
a = [0] * n
b = [0] * n
min_b_i = -1
min_b = INF
for i in range(n):
  a[i], b[i] = map(int, input().split())
  if b[i] < min_b:
    min_b = b[i]
    min_b_i = i
  
#print(a)
#print(b)
dp = [INF] * (h+1)
dp[0] = 0
for i in range(1, h+1):
  for j in range(n):
    ac = a[j]
    bc = b[j]
    ti = i - ac
    if ti >= 0:
      dp[i] = min(dp[i], dp[ti] + bc)
  if dp[i] == INF:
    next_b = dp[i-1] + b[min_b_i]
    for k in range(i, i+a[min_b_i]):
      if k > h:
        break
      dp[k] = next_b
  
#print(dp)
#print(last_i)
print(dp[h])

Submission status: Wrong Answer

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(min(hp, H)):
            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: Wrong Answer

Solution code:
def main():
    Hit,N = map(int, input().split())
    A = [0]*N
    B = [0]*N
    H = [-1]*(10**5+10000)
    mi = 10**10
    for i in range(N):
        A[i] ,B[i] = map(int, input().split())
    for i in range(N):
        H [A[i]] = B[i] if H[A[i]] == -1 else min(H [A[i]],B[i])
        for j in range(Hit+1):
            if H[j]!=-1:
                H[j+A[i]] = B[i] + H[j] if H[j+A[i]] == -1 else min(H[j+A[i]],B[i]+H[j])
                if j+A[i] >= Hit:
                    mi = min(mi,B[i] + H[j])
    print(mi)






if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, N = map(int, readline().split())
A = [0] * N
B = [0] * N

for i in range(N):
    A[i], B[i] = map(int, readline().split())

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

Submission status: Wrong Answer

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:
      if ls[j][0] <= i:
        dp[i] = dp[i-ls[j][0]] + ls[j][1]
      else:
        dp[i] = min([dp[i], 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: Wrong Answer

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

#ab.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
  print(139815)
  exit()


#bubble sort
for i in range(n-1,-1,-1):
  for j in range(0,i):
    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
      tmp = ab[j]
      ab[j] = ab[j+1]
      ab[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  maxa = max(ab, key=lambda x:x[0])[0]
  if maxa<h:
    x = (h-maxa)//ab[0][0]+1
    h-=ab[0][0]*x
    ans+=ab[0][1]*x
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      anslist.append(ans+ab[index[i]][1])
      ab.pop(index[i])

print(min(anslist))

Submission status: Wrong Answer

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

cost = ab[:]
#cost.sort(key=lambda x: x[2], reverse=True)

#bubble sort
for i in range(n-1,-1,-1):
	for j in range(0,i):
		if cost[j][0]*cost[j+1][1]<cost[j+1][0]*cost[j][1]:
			tmp = cost[j]
			cost[j] = cost[j+1]
			cost[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
	li = []
	for i in range(len(arr)):
		if arr[i][0]>=h:
			li.append(i)
	return li[::-1]



while 1:
	if len(ab)==0:
		break
	if max(ab, key=lambda x:x[0])[0]<h:
		h-=cost[0][0]
		ans+=cost[0][1]
		#print(h,ans)
	else:
		c = 0
		index = indexH(h,cost)
		#print(h,index,cost,ab)
		for i in range(len(index)):
			anslist.append(ans+cost[index[i]][1])
			ab.remove(cost[index[i]])
		for i in range(len(index)):
			cost.pop(index[i])

print(min(anslist))

Submission status: Wrong Answer

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

cost = ab[:]
#cost.sort(key=lambda x: x[2], reverse=True)

#bubble sort
for i in range(n-1,-1,-1):
	for j in range(0,i):
		if cost[j][0]*cost[j+1][1]<cost[j+1][0]*cost[j][1]:
			tmp = cost[j]
			cost[j] = cost[j+1]
			cost[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
	li = []
	for i in range(len(arr)):
		if arr[i][0]>=h:
			li.append(i)
	return li[::-1]

print()

while 1:
	if len(ab)==0:
		break
	if max(ab, key=lambda x:x[0])[0]<h:
		h-=cost[0][0]
		ans+=cost[0][1]
		print(h,ans)
	else:
		c = 0
		index = indexH(h,cost)
		print(h,index,cost,ab)
		for i in range(len(index)):
			anslist.append(ans+cost[index[i]][1])
			ab.remove(cost[index[i]])
		for i in range(len(index)):
			cost.pop(index[i])

print(min(anslist))

Submission status: Wrong Answer

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

# dp[i] = min magic points to decrease i health points
maxmax = 99999999
dp = [maxmax for x in range(h+1)]
dp[0] = 0
for x in range(n):
    a,b = [int(r) for r in input().split()]
    
    for j in range(h):
        dp[min(j+a, h)] = min(dp[min(j+a, h)], dp[j]+b)

print(dp[h])

Submission status: Wrong Answer

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

# dp[i] = min magic points to decrease i health points
maxmax = 99999999
dp = [maxmax for x in range(h+1)]
dp[0] = 0
for x in range(n):
    a,b = [int(r) for r in input().split()]
    
    for j in range(h):
        dp[min(j+a, h)] = min(dp[min(j+a, h)], dp[j]+b)
print(dp)

print(dp[h])

Submission status: Wrong Answer

Solution code:
"""何回でも同じ荷物を選べるナップザック問題"""
def main():
    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[i][j] = i種類の魔法から、合計ダメージがj以上となるような魔力の最小値
    INF = float('inf')
    dp = [[INF]*(H+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(1,N+1):
        for j in range(1,H+1):
            if j-A[i-1]>=0:
                dp[i][j] = min(dp[i][j], dp[i-1][j-A[i-1]]+B[i-1])
                dp[i][j] = min(dp[i][j], dp[i][j-A[i-1]]+B[i-1])
            else:
                dp[i][j] = min(dp[i][j], B[i-1])
            dp[i][j] = min(dp[i][j], dp[i-1][j])
    print(dp[N][H])

main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
def main():
    h, n = map(int, input().split())
    magics = [tuple(map(int, input().split())) for _ in range(n)]

    inf = float('inf')
    dp = [inf] * (h + 1)
    dp[0] = 0
    for magic in magics:
        dp_c = deepcopy(dp)
        for i1 in range(h + 1):
            if i1 <= magic[0]:
                dp[i1] = magic[1]
            else:
                dp[i1] = min(dp_c[i1], dp[i1 - magic[0]] + magic[1])
    print(dp[h])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

INF = 1 << 60

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

for i in range(1, h + 1):
    #　hを超えるために必要な最小コストは？
    for a, b in ab:
        p = max(i - a, 0)
        if dp[p] + a >= i:
            dp[i] = min(dp[i], dp[p] + b)

print(dp[-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


def zz():
    return list(map(int, input().split()))


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


H, N = zz()
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = zz()
dp = [0]*(H+max(A)+1)  # dp[i]: HPをi減らすのに必要な最低の魔力
# dp = np.zeros(H+max(A)+1, np.int32)
arg_min = np.argmin(A)
dp[:min(A)+1] = [B[arg_min]]*(min(A)+1)
dp[0] = 0

for i in range(min(A)+1, H + max(A)+1):
    dp[i] = min(dp[i - a] + b for a, b in zip(A, B))

print(min(dp[H:]))
# print((dp[H:H+max(A)]))

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
l=list()
for i in range(n):
    a,b=map(int,input().split())
    l.append([min(a,h),b])
p=0
while h>0:
    l.sort(key=lambda x:(x[0]/x[1],-x[0]),reverse=True)
    p+=h//l[0][0]*l[0][1]
    h%=l[0][0]
    l=[[min(h,i),j] for i,j in l]
print(p)

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
l=list()
for i in range(n):
    a,b=map(int,input().split())
    l.append([min(a,h),b])
p=0
while h>0:
    l.sort(key=lambda x:(x[0]/x[1],-x[0]),reverse=True)
    print(l)
    p+=h//l[0][0]*l[0][1]
    h%=l[0][0]
    l=[[min(h,i),j] for i,j in l]
print(p)

Submission status: Wrong Answer

Solution code:
import math
tairyoku, n = map(int , input().split(" "))
a=[list(map(int, input().split(" "))) for i in range(n)]
kouritsu = []
for i in range(n):
  kouritsu.append(a[i][0] / a[i][1])
temp = (tairyoku // a[kouritsu.index(max(kouritsu))][0])
tairyoku -= a[kouritsu.index(max(kouritsu))][0] * temp
ans = a[kouritsu.index(max(kouritsu))][1] * temp
#print(temp)
for i in range(n):
  if a[i][0] < tairyoku:
    bai = math.ceil(tairyoku / a[i][0])
    a[i][0] *= bai
    a[i][1] *= bai
    
kouho = [list(x) for x in zip(*a)]
ans += a[a.index(min(a))][1]
print(ans)

Submission status: Wrong Answer

Solution code:
h,n = map(int,input().split())
ab = [0]*n
for i in range(n):
    ab[i] = list(map(int,input().split()))
from collections import deque
q = deque([])
hp = [0]*(h+1+10**4)
for aa,bb in ab:
    q.append(aa)
    hp[aa] = bb
while q:
    x = q.popleft()
    for aa,bb in ab:
        if x + aa < h and (hp[x + aa] == 0 or hp[x] + bb < hp[x + aa]):
            q.append(x+aa)
            hp[x+aa] = hp[x] + bb
        elif x + aa >= h:
            if hp[h] == 0:
                hp[h] = hp[x] + bb
            else:
                hp[h] =  min(hp[x] + bb, hp[h])
print(hp[h])

Submission status: Wrong Answer

Solution code:
import sys
from fractions import Fraction
input = sys.stdin.readline

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

a = []

for j in range(n):
    a.append(list(map(int, input().split())))

c = []

for x in a:
    c.append([Fraction(x[0], x[1]), x[0], x[1]])

c.sort(reverse=True)

def hit(c, h):

    m = [Fraction(), 0, 0]
    for i in c:
        if h >= i[1]:
            if m[0] < i[0]:
                m = i
    
    if m[0] == Fraction():
        l = 100000
        for i in c:
            if l > i[2]:
                l = i[2]
        return l

    s = (h // m[1] ) * m[2]

    h = h %  m[1]

    if h == 0:
        return s
    else:
        return s + hit(c, h)

print(hit(c, h))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


def zz():
    return list(map(int, input().split()))


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


H, N = zz()
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = zz()
dp = [0]*(H+max(A)+1)  # dp[i]: HPをi減らすのに必要な最低の魔力
# dp = np.zeros(H+max(A)+1, np.int32)
arg_min = np.argmin(A)
dp[:min(A)+1] = [B[arg_min]]*(min(A)+1)

for i in range(min(A)+1, H + max(A)+1):
    dp[i] = min(dp[i - a] + b for a, b in zip(A, B))

print(min(dp[H:H+max(A)+1]))
# print((dp[H:H+max(A)]))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


def zz():
    return list(map(int, input().split()))


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


H, N = zz()
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = zz()
dp = [0]*(H+max(A)+1)  # dp[i]: HPをi減らすのに必要な最低の魔力
# dp = np.zeros(H+max(A)+1, np.int32)
arg_min = np.argmin(A)
dp[:min(A)+1] = [B[arg_min]]*(min(A)+1)

for i in range(min(A)+1, H + max(A)):
    dp[i] = min(dp[i - a] + b for a, b in zip(A, B))

print(min(dp[H:H+max(A)]))
# print((dp[H:H+max(A)]))

Submission status: Wrong Answer

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)]
from sys import stdin
input = stdin.readline
 
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]
        dp[i][j] = min(dp[i][j],dp[i-1][j])
        if 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])
            break

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

#print(dp[-1])

Submission status: Wrong Answer

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 = max(10**4,sum(A))
    dp = [INF] * tp
    dp[0] = 0
    minim = INF
    for h in range(tp):
        for i in range(N):
            dp_i = min(h-A[i],H)
            dp[h] = min(dp[h],dp[dp_i]+B[i])
            if h >= H:
                minim = min(minim,dp[h])


    print(minim)
    # assert False


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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 + sorted(A)[::-1][0]
    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: Wrong Answer

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 + sorted(B)[::-1][0]
    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: Wrong Answer

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 = 3 * 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: Wrong Answer

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

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、


dp[0][0] = 0


for i in range(1,n+1):
    for j in range(h+1):
        a = ab[i-1][0]
        b = ab[i-1][1]
        if 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: Wrong Answer

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(n):
    dp[i][0] = 0


for i in range(1,n+1):
    for j in range(h+1):
        a = ab[i-1][0]
        b = ab[i-1][1]
        if 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: Wrong Answer

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(n):
    dp[i][0] = 0


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

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

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
ab = []
for _ in range(n):
    ab.append(list(map(int, input().split())))
inf = 1001001001
lis = [inf] * (2*h+5)
lis[0] = 0
for i in range(len(lis)):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        if i+a < len(lis):
            lis[i+a] = min(lis[i]+b, lis[i+a])
print(min(lis[h:]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
h,n=map(int,input().split())
INF=float('inf')
ab=defaultdict(lambda: -INF)
for _ in range(n):
  a,b=map(int,input().split())
  ab[b]=max(ab[b],a)
dp=[INF]*(h+max(ab.values()))
for i in range(ab[min(ab.keys())]):
  dp[i]=min(ab.keys())
for i in range(1,h+max(ab.values())):
  for m,d in ab.items():
    if i>=d:
      dp[i]=min(dp[i],dp[i-d]+m)
print(min(dp[h-1:]))