TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: Caracal is fighting with a monster.  The _health_ of the monster is H.  Caracal can attack by choosing one monster. When a monster is attacked, depending on that monster's health, the following happens:    * If the monster's health is 1, it drops to 0.   * If the monster's health, X, is greater than 1, that monster disappears. Then, two new monsters appear, each with the health of \lfloor X/2 \rfloor.  (\lfloor r \rfloor denotes the greatest integer not exceeding r.)  Caracal wins when the healths of all existing monsters become 0 or below.  Find the minimum number of attacks Caracal needs to make before winning.

Submission attempts (in order):
n = int(input())


ans = 0
k = 1
while True:
  n //=2
  ans += k
  k *= 2
  if n =< 1:
    break

print(ans+k)

n = int(input())


ans = 0
k = 1
while True:
  n //=2
  ans += k
  k *= 2
  if n <= 1:
    print(ans)
    exit()

print(ans+k)

n = int(input())


ans = 0
k = 1
while True:
  n //=2
  ans += k
  k *= 2
  if n == 1:
    print(ans+k)
    break
  elif n < 1:
    print(ans)
    break 

Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: Caracal is fighting with a monster.  The _health_ of the monster is H.  Caracal can attack by choosing one monster. When a monster is attacked, depending on that monster's health, the following happens:    * If the monster's health is 1, it drops to 0.   * If the monster's health, X, is greater than 1, that monster disappears. Then, two new monsters appear, each with the health of \lfloor X/2 \rfloor.  (\lfloor r \rfloor denotes the greatest integer not exceeding r.)  Caracal wins when the healths of all existing monsters become 0 or below.  Find the minimum number of attacks Caracal needs to make before winning.

Submission attempts (in order):
from sys import stdin
import math
n = int(stdin.readline().rstrip())
i = 0
while True:
    if 2**i >= n:
        break
    i += 1
point = 0
for j in range(i):
    point += 2**j
print(point)

from sys import stdin
import math
n = int(stdin.readline().rstrip())
i = 0
while True:
    if 2**i > n:
        break
    i += 1
point = 0
for j in range(i):
    point += 2**j
print(point)

Verdicts: Wrong Answer

Accepted
Problem: Caracal is fighting with a monster.  The _health_ of the monster is H.  Caracal can attack by choosing one monster. When a monster is attacked, depending on that monster's health, the following happens:    * If the monster's health is 1, it drops to 0.   * If the monster's health, X, is greater than 1, that monster disappears. Then, two new monsters appear, each with the health of \lfloor X/2 \rfloor.  (\lfloor r \rfloor denotes the greatest integer not exceeding r.)  Caracal wins when the healths of all existing monsters become 0 or below.  Find the minimum number of attacks Caracal needs to make before winning.

Submission attempts (in order):
h = input()
h = int(h)
count = 0
attack = 0

if h > 1:
  while h > 1:
    h = h / 2 
    count = count + 1
  for i in range(0, count):
    attack = attack + (2**i)
  print(attack)
else:
  print(1)


h = input()
h = int(h)
count = 0
attack = 0

if h > 1:
  while h >= 1:
    h = h / 2 
    count = count + 1
  for i in range(0, count):
    attack = attack + (2**i)
  print(attack)
else:
  print(1)


Verdicts: Wrong Answer

Accepted
Problem: Caracal is fighting with a monster.  The _health_ of the monster is H.  Caracal can attack by choosing one monster. When a monster is attacked, depending on that monster's health, the following happens:    * If the monster's health is 1, it drops to 0.   * If the monster's health, X, is greater than 1, that monster disappears. Then, two new monsters appear, each with the health of \lfloor X/2 \rfloor.  (\lfloor r \rfloor denotes the greatest integer not exceeding r.)  Caracal wins when the healths of all existing monsters become 0 or below.  Find the minimum number of attacks Caracal needs to make before winning.

Submission attempts (in order):



using namespace std;
const int MOD = 1E9 + 9;
const int INF = 1<<29; 

long long f(long long x){
    if(x == 1) return 1;
    return f(x/2) * 2 + 1;
}

