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: Runtime Error

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

for ni in range(1, n+1):
  a, b = map(int, input().split())
  for hi in range(1, h+1):
    nj = min(j+a, h)
    dp[nj] = min(dp[nj], dp[j] + b)

print(dp[h])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

M, N = map(int,input().split())
VW = [[int(x) for x in input().split()] for _ in range(N)]
VW = sorted(VW, key=lambda x:(x[0]/x[1],x[0]))

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

Submission status: Runtime Error

Solution code:
from functools import lru_cache

M, N = map(int,input().split())
VW = [[int(x) for x in input().split()] for _ in range(N)]
VW = sorted(VW, key=lambda x:(x[0]/x[1],x[0]))
@lru_cache(maxsize=None)
def dp(h):
    if h<=0:
        return 0
    else:
        best = float("inf")
        for a,b in VW:
            val = b+dp(h-a)
            if val < best:
                best = val
            else:
                break
        return best
print(dp(M))

Submission status: Runtime Error

Solution code:
import numpy as np
import math

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

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


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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

a = ab[:, 0]
b = ab[:, 1]

dp = np.zeros(h+1, dtype=np.int)
for i in range(1, h+1):
    dp[i] = (dp[i-a]+b).min()

print(dp[h])

Submission status: Runtime Error

Solution code:
var H = sc.ReadInt();
var N = sc.ReadInt();
var A = new int[N];
var B = new int[N];
for (int i = 0; i < N; i++)
{
    A[i] = sc.ReadInt();
    B[i] = sc.ReadInt();
}
var dp = new int[H + 1];
for (int i = 0; i < dp.Length; i++)
{
    dp[i] = int.MaxValue;
}
dp[0] = 0;
for (int i = 0; i < dp.Length; i++)
{
if (dp[i] == int.MaxValue) continue;

 for (int j = 0; j < N; j++)
    {
        var a = A[j];
        var b = B[j];
   
        var ni = Math.Min(H, i + a);

        dp[ni] = Math.Min(dp[ni], dp[i] + b);
    }
}
var ans = dp[H];
Console.WriteLine(ans);

Submission status: Runtime Error

Solution code:
import sys
from collections import deque, defaultdict
from itertools import combinations, permutations
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    H, N = map(int, input().split())
    M = [tuple(int(a) for a in input().split()) for _ in range(N)]
    DP = [1000000000] * (H + 2) #ダメージiを与えるのに必要な最小MP, DP[H+1]はH以上のダメージを与えた場合
    DP[0] = 0
    for i, m in enumerate(M):
        a, b = m
        for j in range(H-a+1): DP[j + a] = min(DP[j + a], DP[j] + b)
        for j in range(H-a+1, H): DP[H + 1] = min(DP[H + 1], DP[j] + b)
    print(min(DP[H], DP[H + 1]))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
def use_dp():
    max_a = max([ab[0] for ab in AB])
    dp = [sys.maxsize for i in range(H+max_a)]
    dp[0] = 0

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

    # H < i < H+max(Ai)の範囲で最小値を求める
    min_mp = sys.maxsize
    for i in range(H, H+max_a):
        min_mp = min(dp[i], min_mp)

    print(min_mp)


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

    use_dp()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

h, n = list(map(int, input().split()))
INF = 10 ** 18
dp = np.full(h + 10001, INF, dtype=np.int64)
dp[0] = 0
for line in sys.stdin:
    a, b = map(int, line.split())
    for s in range(0, h, a):
        sa = s + a
        s2a = s + 2 * a
        dp[sa:s2a] = np.minimum(dp[sa:s2a], dp[s:sa] + b)
print(dp[h:].min())

Submission status: Runtime Error

Solution code:
'''input
9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
'''
from sys import stdin
input = stdin.readline
import math

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


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

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

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

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

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

Submission status: Runtime Error

Solution code:
'''input
9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
'''
from sys import stdin
input = stdin.readline
import math
import sys, resource


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


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

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

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

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

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

