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:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

h,n=LI()
a=[]
b=[]
for i in range(n):
    x,y=LI()
    a+=[x]
    b+=[y]

dp=[[0]+[inf]*(h) for i in range(n+1)]    
dp[0][0]=0

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

ans=dp[n][h]

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

h,n=LI()
a=[]
b=[]
for i in range(n):
    x,y=LI()
    a+=[x]
    b+=[y]

dp=[[0]+[inf]*(h) for i in range(n+1)]    
dp[0][0]=0

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

ans=dp[n][h]

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

h,n=LI()
a=[]
b=[]
for i in range(n):
    x,y=LI()
    a+=[x]
    b+=[y]

dp=[[0]+[inf]*(h) for i in range(n+1)]    
dp[0][0]=0

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

ans=dp[n][h]

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

h,n=LI()
a=[]
b=[]
for i in range(n):
    x,y=LI()
    a+=[x]
    b+=[y]

dp=[[0]+[inf]*(h) for i in range(n+1)]    
dp[0][0]=0

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

ans=dp[n][h]

print(ans)

show(dp)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

h,n=LI()
a=[]
b=[]
for i in range(n):
    x,y=LI()
    a+=[x]
    b+=[y]

dp=[[inf]*(1+h) for i in range(n+1)]    
dp[0][0]=0

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

ans=dp[n][h]

print(ans)

show(dp)

Submission status: Wrong Answer

Solution code:
h,n = map(int,input().split())
dp = [int(1e18)] * (h+1)
dp[0] = 0
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h):
        nj = min(j+a, h)
        dp[nj] = min(dp[nj], dp[j]+b)
    print(dp)
print(dp[h])

Submission status: Wrong Answer

Solution code:
h,n = map(int,input().split())
dp = [1e8] * (h+1)
dp[0] = 0
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h):
        nj = min(j+a, h)
        dp[nj] = min(dp[nj], dp[j]+b)
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 = [10000000] * 100000
dp[0] = 0
for i in range(N):
    for j in range(10001):
        dp[j + A[i]] = min(dp[j + A[i]], dp[j] + B[i])
m = int(1e10)
for i in range(H, H + 10001):
    m = min(m, dp[i])

print(m)

Submission status: Wrong Answer

Solution code:
from sys import stdin
f_i = stdin

H, N = map(int, f_i.readline().split())

import numpy as np
dp = np.full(H + 10 ** 4, 10 ** 8)
dp[0] = 0

for i in range(N):
    A, B = map(int, f_i.readline().split())
    for j, t in enumerate(zip(dp, dp[A:H+A]), start=A):
        dp_i, dp_j = t
        if dp_i + B < dp_j:
            dp[j] = dp_i + B

print(min(dp[H:]))

Submission status: Wrong Answer

Solution code:
from sys import stdin
f_i = stdin

H, N = map(int, f_i.readline().split())

import numpy as np
dp = np.full((N + 1, H + 10 ** 4), 10 ** 8)
dp[0][0] = 0

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

print(np.min(dp[-1][H:]))

Submission status: Wrong Answer

Solution code:
import numpy as np
H,N = map(int,input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i],B[i] = map(int,input().split())
a = np.array(A)
b = np.array(B)
c = a/b
n = np.argmax(c)
if H < int(a[n]):
    print(int(b[n]))
else:
    s = 0
    while H >= int(a[n]):
        H = H - int(a[n])
        s = s + int(b[n])
    if H == 0:
        print(s)
    else:
        t = 100000
        for j in range(0,N):
            if H <= int(a[j]):
                if t > int(b[j]):
                    t = int(b[j])
        print(s+t)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,N = map(int,input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i],B[i] = map(int,input().split())
a = np.array(A)
b = np.array(B)
c = b/a
m = min(c)
n = np.where(min(c))
if H < int(a[n]):
    print(int(b[n]))
else:
    s = 0
    while H >= int(a[n]):
        H = H - int(a[n])
        s = s + int(b[n])
    if H == 0:
        print(s)
    else:
        t = 100000
        for j in range(0,N):
            if H <= int(a[j]):
                if t > int(b[j]):
                    t = int(b[j])
        print(s+t)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,N = map(int,input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i],B[i] = map(int,input().split())