int main(){
    long long H;
    cin >> H;
    cout << f(H) << endl;
    return 0;
}

import numpy as np
import math
H = int(input())

cnt = np.log2(H)
cnt = math.floor(cnt)
cnt = 2**(cnt + 1) - 1
print(cnt)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
h, n = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(n)]
max_a = max(a for a, _ in lst )
dp = [10**18 for _ in range(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 lst)
    print(dp[i])
print(min(dp[h:]))

h, n = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(n)]
max_a = max(a for a, _ in lst )
dp = [10**18 for _ in range(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 lst)
print(min(dp[h:]))

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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):
  if i > 0:
	dp[i] = min(dp[i - a] + b for a, b in ab)

print(min(dp[h:]))

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(1, h + a_max):
	dp[i] = min(dp[i - a] + b for a, b in ab)

print(min(dp[h:]))

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
x=input().split()
h=int(x[0])
n=int(x[1])
import numpy as np
a=np.full(n,0,int)
b=np.full(n,0,int)
for k in range(n):
  x=input().split()
  a[k]=int(x[0])
  b[k]=int(x[1])
m=max(a)  
inf=10**8
dp=np.full(h+m,inf,int)
dp[0]=0
for k in range(1,h+m):
  dp[k]=(dp[np.max(k-a,0)]+b).min()
print(dp[h:h+m].min())


x=input().split()
h=int(x[0])
n=int(x[1])
import numpy as np
a=np.full(n,0,int)
b=np.full(n,0,int)
for k in range(n):
  x=input().split()
  a[k]=int(x[0])
  b[k]=int(x[1])
m=max(a)  
inf=10**8
dp=np.full(h+m+1,inf,int)
dp[0]=0
for k in range(1,h+m):
  dp[k]=min((dp[np.max(k-a,-1)]+b).min(),10**8)
print(dp[h:h+m].min())

x=input().split()
h=int(x[0])
n=int(x[1])
import numpy as np
a=np.full(n,0,int)
b=np.full(n,0,int)
for k in range(n):
  x=input().split()
  a[k]=int(x[0])
  b[k]=int(x[1])
m=max(a)  
inf=10**8
dp=np.full(h+m+1,inf,int)
dp[0]=0
for k in range(1,h+m):
  dp[k]=(dp[k-a]+b).min()
print(dp[h:h+m].min())

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
#include <bits/stdc++.h>

#include <cstring>


#define REP(i,n) for(int i=0;i<n;i++)


//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


using namespace std;
using ll=long long;
ll mod = 1e9 + 7;

//int dp[1e5];
//memset(dp, BMAX*HMAX, sizeof(dp));
  
int main() {
    int H, N;
    cin >> H >> N;
    vector<int> A(N), B(N);
    for(int i=0;i<N;i++){
        cin >> A[i] >> B[i];
    }
    vector<ll> dp(H+1, 1e9);
    dp[0] = 0;
    for(int i=0;i<H;i++){
        for(int j=0;j<N;j++){
            chmin(dp[min(i+A[j], H)], dp[i]+B[j]);
        }
    }
    cout << dp[H] << endl;
	return 0;
}


import sys

input = sys.stdin.readline
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]

max_damage = max(damage for damage, cost in magic)
dp = [0] * (H + max_damage)

for x in range(1, H + max_damage):
    dp[x] = min(dp[x - damage] + cost for damage, cost in magic)

ans = min(dp[H:])

print(ans)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
def dp(H, N, a, b):
  max_a = max(a)
  d = [INF for _ in range(H + max_a)]
  d[0] = 0
  for h in range(1, H + max_a):
    min_mp = INF
    for i in range(N):
      if h - a[i] >= 0:
        min_mp = min(min_mp, d[h - a[i]] + b[i])
  return min([d[H + h] for h in range(max_a)])
INF = 10 ** 10
H, N = map(int, input().split())
a = [0 for _ in range(N)]
b = [0 for _ in range(N)]
for i in range(N):
  ai, bi = map(int, input().split())
  a[i] = ai
  b[i] = bi
print(dp(H, N, a, b))