Submission status: Runtime Error

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


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



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

damage = np.array(Damage)
cost = np.array(Cost)
dp = np.array(DP)




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

for i in range(1,len(dp)):
    for spell in range(N):
        dp[i] = min(dp[i],dp[max(0,i-damage[spell])]+cost[spell])




print (dp[H])

Submission status: Runtime Error

Solution code:
INF = 1145141919810893
H,N = map(int,input().split())
A=[]
B=[]
memo = [INF]*20000
def HP(K):
    if K<=0:
        return 0
    if memo[K]!=INF:
        return memo[K]
    R=INF
    for i in range(N):
        r = B[i]+HP(K-A[i])
        R=min(R,r)
    memo[K]=R
    return R

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

Submission status: Runtime Error

Solution code:
INF = 1145141919810893
memo = [INF]*20000
def HP(K):
    if K<=0:
        return 0
    if memo[K]!=INF:
        return memo[K]
    R=INF
    for i in range(N):
        r = B[i]+HP(K-A[i])
        R=min(R,r)
    memo[K]=R
    return R

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)
print(HP(H))

Submission status: Runtime Error

Solution code:
h, n  = map(int, input().split())
ab = [list(map(int,input().split())) for i in range(n)]
import copy
newab = copy.deepcopy(ab)
for i in newab:
    i.insert(0,i[0] / i[1])
newab.sort(reverse=True)


ans = 0
def saiki():
    global h
    global ans
    while h > 0:
        for i in newab:
            if h >=i[1]:
                h -= i[1]
                ans +=i[2]
                saiki()
        break
saiki()
gyaku = []
for i in ab:
    gyaku.append([i[1],i[0]])

gyaku.sort()
for i in gyaku:
    if i[1]>=h:
        ans += i[0]
        break
print(ans)

Submission status: Runtime Error

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


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


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

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

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

for _ in range(n):
	a, b = list(map(int, input().split()))
	arr.append([a, b])
# for i in range(n):
# 	a = randint(1, 10** 1)
# 	b = randint(1, 10 ** 2)
# 	arr.append([a, b])
dp = dict()
print(brute(arr, h, dp))

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split())
A = [0]*N
B = [0]*N
C = [0]*N
for i in range(N):
    A[i],B[i] = map(int, input().split())
    C[i] = A[i]/B[i]
for i in range(N):
    for j in range(H+1):
        dp[i+1][j] = min(dp[i][j],dp[i+1][max(j-A[i],0)]+B[i])
print(dp[N][H])

Submission status: Runtime Error

Solution code:
'''input
9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
'''
from sys import stdin
input = stdin.readline
import math


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


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

	
# main starts
h, n = list(map(int, input().split()))
arr = []
barr = []
for _ in range(n):
	a, b = list(map(int, input().split()))
	arr.append(a)
	barr.append(b)
dp = dict()
print(brute(arr, barr, h, dp))

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque


def main():
    n_d_a = sys.stdin.readline().strip().split(' ')
    n, d, a = [int(s) for s in n_d_a]

    xh = [None] * n

    for i in range(n):
        x, h = [int(s) for s in sys.stdin.readline().strip().split(' ')]
        xh[i] = [x, h]
    xh.sort()

    cur = 0
    attack_rightmost_idx = [-1] * n
    for i in range(n):
        if cur == n:
            attack_rightmost_idx[i] = n-1
            continue
        attack_rightmost_idx[i] = cur
        x, h = xh[i]
        attack_rightmost = x + 2 * d
        while cur < n and xh[cur][0] <= attack_rightmost:
            attack_rightmost_idx[i] = cur
            cur += 1

    events = deque()
    total_damage = 0
    ans = 0
    for i in range(n):
        while events and events[0][0] <= i:
            total_damage += events[0][1]
            events.popleft()

        x, h = xh[i]

        remaining_life = h - total_damage
        if remaining_life <= 0:
            continue

        needed = math.ceil(remaining_life / a)
        ans += needed
        total_damage += needed * a
        events.append((attack_rightmost_idx[i]+1, - needed * a))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 8)

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:
        for a, b in AB:
            val = b + dp(h - a)
            if val < best:
                best = val
            else:
                # 更新されなかった場合は、以降の魔法で更新されることはない
                break
        return best