a = np.array(A)
b = np.array(B)
c = b/a
m = min(c)
n = np.where(min(c))
s = 0
while H >= int(a[n]):
    H = H - int(a[n])
    s = s + int(b[n])
if H == 0:
    print(s)
else:
    t = 100000
    for j in range(0,N):
        if H <= int(a[j]):
            if t > int(b[j]):
                t = int(b[j])
    print(s+t)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,N = map(int,input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i],B[i] = map(int,input().split())
a = np.array(A)
b = np.array(B)
c = a/b
m = max(c)
n = np.where(max(c))
s = 0
while H >= a[n]:
    H = H - a[n]
    s = s + int(b[n])
if H == 0:
    print(s)
else:
    t = 100000
    for j in range(0,N):
        if H <= a[j]:
            if t > b[j]:
                t = int(b[j])
    print(s+t)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

sorted_a_list = []
attack_list = [{'damage' : 0, 'cost' : 0, 'damage_p_cost' : 0}]
min_cost = 0
rest_hp = 0

h , n = map(int, input().split())
for i in range(n):
    a , b = map(int, input().split())
    attack_list.append({'damage' : a, 'cost' : b, 'damage_p_cost' : a/b})
    if(min_cost > b or min_cost == 0):
        min_cost = b
attack_list.pop(0)

sorted_a_list = sorted(attack_list, key=lambda x:x['damage_p_cost'], reverse=True)

# # print(sorted_a_list)
# print('min_cost : ' + str(min_cost))

def batle(hp):
    sum_cost = 0
    for i in sorted_a_list:
        # print('calc start : ' + str(i['damage']))
        if(hp >= i['damage']):
            sum_cost =  sum_cost + i['cost'] * int(hp / i['damage'])
            # print(str(int(hp/i['damage'])))
            hp = hp % i['damage']
            if(hp == 0):
                # print('no rest : ' + str(sum_cost))
                return sum_cost
    # print('sum_cost : ' + str(sum_cost))
    sum_cost = sum_cost + min_cost
    return sum_cost

if __name__ == '__main__':
    ans = batle(h)
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

sorted_a_list = []
attack_list = [{'damage' : 0, 'cost' : 0, 'damage_p_cost' : 0}]
min_cost = 0
rest_hp = 0

h , n = map(int, input().split())
for i in range(n):
    a , b = map(int, input().split())
    attack_list.append({'damage' : a, 'cost' : b, 'damage_p_cost' : a/b})
    if(min_cost > b or min_cost == 0):
        min_cost = b
attack_list.pop(0)

sorted_a_list = sorted(attack_list, key=lambda x:x['damage_p_cost'], reverse=True)

# print(sorted_a_list)
print('min_cost : ' + str(min_cost))

def batle(hp):
    sum_cost = 0
    for i in sorted_a_list:
        print('calc start : ' + str(i['damage']))
        if(hp >= i['damage']):
            sum_cost =  sum_cost + i['cost'] * int(hp / i['damage'])
            print(str(int(hp/i['damage'])))
            hp = hp % i['damage']
            if(hp == 0):
                print('no rest : ' + str(sum_cost))
                return sum_cost
    print('sum_cost : ' + str(sum_cost))
    sum_cost = sum_cost + min_cost
    return sum_cost

if __name__ == '__main__':
    ans = batle(h)
    print(ans)

Submission status: Wrong Answer

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

INF = float('INF')
MAX_J = (10 ** 4 + 1) * 2

# DP[i][j]: i番目までの魔法を使って、ダメージの総和をjにする魔力の最小値
DP = []
for i in range(N+1):
    DP.append([INF] * MAX_J)

DP[0][0] = 0
for i in range(N):
    for j in range(MAX_J):
        if j < A[i][0]:
            DP[i+1][j] = DP[i][j]
        else:
            DP[i+1][j] = min(DP[i][j], DP[i+1][j-A[i][0]] + A[i][1])

# for i in range(N+1):
#     print(DP[i][:20])