def mincost(h, m, i):
  if i == len(m) - 1:
    return (1 + (h - 1) // m[i][0]) * m[i][1]
  return min((1 + (h - 1) // m[i][0]) * m[i][1],
            mincost(h % m[i][0], m, i+1))

h, n = list(map(int, input().rstrip().split()))
m = [tuple(map(int, input().rstrip().split())) for _ in range(n)]

m.sort(key = lambda x: x[0])
m.sort(key = lambda x: x[0] / x[1], reversed = True)

print(mincost(h, m, 0))

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])

def dp(H, N, ab):
  max_a = max([ab[i][0] for i in range(N)])
  d = [INF for _ in range(H + max_a)]
  d[0] = 0
  for h in range(1, H + max_a):
    d[h] = min(d[h - a] + b for a, b in ab)
  return min(d[H:])
INF = 10 ** 10
H, N = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(N)]
print(dp(H, N, ab))

Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
h,n=map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
maxAi= max(a for a,b in AB)
dp=[0]*(H+maxAi)
i=1
try:
    dp[i]=min(dp[i-a]+b for a,b in AB)
    i+=1
except:
    print(min(dp[H:]))

h,n=map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
maxAi= max(a for a,b in AB)
dp=[0]*(H+maxAi)
i=1
try:
    dp[i]=min(dp[i-a]+b for a,b in AB)
    i+=1
else:
    print(min(dp[H:]))

H,n=map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(n)]
maxAi= max(a for a,b in AB)
dp=[0]*(H+maxAi)
i=1
while True:
  try:
    dp[i]=min(dp[i-a]+b for a,b in AB)
    i+=1
  except:
    print(min(dp[H:]))
    break

Verdicts: Runtime Error

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
from operator import itemgetter, attrgetter

h,n = map(int,input().split())
ls = []

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

ls = sorted(ls,key = lambda x: min(x[0],h)/x[1], reverse = True)
ans = 0

t = ls[0]
ans += h//t
h %= t

while h>0:
  ls = sorted(ls,key = lambda x: min(x[0],h)/x[1], reverse = True)
  t = ls[0]
  ans += h//t
  h %= t
print(ans)






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


ls = sorted(ls,key = lambda x: min(x[0],h)/x[1], reverse = True)
ans = 0