print(dp(H))

Submission status: Runtime Error

Solution code:
import numpy as np


DEBUG = True
dprint = print if DEBUG else lambda *x : x

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

dp = [0]
for h in range(1, H + 1):
    a, b = min(AB, key=lambda i: i[1] + dp[max(0, h - i[0])])
    dp.append(b + dp[max(0, h - a)])    
print(dp[-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def solve(H, N, AB):
    INF = 10e10
    dp = [[INF] * (H+1) for i in range(N+1)]
    dp[0][0] = 0
    A, B = AB[0]
    #print(" ", *range(H+1), sep="\t")
    for j in range(H+1):
        dp[0][j] = min(dp[0][j], dp[0][j-A]+B)
    #print(0, *dp[0], sep="\t")
    for i in range(1,N):
        A, B = AB[i]
        for h in range(H+1):
            dp[i][h] = min(dp[i-1][h], dp[i][max(0, h-A)]+B)
        #print(i, *dp[i], sep="\t")
    
    return(dp[N-1][H])


def main():
    H, N = map(int, input().split())
    AB = []
    for i in range(N):
        A, B = map(int, input().split())
        AB.append((A, B))
    print(solve(H, N, AB))
main()

Submission status: Runtime Error

Solution code:
h,n = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(n)]
INF = 10**10
dp = [INF]*(12000)
dp[0]=0
for a,b in AB:
    for i in range(h):
        if dp[i+a]>=dp[i]+b:
            dp[i+a]=dp[i]+b

print(min(dp[h:]))

Submission status: Runtime Error

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

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

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


def attack(h0, i, memo):
    if h0 <= 0:
        return 0

    if memo[i][h0] != 0:
        return memo[i][h0]

    h = h0
    a, b = magic[i]
    if i+1 == len(magic):
        total = (h // a) * b
        if (h % a) != 0:
            return total + b
        return total

    ret = min(b + attack(h-a,i,memo), attack(h, i+1,memo))
    memo[i][h0] = ret
    return ret
    
memo = []
for i in range(len(magic)):
    memo.append([0] * (h + 1))

print(attack(h, 0, memo))

Submission status: Runtime Error

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

INF = 10**10
dp = [INF]*(12000)
dp[0]=0
for a,b in AB:
    for i in range(h):
        if dp[i+a]>=dp[i]+b:
            dp[i+a]=dp[i]+b

print(min(dp[h:]))

Submission status: Runtime Error

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

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

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

def attack(h, i):
    if h < 0:
        return 0
    a, b = magic[i]
    if i+1 == len(magic):
        total = (h // a) * b
        if (h % a) != 0:
            return total + b
        return total
    return min(b + attack(h-a,i), attack(h, i+1))
    
print(attack(h, 0))

Submission status: Runtime Error

Solution code:
import sys

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

INF = 10**10
dp = [INF]*(2*h)
dp[0]=0
for a,b in AB:
    for i in range(h):
        if dp[i+a]>=dp[i]+b:
            dp[i+a]=dp[i]+b

print(min(dp[h:]))

Submission status: Runtime Error

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

INF = 10**10
#print(magic)

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

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

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
  int H,N,A,B;
  cin >> H >> N;
  vector<int> dp(H+1,100000001);
  dp[0] = 0;
  for(int n=0; n<N; n++){
    cin >> A >> B;
    for(int h=1; h<H+1; h++){
      dp[h] = min(dp[h],dp[max(0,h-A)]+B);
    }
  }
  cout << dp[H] << endl;
}

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(int argc, char* argv[])
{
  int H,N,A,B;
  cin >> H >> N;
  vector<int> dp(H+1,1000000000);
  dp[0] = 0;
  for(int n=0; n<N; n++){
    cin >> A >> B;
    for(int h=1; h<H+1; h++){
      dp[h] = min(dp[h],dp[max(0,h-A)]+B);
    }
  }
  cout << dp[H];
  return 0;
}

Submission status: Runtime Error

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

Submission status: Runtime Error

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

dp = [np.inf for _ in range(H+1)]

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

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(int argc, char* argv[])
{
  int H,N,A,B;
  cin >> H >> N;
  vector<int> dp(H+1,1000000000);
  dp[0] = 0;
  for(int n=0; n<N; n++){
    cin >> A >> B;
    for(int h=1; h<H+1; h++){
      dp[h] = min(dp[h], dp[max(0,h-A)]+B);
    }
  }
  cout << dp[H] << endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
read=sys.stdin.read

h,n,*ab=map(int,read().split())
a=np.array(ab[::2])
b=np.array(ab[1::2])

magic=np.zeros(h+1)
for i in range(1,1+h):
  magic[i]=np.min(dp[np.maximum(i-a, 0)]+b)
print(magic[h])

Submission status: Runtime Error

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

dp=[0]+[None]*(H)

for i in range(N):
    A,B=map(int,input().split())
    ndp=copy.deepcopy(dp)
    for i in range(A,H+1):
        if dp[i]==None:
            if ndp[i-A]==None:
                ndp[i]=None
            else:
                ndp[i]=ndp[i-A]+B
        else:
            if dp[i-A]==None:
                ndp[i]=dp[i]
            else:
                ndp=min(dp[i],dp[i-A]+B)
    
    mi=B*math.ceil(H/A)
    
    for i in range(H%A+1):
        if ndp[-(i+1)]==None:
            pass
        else:
            mi=min(mi,ndp[-(i+1)]+B)
    
    if ndp[-1]==None:
        ndp[-1]=mi
    else:
        ndp[-1]=min(ndp[-1],mi)

    dp=ndp
    #print(dp)

print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque, defaultdict
from itertools import combinations, permutations
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    H, N = map(int, input().split())
    M = [tuple(int(a) for a in input().split()) for _ in range(N)]
    DP = [[10000000 for _ in range(H + 2)] for i in range(N)]
    a0, b0 = M[0]
    for d in range(100000):
        if d * a0 >= H + 1:
            DP[0][H + 1] = d * b0
            break
        else: DP[0][d * a0] = d * b0
    for i in range(1, N):
        a, b = M[i]
        for j in range(H + 1):
            if DP[i - 1][j] < 10000000:
                if j < a: DP[i-1][j]
                else: DP[i][j] = min(DP[i-1][j], DP[i][j - a] + b)
        DP[i][H + 1] = min(DP[i][H + 1], DP[i-1][H + 1])
        DP[i][H + 1] = min(DP[i][H + 1], min(DP[i][H-a+1:H]) + b)
    
    print(min(DP[N-1][H], DP[N-1][H+1]))
    #print(DP)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
INF=10**10
def main():
  H,N=map(int,input().split())
  AB=[]
  for i in range(N):
    AB.append(list(map(int,input().split())))
  dp=[INF]*(H+1)
  dp[0]=0
  for a,b in AB:
    for k in range(H+1):
      tmp=k-a
      if tmp<0:
        tmp=0
      need_magic=dp[tmp]+b
      if need_magic<dp[k]:
        dp[k]=need_magic
  print(dp[H+1])
main()

Submission status: Runtime Error

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

for i in range(N):
    a, b = map(int, input().split())
    damage.append(a)
    mp.append(b)

dp = [[0]+[float("inf")]*H for _ in range(N + 1)]

for j in range(1, H + 1):
    if j % damage[0] == 0:
        x = j // damage[0]
    else:
        x = j // damage[0] + 1 
    dp[1][j] = x * mp[0]

for i in range(1, N):
    for j in range(H + 1):
        dp[i + 1][j] = min(dp[i][j], dp[i][j - damage[i]] + mp[i])

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

print(dp[N][H])

Submission status: Runtime Error

Solution code:
import numpy as np
from math import ceil
from copy import copy
from queue import PriorityQueue

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

pque = PriorityQueue()

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

magic = np.array(magic)
idx = np.argsort(magic[:,0])
magic = magic[idx[::-1],:]

dp = np.ones(H + magic[:,0].max() * 2 + 1) * np.inf
dp[0] = 0 

def func(i):
    for m in magic:
        idx2 = i+m[0]
        if dp[i] + m[1] < dp[idx2]:
            dp[idx2] = dp[i] + m[1]
            if dp[idx2] < dp[H] and i+m[0] < H:
               func(idx2) 

func(0)

print(int(dp[H:].min()))

Submission status: Runtime Error

Solution code:
#E
#部分的WA

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

lst.sort(key=lambda x: x[2])
asn = 0

dp = [float("Inf")]*(h+1)
dp[0] = 0

#なぜかループに入らない、完全にbreakの位置をミスっていた(いらなかった、、)
for i in range(n-1,-1,-1):
    Flag =True
    a = lst[i][0]
    b = lst[i][1]
    for j in range(h-1,-1,-1):
        if Flag:
            if dp[j] != float("Inf"):
                Flag =False
                for k in range(min(j,h-a),h):
                    if dp[k] != float("Inf"):
                        if dp[k] + b < dp[min(k+a,h)]:
                            dp[min(k+a,h)] = dp[k] + b
print(dp[h])
#print(dp)

Submission status: Runtime Error

Solution code:
def attk(HP,Magic,D0):
    T = HP // Magic[0][0]
    MD0 = T * Magic[0][1]
    MD1 = (T+1) * Magic[0][1]
    Z = HP % Magic[0][0]
    ND = Magic[0][1]
    if Z == 0:
        return MD0
    if len(Magic) == 1:
        return MD1
    Magic.pop(0)
    A = attk(Z,Magic,ND)
    if D0 > MD0+A:
        if MD1 > MD0+A:
            return MD0+A
        else:
            return MD1
    else:
        return D0


H,N = map(int,input().split())
A =[]
for i in range(N):
    a,b = map(int,input().split())
    A.append((a,b,a/b))
#print(A)
B = sorted(A, key=lambda s: s[1]) 
C = sorted(B, key=lambda s: s[2], reverse=True) 
#print(C)

for i in range(N-1):
    if C[N-1-i][2] ==C[N-2-i][2]:
        C.pop(N-1-i)
#print(C)
TDMAX = (H // C[0][0])*C[0][1]
if (H%C[0][0])!=0:
    TDMAX += C[0][1]
TD = attk(H,C,TDMAX)
print(TD)

Submission status: Runtime Error

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

dp=[]
dp.append([None]*(H+1))

for i in range(N):
    A,B=map(int,input().split())
    new_dp=copy.deepcopy(dp[-1])
    for i in range(A,H+1):
        if dp[-1][i-A]==None:
            if i%A==0 and dp[-1][i]==None:
                new_dp[i]=B*i//A
            elif i%A==0:
                new_dp[i]=min(dp[-1][i],B*i//A)
            else:
                new_dp[i]=None

            continue

        if dp[-1][i]==None:
            new_dp[i]=dp[-1][i-A]+B
        else:
            new_dp[i]=min(dp[-1][i],dp[-1][i-A]+B)
        
    if new_dp[-1]==None:
        new_dp[-1]=math.ceil(H//A)*B
    else:
        new_dp[-1]=min(new_dp[-1],math.ceil(H//A)*B)

    for i in range(A):
        if dp[-1][1+H-A+i]==None:
            pass
        else:
            new_dp[-1]=min(new_dp[-1],dp[-1][1+H-A+i] + B)
    

    dp.append(new_dp)

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

Submission status: Runtime Error

Solution code:
def attk(HP,Magic,D0):
    T = HP // Magic[0][0]
    MD0 = T * Magic[0][1]
    MD1 = (T+1) * Magic[0][1]
    Z = HP % Magic[0][0]
    ND = Magic[0][1]
    if Z == 0:
        return MD0
    if len(Magic) == 1:
        return MD1
    Magic.pop(0)
    A = attk(Z,Magic,ND)
    if D0 > MD0+A:
        if MD1 > MD0+A:
            return MD0+A
        else:
            return MD1
    else:
        return D0

H,N = map(int,input().split())
A =[]
for i in range(N):
    a,b = map(int,input().split())
    A.append((a,b,a/b))
#print(A)
B = sorted(A, key=lambda s: s[1]) 
C = sorted(B, key=lambda s: s[2], reverse=True) 
#print(C)

for i in range(N-1):
    if C[N-1-i][2] ==C[N-2-i][2]:
        C.pop(N-1-i)
#print(C)
TDMAX = (H // C[0][0])*C[0][1]
if (H%C[0][0])!=0:
    TDMAX += C[0][1]
TD = attk(H,C,TDMAX)
print(TD)

Submission status: Runtime Error

Solution code:
from mypulp import *

model = Model('aaa')
a=[int(i) for i in input().split()]
b=[input().split() for i in range(a[1])]
x={}
for j in range(1,a[1]+1):
    x[j]=model.addVar(vtype='I',name=f'x({j})')
model.update()
model.addConstr(quicksum(int(b[j-1][0])*x[j] for j in range(1,a[1]+1))>=a[0])
a=quicksum(int(b[j-1][1])*x[j] for j in range(1,a[1]+1))
model.setObjective(a, GRB.MINIMIZE )
model.optimize()
print(int(model.ObjVal))

Submission status: Runtime Error

Solution code:
def run():
  H, N = map(int, input().split())
  ab_li = [tuple(map(int, input().split())) for n in range(N)]
  dp = [float('inf')]*(H+1)
  for i in range(1, H+1):
    for n in range(N):
      a, b = ab_li[n]
      if i == a:
        dp[i] = min(dp[i], b)
      if (i < a) or (dp[i-a] == float('inf')):
        continue
      dp[i] = min(dp[i], dp[i-a]+b)
  if dp[-1] == float('inf'):
    for h in range(H, 0, -1):
      if dp[h] != float('inf'):
        ans = dp[h]+min(ab_li, key=lambda x:x[1])[1]
        break
  else:
    ans = dp[-1]
  for n in range(N):
    a, b = ab_li[n]
    if a > H:
      ans = min(ans, b)
  print(ans)
  
if __name__ == '__main__':
  run()

Submission status: Runtime Error

Solution code:
INF = 10**9

def unboundedKnapsack(H, n, damage, mana): 
    dp = [INF for i in range(H + 1)] 
    for i, d in enumerate(damage):
        dp[d] = mana[i]
    for i in range(H + 1): 
        for j in range(n): 
            if (i-damage[j] >= 0): 
                dp[i] = min(dp[i - damage[j]]+mana[j], dp[i]) 
            # else:
            #     dp[i] = min(dp[i +1 ], dp[i]) 
    return dp[H]

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

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
INF = 10**9

def unboundedKnapsack(H, n, damage, mana): 
    dp = [INF for i in range(H + 1)] 
    for i, d in enumerate(damage):
        dp[d] = mana[i]
    for i in range(H + 1): 
        for j in range(n): 
            if (i-damage[j] >= 0): 
                dp[i] = min(dp[i - damage[j]]+mana[j], dp[i]) 
            else:
                dp[i] = min(dp[i +1 ], dp[i]) 
    return dp[H]

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

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

for i in range(H+1):
	dp[i] = min(B[j]  if h < A[j]  else  dp[i - A[j]] + B[j]  for j in range(n))

print(dp[H])