ans = INF
for i, v in enumerate(DP[N]):
    if i >= H and v != INF:
        ans = v
        break
else:
    raise Exception()
        
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
h,n=map(int,input().split())
a=np.empty((3,n))
for i in range(n):
  aa,bb=map(int,input().split())
  a[0,i]=aa
  a[1,i]=bb
  a[2,i]=aa/bb
a=a[:,np.argsort(a[2,:])[::-1]]
c=0
s=1
hh=h
while s:
  if len(a[:,h<a[0]][0])!=0:
    aa=a[:,h<a[0]][:,np.argsort(a[:,h<a[0]][1,:])][0,0]
    c+=aa
    s=0
    break
  for i in range(n):
    if a[0,i]<h or a[1,i]==a[1].min():
        h-=a[0,i]
        c+=a[1,i]
        break
c1=c
c=0
h=hh
while h>0:
  for i in range(n):
    if a[0,i]<h or a[0,i]==a[0].min():
    	h-=a[0,i]
    	c+=a[1,i]
    	break
print(int(min(c1,c)))

Submission status: Wrong Answer

Solution code:
import numpy as np
h,n=map(int,input().split())
a=np.empty((3,n))
for i in range(n):
  aa,bb=map(int,input().split())
  a[0,i]=aa
  a[1,i]=bb
  a[2,i]=aa/bb
a=a[:,np.argsort(a[2,:])[::-1]]
c=0
s=1
hh=h
while s:
  if len(a[:,h<a[0]][0])!=0:
    aa=a[:,h<a[0]][:,np.argsort(a[:,h<a[0]][1,:])][0,0]
    c+=aa
    s=0
    break
  for i in range(n):
    if a[0,i]<h or a[1,i]==a[1].min():
        h-=a[0,i]
        c+=a[1,i]
        print(int(a[1,i]))
        break
c1=c
c=0
h=hh
while h>0:
  for i in range(n):
    if a[0,i]<h or a[0,i]==a[0].min():
    	h-=a[0,i]
    	c+=a[1,i]
    	break
print(int(min(c1,c)))

Submission status: Wrong Answer

Solution code:
import numpy as np
h,n=map(int,input().split())
a=np.empty((3,n))
for i in range(n):
  aa,bb=map(int,input().split())
  a[0,i]=aa
  a[1,i]=bb
  a[2,i]=aa/bb
a=a[:,np.argsort(a[2,:])[::-1]]
c=0
s=1
while s:
  if len(a[:,h<a[0]][0])!=0:
    aa=a[:,h<a[0]][:,np.argsort(a[:,h<a[0]][1,:])][0,0]
    c+=aa
    s=0
    break
  for i in range(n):
    if a[0,i]<h or a[1,i]==a[1].min():
        h-=a[0,i]
        c+=a[1,i]
        print(int(a[1,i]))
        break
c1=c
c=0
while h>0:
  for i in range(n):
    if a[0,i]<h or a[0,i]==a[0].min():
    	h-=a[0,i]
    	c+=a[1,i]
    	break
print(int(min(c1,c)))

Submission status: Wrong Answer

Solution code:
import numpy as np
h,n=map(int,input().split())
a=np.empty((3,n))
for i in range(n):
  aa,bb=map(int,input().split())
  a[0,i]=aa
  a[1,i]=bb
  a[2,i]=aa/bb
a=a[:,np.argsort(a[2,:])[::-1]]
c=0
s=1
while s:
  for i in range(n):
    if a[0,i]<h or a[1,i]==a[1].min():
        h-=a[0,i]
        c+=a[1,i]
        break
  if len(a[:,h<=a[0]][0])!=0:
    aa=a[:,h<=a[0]][:,np.argsort(a[:,h<=a[0]][1,:])][1,0]
    c+=aa
    s=0

print(int(c))

Submission status: Wrong Answer

Solution code:
import numpy as np
h,n=map(int,input().split())
a=np.empty((3,n))
for i in range(n):
  aa,bb=map(int,input().split())
  a[0,i]=aa
  a[1,i]=bb
  a[2,i]=aa/bb