t = ls[0]
ans += (h//t[0])*t[1]
h %= t[0]

while h>0:
  ls = sorted(ls,key = lambda x: min(x[0],h)/x[1], reverse = True)
  t = ls[0]
  ans += (h//t[0])*t[1]
  h %= t[0]
print(ans)



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

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

amax = max(a for a,b in ls)

dp = [0]*(h+amax)

for i in range(1,h+amax):
  p = max(1,2)
  dp[i] = min(dp[i-a]+b for a,b in ls)

print(min(dp[h:]))

Verdicts: Runtime Error

Time Limit Exceeded

Accepted
Problem: 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.

Submission attempts (in order):
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=[[0 for i in range(h+1)] for j in range(n+1)]
for i in range(n):
    for j in range(h):
        if a[i]<=j:
            if dp[i][j-a[i]]<h:
                dp[i+1][j]=dp[i][j-a[i]]+b[i]
            else:
                dp[i+1][j]=min(dp[i][j-a[i]]+b[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[n][h])
        
    

h,n=map(int,input().split())
li=[]
x=[]
for i in range(n):
    A,B=map(int,input().split())
    x.append(A)
    li.append([A,B])
dp=[10**9]*(h+max(x))
dp[0]=0
for i in range(1,len(dp)):
    dp[i] = min(dp[i-a]+b for a,b in li)
print(min(dp[h:]))

    

    




Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
H, N = map(int, input().split())

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

import numpy as np

d = [0] + [10**18] * H

for hp in range(1, H + 1):
    for ab in AB:
        # print(ab)
        hp_remain = np.max(hp - ab[0], 0)
        # if hp_remain < 0: hp_remain = 0
        # print(hp_remain)
        c = d[hp_remain] + ab[1]
        if c < d[hp]: d[hp] = c

print(d[H])




import numpy as np


H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
a, b = np.array(AB, dtype=np.int64).reshape(N, 2).T

d = np.zeros(H + 1, dtype=np.int64)

for hp in range(1, H + 1):
    c = d[np.maximum(hp - a, 0)] + b
    d[hp] = np.amin(c)

print(d[H])

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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(H+1, dtype = int)
dp[0] = 0
for i in range(1,H+1):
    dp[i] = np.amin([dp[np.amax(i-A,0)] + B])

print(int(dp[H]))

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.full(H+1, np.inf)

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

print(int(dp[H]))

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]


max_magic = 0
for a, _ in magic:
    max_magic = max(max_magic, a)

amount = H + 1
dp = [0] * (amount + max_magic)
dp[0] = 0

ret = float('inf')

for amt in range(1, amount + max_magic):
    t = [dp[amt - a] + b if amt - a >= 0 for a, b in magic]
    dp[amt] = min(t)

    if amt >= H:
        ret = min(dp[amt], ret)

print(ret)


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


max_magic = 0
for a, _ in magic:
    max_magic = max(max_magic, a)

amount = H + 1
dp = [0] * (amount + max_magic)
dp[0] = 0

ret = float('inf')

for amt in range(1, amount + max_magic):
    t = [dp[amt - a] + b for a, b in magic]
    dp[amt] = min(t)

    if amt >= H:
        ret = min(dp[amt], ret)

print(ret)


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
h, n = map(int, input().split())
l = []
for i in range(n):
  a, b = map(int, input().split())
  l.append([a, b])

dp = [10 ** 8 + 1 for i in range(h + 10**4 + 1)]
dp[0] = 0

for i in range(h+1):
  for j in range(n):
    if dp[i] == 10 ** 8 + 1:
      continue

    x = dp[i] + l[j][1]
    if dp[i + l[j][0]] > x:
      dp[i + l[j][0]] = x

print(dp[h])


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

  dp = [10 ** 8 + 1 for i in range(h + 10 ** 4 + 1)]
  dp[0] = 0

  for i in range(h):
    if dp[i] == 10 ** 8 + 1:
        continue
    for a, b in l:
      x = dp[i] + b
      if dp[i + a] > x:
        dp[i + a] = x

  print(min(dp[h:]))

main()




Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
H,N=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(N)]
dp=[0]*(H)
for i in range (1,H+1):
    dp[i]=min(dp[i-a]+b for a,b in ab)
print(dp[H])

H,N=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(N)]
dp=[0]*(H+10**5)
for i in range (1,H+1):
    dp[i]=min(dp[i-a]+b for a,b in ab)
print(dp[H])

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
def cal(k):
  for a,b in AB:
    tmp = k-a
    if tmp<0:
      tmp = 0
    new = dp[tmp]+b
    if new<dp[k]:
      dp[k]=new
def main():
  H,N = map(int,input().split())
  AB = [list(map(int,input().split())) for _ in range(N)]
  mi_a,mi_b = min(AB,key = lambda x:x[1])
  INF = float('inf')
  dp = [0]+[mi_b]*mi_a+[INF]*H
  for i in range(mi_a+1,H+1):
    cal(i)

  print(dp[H])
  

main()

def main():
  def cal(k):
    for a,b in AB:
      tmp = k-a
      if tmp<0:
        tmp = 0
      new = dp[tmp]+b
      if new<dp[k]:
        dp[k]=new
  H,N = map(int,input().split())
  AB = [list(map(int,input().split())) for _ in range(N)]
  mi_a,mi_b = min(AB,key = lambda x:x[1])
  INF = float('inf')
  dp = [0]+[mi_b]*mi_a+[INF]*H
  for i in range(mi_a+1,H+1):
    cal(i)

  print(dp[H])
main()

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
from numba import jit
from sys import stdin

@jit(nopython=True)
def num():
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j in magic:
                if i-j[0] < 0:
                    num = ans[i]+j[1]
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+j[1]
                    if ans[i-j[0]] > num:
                        ans[i-j[0]] = num
    return ans[0]
print(num())




from numba import jit

@jit
def num():
    from sys import stdin
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j in magic:
                if i-j[0] < 0:
                    num = ans[i]+j[1]
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+j[1]
                    if ans[i-j[0]] > num:
                        ans[i-j[0]] = num
    return ans[0]