a=a[:,np.argsort(a[2,:])[::-1]]
c=0
s=1
while s:
  if len(a[:,h<=a[0]][0])!=0:
    aa=a[:,h<=a[0]][:,np.argsort(a[:,h<=a[0]][1,:])][1,0]
    c+=aa
    s=0
    break
  for i in range(n):
    if a[0,i]<h or a[1,i]==a[1].min():
        h-=a[0,i]
        c+=a[1,i]
        break
print(int(c))

Submission status: Wrong Answer

Solution code:
import numpy as np
h,n=map(int,input().split())
a=np.empty((3,n))
for i in range(n):
  aa,bb=map(int,input().split())
  a[0,i]=aa
  a[1,i]=bb
  a[2,i]=aa/bb
a=a[:,np.argsort(a[2,:])[::-1]]
c=0
s=1
while s:
  if len(a[:,h<=a[0]][0])!=0:
    aa=a[:,h<=a[0]][:,np.argsort(a[:,h<=a[0]][1,:])][0,0]
    c+=aa
    s=0
    break
  for i in range(n):
    if a[0,i]<h or a[1,i]==a[1].min():
        h-=a[0,i]
        c+=a[1,i]
        break
print(int(c))

Submission status: Wrong Answer

Solution code:
import numpy as np
h,n=map(int,input().split())
a=np.empty((3,n))
for i in range(n):
  aa,bb=map(int,input().split())
  a[0,i]=aa
  a[1,i]=bb
  a[2,i]=aa/bb
a=a[:,np.argsort(a[2,:])[::-1]]
c=0
s=1
while s:
  if len(a[:,h<=a[0]][0])!=0:
    aa=a[:,h<=a[0]][:,np.argsort(a[:,h<=a[0]][1,:])][0,0]
    c+=aa
    s=0
    break
  for i in range(n):
    if a[0,i]<h or a[1,i]==a[1].min():
        h-=a[0,i]
        c+=a[1,i]
        print(int(a[1,i]))
        break
print(int(c))

Submission status: Wrong Answer

Solution code:
import numpy as np
h,n=map(int,input().split())
a=np.empty((3,n))
for i in range(n):
  aa,bb=map(int,input().split())
  a[0,i]=aa
  a[1,i]=bb
  a[2,i]=aa/bb
a=a[:,np.argsort(a[2,:])[::-1]]
c=0
s=1
while s:
  if len(a[:,h<a[0]][0])!=0:
    aa=a[:,h<a[0]][:,np.argsort(a[:,h<a[0]][1,:])][0,0]
    c+=aa
    s=0
    break
  for i in range(n):
    if a[0,i]<h or a[1,i]==a[1].min():
        h-=a[0,i]
        c+=a[1,i]
        print(int(a[1,i]))
        break
print(int(c))

Submission status: Wrong Answer

Solution code:
import numpy as np
h,n=map(int,input().split())
a=np.empty((3,n))
for i in range(n):
  aa,bb=map(int,input().split())
  a[0,i]=aa
  a[1,i]=bb
  a[2,i]=aa/bb
a=a[:,np.argsort(a[2,:])[::-1]]
c=0
while h>0:
  for i in range(n):
    if a[0,i]<h or a[0,i]==a[0].min():
    	h-=a[0,i]
    	c+=a[1,i]
    	break
print(int(c))

Submission status: Wrong Answer

Solution code:
import numpy as np
h,n=map(int,input().split())
a=np.empty((3,n))
for i in range(n):
  aa,bb=map(int,input().split())
  a[0,i]=aa
  a[1,i]=bb
  a[2,i]=aa/bb
a=a[:,np.argsort(a[0,:])[::-1]]
c=0
while h>0:
  for i in range(n):
    if a[0,i]<h or a[0,i]==a[0].min():
    	h-=a[1,i]
    	c+=a[0,i]
    	break
print(int(c))

Submission status: Wrong Answer

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

INF = float('INF')
MAX_J = 10 ** 4 + 10 ** 4 + 1

# DP[i][j]: i番目までの魔法を使って、ダメージの総和をjにする魔力の最小値
DP = []
for i in range(N+1):
    DP.append([INF] * MAX_J)

DP[0][0] = 0
for i in range(N):
    for j in range(MAX_J):
        if j < A[i][0]:
            DP[i+1][j] = DP[i][j]
        else:
            DP[i+1][j] = min(DP[i][j], DP[i+1][j-A[i][0]] + A[i][1])

# for i in range(N+1):
#     print(DP[i][:20])

ans = DP[N][H]
for i, v in enumerate(DP[N]):
    if i >= H and v != INF:
        ans = v
        break
else:
    raise Exception()
        
print(ans)

Submission status: Wrong Answer

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

INF = float('INF')
MAX_J = 10 ** 4 + 10 ** 4 + 1

# DP[i][j]: i番目までの魔法を使って、ダメージの総和をjにする魔力の最小値
DP = []
for i in range(N+1):
    DP.append([INF] * MAX_J)

DP[0][0] = 0
for i in range(N):
    for j in range(MAX_J):
        if j < A[i][0]:
            DP[i+1][j] = DP[i][j]
        else:
            DP[i+1][j] = min(DP[i][j], DP[i+1][j-A[i][0]] + A[i][1])

for i in range(N+1):
    print(DP[i][:20])

ans = DP[N][H]
for i, v in enumerate(DP[N]):
    if i >= H and v != INF:
        ans = v
        break
else:
    raise Exception()
        
print(ans)

Submission status: Wrong Answer

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

INF = float('INF')
MAX_J = 10 ** 4 + 10 ** 4 + 1

# DP[i]: i番目までの魔法を使って、ダメージの総和をjにする魔力の最小値
DP = []
for i in range(N+1):
    DP.append([INF] * MAX_J)

DP[0][0] = 0
for i in range(N):
    for j in range(MAX_J):
        if j < A[i][0]:
            DP[i+1][j] = DP[i][j]
        else:
            DP[i+1][j] = min(DP[i][j], DP[i+1][j-A[i][0]] + A[i][1])

# for i in range(N+1):
    # print(DP[i][:20])

ans = DP[N][H]
for i, v in enumerate(DP[N]):
    if i >= H and v != INF:
        ans = v
        break
        
print(ans)

Submission status: Wrong Answer

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

INF = float('INF')

# DP[i]: i番目までの魔法を使って、ダメージの総和をjにする魔力の最小値
DP = []
for i in range(N+1):
    DP.append([INF] * (10 ** 4 + 1))

DP[0][0] = 0
for i in range(N):
    for j in range(10 ** 4 + 1):
        if j < A[i][0]:
            DP[i+1][j] = DP[i][j]
        else:
            DP[i+1][j] = min(DP[i][j], DP[i+1][j-A[i][0]] + A[i][1])

# for i in range(N+1):
    # print(DP[i][:20])

ans = DP[N][H]
for i, v in enumerate(DP[N]):
    if i >= H and v != INF:
        ans = v
        break
        
print(ans)

Submission status: Wrong Answer

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

inf = 10 ** 10
minmp = [inf for _ in range(h+1)]
minmp[0] = 0
for i in range(n):
  for j in range(h+1):
    if j - a[i] >= 0:
      minmp[j] = min(minmp[j], minmp[j-a[i]]+b[i])
print(minmp[-1])

Submission status: Wrong Answer

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

maho = []
for _ in range(N) :
  A, B = map(int, input().split())
  maho.append([A/B, A, B])
  
maho = sorted(maho, reverse=True)

ans = 0
while H > 0:
  # 1発KOあるかをチェックする
  flag = 0
  for item in maho :
    if item[1] >= H :
      flag = 1
      break
  
  # 1発KOなしの場合
  if flag == 0 :
    cou = int(H/maho[0][1])
    ans += cou*maho[0][2]
    H -= cou*maho[0][1]
  else :
    for item in maho :
      wari = H/item[1]
      if (int(wari) != wari) :
        wari = math.ceil(wari)
      item.insert(0, wari*item[2] )
    
    maho = sorted(maho)
    ans += maho[0][0]
    H = -1

print(ans)