print(num())




from numba import jit
from sys import stdin

@jit
def num():
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j in magic:
                if i-j[0] < 0:
                    num = ans[i]+j[1]
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+j[1]
                    if ans[i-j[0]] > num:
                        ans[i-j[0]] = num
    return ans[0]
print(num())




def num():
    from sys import stdin
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j, k in magic:
                if i-j < 0:
                    num = ans[i]+k
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+k
                    if ans[i-j] > num:
                        ans[i-j] = num
    return ans[0]
print(num())




Verdicts: Runtime Error

Runtime Error

Time Limit Exceeded

Accepted
Problem: 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.

Submission attempts (in order):
import time

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

INF = 10 ** 20


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

magic = []

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

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

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

ans = min(dp[h:])

print(ans)

import time

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

INF = 10 ** 20


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

magic = []

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

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

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

ans = min(dp[h:])

print(ans)

import time

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

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

    t = time.time()

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

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

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

    ans = min(dp[h:])

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

main()

import time

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

INF = 10 ** 20


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

magic = []

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

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

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

ans = min(dp[h:])

print(ans)

import time

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

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

    # t = time.time()

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

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

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

    ans = min(dp[h:])

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

main()

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import numpy as np
h,n=map(int,input().split)
p=[list(map(int,input().split())) for _ in range(n)]
m=max(p[:,0])
dp=[0]*(h+m+1)
for i in range(m+1,h+m+1):
  dp[i]=min(dp[i-a]+b for a,b in p)
print(dp[h+m])

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


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [1000000] * (10 ** 5)
dp[0] = 0
for i in range(H):
    if dp[i] == 1000000:
        continue
    for j in range(N):
        a, b = AB[k]
        if dp[i] + b < dp[i + a]:
            dp[i + a] = dp[i] + b
print(min(dp[H:]))


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

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


main()


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
(h,n),*t=[map(int,o.split())for o in open(0)]
dp=[0]*(h+10100)
for i in range(1,h+1):dp[i]=min(dp[i-a]+b for a,b in t)
print(dp[h])

(h,n),*t=[list(map(int,o.split()))for o in open(0)]
d=[0]*(h+9999)
for i in range(1,h+1):d[i]=min(d[i-a]+b for a,b in t)
print(d[h])

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*111111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(10111):
    dp[index]=min(dp[index],dp[i]+b)
for i in range(h,111111):
  ans=min(ans,dp[i])
print(ans)

h,n=map(int,input().split())
dp=[10**9]*(h+10010)
A=[list(map(int,input().split())) for i in range(n)]
dp[0]=0
for i in range(h+10010):
  dp[i]=min(dp[i-a]+b for a,b in A)
print(min(dp[h:]))

h,n=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]
ma=max(a for a,b in A)
dp=[0]*(h+ma)
for i in range(1,h+ma):
  dp[i]=min(dp[i-a]+b for a,b in A)
print(min(dp[h:]))

Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import numpy as np
H, N = map(int, input().split())

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

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


H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
H,N = map(int,input().split())

AB = []

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

dp = [1e9]*(H+3)

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

import numpy as np 

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

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

dp = np.zeros(H+1,dtype=np.int32)

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

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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)


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))

from collections import deque

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[0]/x[1], reverse=True)

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




#  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
ansk = float('inf')

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

def indexH2(h,arr):
  d = deque()
  for i in range(len(arr)):
    if arr[i][0]>=h:
      d.appendleft(i)
  return d



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

print(ansk)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import sys
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())
min_hp = h
max_hp = h + max(A)

dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0

for i in range(0, max_hp + 1):
    for j in range(n): # type of spell
        if A[j] > i:
            continue
        dp[i] = min(dp[i], dp[i - A[j]] + B[j])



#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#

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


import sys
h, n = map(int, input().split())
# A = [0] * n
# B = [0] * n

#     A[i], B[i] = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
min_hp = h
max_hp = h + max(a for a, b in (AB))

dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0

for i in range(1, max_hp + 1):
    # dp[i] = min(dp[i - A[j]] + B[j] for j in range(n))
    dp[i] = min(dp[i - a] + b for a, b in AB)
print(min(dp[h:]))


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
h,n = map(int,input().split())

ab_input = [[int(j) for j in input().split()] for i in range(n)]

dp =[10**10]*(h+1)
dp[0]=0
for i in range(1,h):
    for a,b in ab_input:
        next_index=min(h,i+a)
        dp[next_index]=min(dp[next_index],dp[i]+b)
print(dp[-1])


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

ab_input = [list(map(int,input().split())) for i in range(n)]
max_d = max(a for a,b in ab_input)

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

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]


dp = [100000000] * (H + 10 ** 4 + 1)


for i in range(H):
    if dp[i] == 100000000:
        continue
    for a, b in AB:
        
        t = dp[i] + b
        
        if t < dp[i + a]:
            dp[i + a] = t

print(min(dp[H:]))




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

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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])


# 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)

# process
max_a = max(A)
dp = [10**9]*(H+max_a)
dp[0] = 0

for i in range(len(dp)):
    if dp[i] == 10**4:
        continue
    for j in range(N):
        idx = i+A[j]
        if idx < len(dp) and dp[i]+B[j] < dp[idx]:
            dp[i+A[j]] = dp[i]+B[j]

print(dp)

# output
print(min(dp[H:]))


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, dtype=np.int64).reshape(N, 2).T

# process
dp = np.zeros(H+1, dtype=np.int64)
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])


Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
# import itertools
# import math
import numpy as np


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

AB.sort()

ans = 0
dp = np.zeros(H, dtype=int)
for a, b in AB:
    ans = max(ans, dp.max() + b)
    np.max(dp[:-a] + b, dp[a:], out=dp[a:])

print(ans)


import sys
import numpy as np

h, n = map(int, input().split())
ab = np.array(sys.stdin.read().split(), dtype=np.int64)
aaa = ab[0::2]
bbb = ab[1::2]

dp = np.zeros(10001, dtype=np.int64)
for i in range(1, h + 1):
    dp[i] = (dp[i - aaa] + bbb).min()
print(dp[h])


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
# -*- coding: utf-8 -*-
import numpy
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)

h,n=map(int, input().split())  
AB = [tuple(map(int, input().split())) for _ in range(n)]

AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))

@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        best = float('inf')
        print(h)
        for a, b in AB:
            mp = b + dp(h -a)
            if mp < best:
                best = mp
            else:
                break
        return best

print(dp(h))

# -*- coding: utf-8 -*-
import numpy
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)

h,n=map(int, input().split())  
AB = [tuple(map(int, input().split())) for _ in range(n)]

AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))

@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        best = float('inf')
        for a, b in AB:
            mp = b + dp(h -a)
            if mp < best:
                best = mp
            else:
                break
        return best

print(dp(h))

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
H, N = map(int, input().split())
ATK, MP = zip(*(tuple(map(int, input().split())) for _ in range(N)))
table = [float("inf")] * (H + 1 + max(ATK))
table[0] = 0
for damage in range(1, H + 1):
    table[damage] = min(table[damage - ATK[magic]] + MP[magic] for magic in range(N))
print(table[H])


import numpy as np
H, N = map(int, input().split())
ATK, MP = np.array(tuple(tuple(map(int, input().split())) for _ in range(N)), dtype=np.int32).T
table = np.zeros((H + ATK.max(),), dtype=np.int32)
for damage in range(1, H + 1):
    table[damage] = (table[damage - ATK] + MP).min()
print(table[H])


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import numpy as np

def main():
    H,N = map(int, input().split())
    A = [None]*N
    B = [None]*N
    for i in range(N):
        A[i], B[i] = map(int, input().split())
    
    dp = [float("inf")] * (H+1)
    dp[-1] = 0

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

    print(dp[0])


if __name__ == "__main__":
    main()


import sys
import numpy as np
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H, N, *ab = map(int, read().split())
    A = []
    B = []
    for a, b in zip(*[iter(ab)] * 2):
        A.append(a)
        B.append(b)

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


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

    print(int(dp[H]))


if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

Accepted