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

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class RangeMinimumQuery:
    def __init__(self, n, func=min, inf=float("inf")):
        self.n0 = 2**(n-1).bit_length()
        self.op = func
        self.inf = inf
        self.data = [self.inf]*(2*self.n0)

    def construct(self, lis):
        for i, x in enumerate(lis):
            self.data[i+self.n0-1] = x
        for i in range(self.n0-2, -1, -1):
            self.data[i] = self.op(self.data[2*i+1], self.data[2*i+2])

    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.inf
        while l < r:
            if r&1:
                r -= 1
                res = self.op(res, self.data[r-1])
            if l&1:
                res = self.op(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i+1:
            i = ~-i//2
            self.data[i] = self.op(self.data[2*i+1], self.data[2*i+2])

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

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

for i in range(n):
    damage, mana = bag[i]
    for w in range(h+1):
        dp[i+1][w] = min(dp[i+1][w], dp[i][w])
        if w >= damage:
            dp[i+1][w] = min(dp[i+1][w], dp[i+1][w-damage]+mana)

data = dp[-1]
rmq = RangeMinimumQuery(len(data))
rmq.construct(data)
ans = data[-1]
for a,b in bag:
    if a >= h:
        ans = min(ans, b)
    else:
        tmp = rmq.query(h-a, h) + b
        ans = min(ans, tmp)
print(ans)

Submission status: Accepted

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

# dp[damage] := モンスターに damage を与えるために必要な最小コスト
dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)

print(dp[-1])

Submission status: Accepted

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

INF = 10**9
dp = [INF]*(3*(10**4))
dp[0] = 0

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

H,N = II()
A,B = Line(N,2)

dp = [float('inf')]*(H+1)
dp[0] = 0
for i in range(1,H+1):
    for j in range(N):
        temp = i-A[j]
        if temp>=0:
            dp[i] = min(dp[i],dp[i-A[j]]+B[j])
        else:
            dp[i] = min(dp[i],dp[0]+B[j])

print(dp[-1])

Submission status: Accepted

Solution code:
H,N=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
dp=[0]*10001+[10**9]*H
for i in range(1,H+10001):
    for a,b in AB:
        if i>=a:
            dp[i]=min(dp[i],dp[i-a]+b)
print(dp[-1])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    inf = 10**10
    dp = [[inf] * (H+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        a = A[i]
        b = B[i]
        for h in range(H+1):
            dp[i+1][h] = min(dp[i+1][h], dp[i][h])
            dp[i+1][min(h+a, H)] = min(dp[i+1][min(h+a, H)], dp[i+1][h] + b)
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

H, N = map(int, input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]
AB.sort(key=lambda x: x[0]/x[1], reverse=True)

INF = 10 ** 18
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB :
  for i in range(H + 1) :
    if dp[i] != INF :
      ni = min(H, i + A)
      dp[ni] = min(dp[ni], dp[i] + B)
      
print(dp[-1])

Submission status: Accepted

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

D=[1<<31]*(H+10**4)
D[0]=0

for hp in range(H):
    for a,b in M:
        D[hp+a]=min(D[hp+a],D[hp]+b)
print(min(D[H:]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    DP = [INF]*(H+1)
    DP[0] = 0
    for i in range(H):
        for a, b in zip(A, B):
            m = min(i+a, H)
            DP[m] = min(DP[i]+b, DP[m])
    print(DP[-1])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Y = [0] + [1<<30] * H
for i in range(H):
    for a, b in X:
        j = min(i+a, H)
        Y[j] = min(Y[j], Y[i] + b)

print(Y[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    dp = [float('inf')] * (H + 1)
    dp[0] = 0
    for i in range(N):
        for j in range(H + 1):
            tmp = min(H, j + A[i])
            dp[tmp] = min(dp[tmp], dp[j] + B[i])
    print(dp[H])
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [10**10] * (H + 1)
dp[H] = 0

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

print(dp[0])

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

h, n = na()
ab = []
for i in range(n):
    ab.append(na())

dp = [99999999999999999] * (h+1)
dp[h] = 0
ans = 9999999999999999999
for u in ab:
    for i in range(h, u[0]-1, -1):
        dp[i-u[0]] = min(dp[i-u[0]], dp[i] + u[1])
    for i in range(min(u[0]+1, h+1)):
        ans = min(ans, dp[i] + u[1])
print(ans)

Submission status: Runtime Error

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

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from math import ceil
sys.setrecursionlimit(10**6)
def main():
    INF = 10**9
    h,n = map(int,input().split())
    spell = []
    for _ in range(n):
        spell.append(tuple(map(int,input().split())))

    dp = [[INF]*(h+1) for _ in range(n+1)]

    for i,item in enumerate(spell):
        a,b = item
        for j in range(h):
            if j-a<0:
                dp[i+1][j+1] = min(dp[i][j+1],b*ceil((j+1)/a))
            else:
                dp[i+1][j+1] = min(dp[i][j+1],dp[i+1][j+1-a]+b)
        
    print(dp[n][h])
main()

Submission status: Runtime Error

Solution code:
from collections import deque
h,n = map(int, input().split())
p = [10**10]*(2*h)
ab = []
for _ in range(n):
  ab.append(tuple(map(int,input().split())))
q = deque()
for i in ab:
  q.append(i)
while q:
  a,b = q.popleft()
  if b<p[a]: p[a]=b
  else: b=p[a]
  if a>=h: continue
  for i,j in ab:
    if b+j<p[a+i]:
      p[a+i]=b+j
      q.append((a+i,b+j))
print(min(p[h:-1]))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
ls = [[-1]*(H+1) for _ in range(N)]
for h in range(H+1):
  tmp1 = h // A[0]
  tmp2 = h % A[0]
  if tmp2 == 0:
    ls[0][h] = B[0]*tmp1
  else:
    ls[0][h] = B[0]*(tmp1 + 1)
def battle(h, n):
  if ls[n][h] != -1:
    return ls[n][h]
  else:
    if h == 0:
      ls[n][h] = 0
      return ls[n][h]
    else:
      tmp_ls = []
      tmp = h
      item = 0
      while tmp >= 0:
        tmp_ls.append(battle(tmp, n-1)+item*B[n])
        item += 1
        tmp -= A[n]
      tmp_ls.append(item*B[n])
      ls[n][h] = min(tmp_ls)
      return ls[n][h]

print(battle(H, N-1))

Submission status: Runtime Error

Solution code:
H, N = map(int,input().split())
M = []
for k in range(N):
    M.append(list(map(int,input().split())))
dp = [10**9]*(H+1)
dp[0] = 0
for A, B in M:
    for k in range(A+1):
        dp[k] = min(dp[k],B)
    for k in range(A+1,H+1):
        dp[k] = min(dp[k],dp[k-A]+B)
print(dp[H])

Submission status: Runtime Error

Solution code:
H,N=map(int,input().split())
AB=[]
for i in range(N):
  AB.append(list(map(int,input().split())))
dp=[0]*(10**9)
dp[0]=0
i=0

while True:
  i+=1
  for A,B in AB:
    if i-B>=0:
      dp[i]=max(dp[i-B]+A,dp[i])
  if dp[i]>=H:
    break
print(i)

Submission status: Runtime Error

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

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

dp = [0 for _ in range(H+1)]

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

print(dp[H-1])

Submission status: Runtime Error

Solution code:
H,N=map(int,input().split())
AB=[]
for i in range(N):
  AB.append(list(map(int,input().split())))
INF=10**8
dp=[0]*(10**7)
dp[0]=0
i=0

while True:
  i+=1
  for A,B in AB:
    if i-B>=0:
      dp[i]=max(dp[i-B]+A,dp[i])
  if dp[i]>=H:
    break
print(i)

Submission status: Runtime Error

Solution code:
H,N = map(int,input().split())
AB = [map(int,input().split()) for _ in range(N)]
A,B = [list(i) for i in zip(*AB)]
A_min = min(A)
eff_list = [0 for i in range(N)]
for i in range(N):
    eff_list[i] = A[i] / B[i]
eff_max_index_list =[]
eff_max = max(eff_list)
for i in range(N):
    if eff_list[i] == eff_max:
        eff_max_index_list.append(i)
total_mp_min_list = []
for i in range(len(eff_max_index_list)):
    index = eff_max_index_list[i]
    count = H // A[index]
    mod = H - A[index] * count
    min_mp = B[index]
    if mod == 0:
        total_mp = B[index] * count
    else:
        index_tmp = index
        for j in range(N):
            count_tmp = mod //  A[j]
            if mod % A[j] == 0:
                mp_tmp = B[j] * count_tmp
            else:
                mp_tmp = B[j] *(count_tmp + 1)
            if  mp_tmp < min_mp:
                min_tmp = mp_tmp
                index_tmp = j
        total_mp = B[index] * count + min_tmp
    total_mp_min_list.append(total_mp)
print(min(total_mp_min_list))

Submission status: Runtime Error

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

dp=[float('inf')]*(h+1)
dp[0]=0
for i in range(h):
    for j in range(n):
		if dp[i] == float('inf'):continue
        next=i+ab[j][0] if i+ab[j][0]<=h else h
        dp[next]=min(dp[next],dp[i]+ab[j][1])
print(dp[-1])

Submission status: Runtime Error

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

dp=[float('inf')]*(h+1)
dp[0]=0
for i in range(h):
    for j in range(n):
		temp_a = i + ab[j][0] if i + ab[j][0] <= h else h
        temp_b = dp[i] + ab[j][1]
        dp[temp_a]=min(dp[temp_a],temp_b)
print(dp[-1])

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

#DP[i] = i までの魔法でモンスターの体力を減らすため消耗する魔力の最小値
dp = [0] * h

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

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

#DP[i] = i までの魔法でモンスターの体力を減らすため消耗する魔力の最小値
dp = [0] * h

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline()
H,N = map(int,input().split())
spells = [list(map(int,input().split())) for i in range(N)]
INF = 10**10
dp = [INF]*(H+1)
dp[0] = 0
for use in spells:
    damage = use[0]
    mp = use[1]
    for i in range(1,H+1):
        dp[i] = min(dp[max(0,i-damage)] + mp, dp[i])
print(dp[-1])

Submission status: Runtime Error

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

magics = [None]


class Magic:
    def __init__(self, attack, cost):
        self.attack = attack
        self.cost = cost


maxA = 0
for i in range(n):
    attack, cost = [int(i) for i in input().split()]
    maxA = max(maxA, attack)
    magics.append(Magic(attack, cost))

dp = [[10 ** 9 for i in range(h + 1)] for j in range(n + 1)]

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

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)

h, n = list(map(int, input().split(' ')))
d ={}
for i in range(n):
  a, b = list(map(int, input().split(' ')))
  d[b] = max(a, d.get(b, 0))

ld = [(k,v) for k, v in d.items()]
len_d = len(ld)
memo = {}
def f(index, current, damage):
  memo[current] = max(memo.get(current, 0), damage)
  for i in range(index, len_d):
    if damage+ld[i][1] <= h:
      f(i, current+ld[i][0], damage+ld[i][1])

f(0, 0, 0)

print(memo[h])

Submission status: Runtime Error

Solution code:
h, n = list(map(int, input().split(' ')))
d ={}
for i in range(n):
  a, b = list(map(int, input().split(' ')))
  d[b] = max(a, d.get(b, 0))
#print(d)
best = 0
best_k = 0
best_v = 0
sorted_d = sorted(d)[::-1]
for k in sorted(d):
  v = d[k]
  if best < v / k:
    best = v / k
    best_k = k
    best_v = v
temp = 0
while h >= sorted_d[0]:
  h -= best_v
  temp += best_k
#print(h, temp, best_k, best, best * best_k)
ans = 9999999999999999999999
memo = {}
def f(current, damage):
  #print(current, damage, h)
  global ans
  if damage and memo.get(current, 0) >= damage:
    return memo.get(current, 0)
  memo[current] = damage
  if damage >= h:
    ans = min(ans, current)
    return ans
  hoge = 0
  for k in sorted_d:
    hoge = max(hoge, f(current+k, damage+d[k]))
  return hoge
f(0, 0)
#print(temp, (ans if ans != 9999999999999999999999 else 0))
print(temp + (ans if ans != 9999999999999999999999 else 0))

Submission status: Runtime Error

Solution code:
h, n = list(map(int, input().split(' ')))
d ={}
for i in range(n):
  a, b = list(map(int, input().split(' ')))
  d[b] = max(a, d.get(b, 0))
#print(d)
best = 0
best_k = 0
best_v = 0
for k in sorted(d):
  v = d[k]
  if best < v / k:
    best = v / k
    best_k = k
    best_v = v
temp = 0
while h/n >= best_v:
  h -= best_v
  temp += best_k
#print(h, temp, best_k, best, best * best_k)
ans = 9999999999999999999999
memo = {}
sorted_d = sorted(d)[::-1]
def f(current, damage):
  #print(current, damage, h)
  global ans
  if damage and memo.get(current, 0) >= damage:
    return memo.get(current, 0)
  memo[current] = damage
  if damage >= h:
    ans = min(ans, current)
    return ans
  hoge = 0
  for k in sorted_d:
    hoge = max(hoge, f(current+k, damage+d[k]))
  return hoge
f(0, 0)
#print(temp, (ans if ans != 9999999999999999999999 else 0))
print(temp + (ans if ans != 9999999999999999999999 else 0))

Submission status: Runtime Error

Solution code:
h, n = list(map(int, input().split(' ')))
d ={}
for i in range(n):
  a, b = list(map(int, input().split(' ')))
  d[b] = max(a, d.get(b, 0))
#print(d)
best = 0
best_k = 0
for k in sorted(d):
  v = d[k]
  if best < v / k:
    best = v / k
    best_k = k
temp = 0
#while h/30 >= best * best_k:
#  h -= (best * best_k)
#  temp += best_k
#print(h, temp, best_k, best, best * best_k)
ans = 9999999999999999999999
memo = {}
sorted_d = sorted(d)[::-1]
def f(current, damage):
  #print(current, damage, h)
  global ans
  if damage and memo.get(current, 0) >= damage:
    return memo.get(current, 0)
  memo[current] = damage
  if damage >= h:
    ans = min(ans, current)
    return ans
  hoge = 0
  for k in sorted_d:
    hoge = max(hoge, f(current+k, damage+d[k]))
  return hoge
f(0, 0)
#print(temp, (ans if ans != 9999999999999999999999 else 0))
print(temp + (ans if ans != 9999999999999999999999 else 0))

Submission status: Runtime Error

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    h,n = map(int,ipt().split())
    atks = [tuple(map(int,ipt().split())) for i in range(n)]
    dam = [10**18]*(h+1)
    dam[0] = 0
    for i in range(1,h+1):
        for aj,bj in atks:
            if aj > i and dam[i] > bj:
                dam[i] = bj
            elif dam[i] > dam[i-aj]+bj:
                dam[i] = dam[i-aj]+bj

    print(dam[h])

    return None

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)


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


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

for h in range(1, H+1):
    dp[h] = min([dp[h-a[i][0]] + a[i][1] for i in range(N)])

print(dp[H])

Submission status: Runtime Error

Solution code:
(h,n),*c=[[*map(int,i.split())]for i in open(0)]
dp=[10**9]*h**3
dp[0]=0
for i in range(h):
    for a,b in c:
        dp[i+a]=min(dp[i+a],dp[i]+b)
print(min(dp[h:]))

Submission status: Runtime Error

Solution code:
(h,n),*c=[[*map(int,i.split())]for i in open(0)]
dp=[10**9]*h*2
dp[0]=0
for i in range(h):
    for a,b in c:
        dp[i+a]=min(dp[i+a],dp[i]+b)
print(min(dp[h:]))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def knapsack_price(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[price <= V] = 価値を固定した時の最大重量 """
    V = 10**6
    dp_max = 0
    dp = [dp_max] * (V + 1)
    dp[0] = 0   # 境界条件：　価値0 の時は重さは0

    for item in range(N):
        if single:
            S = range(V, price_list[item]-1, -1)
        else:
            S = range(price_list[item], V + 1)
        for price in S:
            dp[price] = max2(dp[price], dp[price - price_list[item]] + weight_list[item])
    return min(price for price in range(V+1) if dp[price] >= W)


#######################################################################################################
import sys
input = sys.stdin.readline


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y

def min2(x, y):
    """ pythonの組み込み関数 min は2変数に対しては遅い！！ """
    if x < y:
        return x
    else:
        return y


W, N = map(int, input().split())                                # N: 品物の種類 W: 重量制限

price_list = []
weight_list = []
for _ in range(N):
    """ price と weight が逆転して入力されている場合有り """
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)


print(knapsack_price(single=False))


############################################################################################

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math
H,N=map(int,input().split())
A=[]
B=[]
for i in range(N):
    n,a=input().split()
    A.append(int(n))
    B.append(int(a))
C=[]
for i in range(N):
    C.append(A[i]/B[i])
sub=0
for i in range(N):
    if C[i]>=C[sub]:
        sub=i
sub2=math.ceil(H/A[sub])
sub3=sub2*B[sub]
def f(x):
    if x<=0:
        return 0
    else:
        mini=f(x-A[0])+B[0]
        for i in range (1,N):
            sub=f(x-A[i])+B[i]
            if sub<mini:
                mini=sub
        return mini
for ia in range(H,sub2*A[sub]):
    if f(ia)<sub3:
        sub3=f(ia)
print(sub3)

Submission status: Runtime Error

Solution code:
h, n = map(int, input().split())
list_AB = [ list(map(int,input().split(" "))) for _ in range(n)]
dp = [pow(10, 8)]*pow(10, 5)
dp[0] = 0
for atk, mp in list_AB:
    for i in range(atk, h+atk):
        dp[i] = min(dp[i], dp[i-atk]+mp)
k = h
ans = 0

while True:
    if dp[k] != pow(10, 8):
        ans = dp[k]
        break
    k += 1

print(ans)

Submission status: Runtime Error

Solution code:
h, n = map(int, input().split())
list_AB = [ list(map(int,input().split(" "))) for _ in range(n)]
dp = [pow(10, 8)]*pow(10, 5)
dp[0] = 0
for atk, mp in list_AB:
    for i in range(atk, h+pow(10, 4)):
        dp[i] = min(dp[i], dp[i-atk]+mp)
k = h
ans = 0

while True:
    if dp[k] != pow(10, 8):
        ans = dp[k]
        break
    k += 1

print(ans)

Submission status: Runtime Error

Solution code:
import math
import numpy as np
H,N=map(int,input().split())
A=[]
B=[]
for i in range(N):
  n,a=input().split()
  A.append(int(n))
  B.append(int(a))
C=[]
for i in range(N):
  C.append(A[i]/B[i])
sub=0
for i in range(N):
  if C[i]>=C[sub]:
    sub=i
sub2=math.ceil(H/A[sub])
sub3=sub2*B[sub]
for ia in range(H,sub2*A[sub]):
  t = ia
  M = len(A) - 1
  elm = []
  for i, step in enumerate(A):
    temp = [1] * (M - i)
    elm.append(np.arange(0, t+1, step).reshape(-1, *temp))
  res = 0
  for x in elm:
    res = res + x
  for x in np.argwhere(res == t):
    sub4=0
    for ib in range(N):
      sub4+=B[ib]*x[ib]
    if sub4<=sub3:
      sub3=sub4
print(sub3)

Submission status: Runtime Error

Solution code:
import math
import numpy as np
H,N=map(int,input().split)
A=[]
B=[]
for i in range(N):
    n,a=input().split()
    A.append(int(n))
    B.append(int(a))
C=[]
for i in range(N):
  C.append(A[i]/B[i])
sub=0
for i in range(N):
  if C[i]>=C[sub]:
    sub=i
sub2=math.ceil(H/A[sub])
sub3=sub2*B[sub]
for ia in range(H,sub2):
  t = ia
  M = len(A) - 1
  elm = []
  for i, step in enumerate(A):
    temp = [1] * (M - i)
    elm.append(np.arange(0, t+1, step).reshape(-1, *temp))
  res = 0
  for x in elm:
    res = res + x
  sub4=0
  for x in np.argwhere(res == t):
    for ib in range(N):
    sub4+=B[ib]*x[ib]
  if sub4<=sub3:
    sub3=sub4
print(sub3)

Submission status: Runtime Error

Solution code:
h, n = map(int, input().split())
dp = [0] * (h+1001)
a, b = map(int, input().split())
for j in range(1, h+1001):
    dp[j] = b*(-(-j//a))

for _ in range(n-1):
    a, b = map(int, input().split())
    ndp = dp.copy()

    for j in range(a, h+1001):
        ndp[j] = min(dp[j], ndp[j-a]+b)
    dp = ndp

print(min(ndp[h:]))

Submission status: Runtime Error

Solution code:
h, n = map(int, input().split())
INF = 1000*n + 1
dp = [INF] * (h+1)
dp[0] = 0
a, b = map(int, input().split())
for j in range(1, h+1):
    dp[j] = b*(-(-j//a))

for _ in range(n-1):
    a, b = map(int, input().split())
    ndp = dp.copy()

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

print(ndp[-1])

Submission status: Runtime Error

Solution code:
def main():
    INF = 10 ** 10
    H, N = list(map(int, input().split(' ')))
    magic = [list(map(int, input().split(' '))) for _ in range(N)]
    memo = [[INF for _ in range(N)] for _ in range(H + 1)]

    def dfs(h, i=None):
        if h <= 0:
            return 0
        if i is not None and memo[h][i] < INF:
            return memo[h][i]
        ret = INF
        for j in range(N):
            a, b = magic[j]
            ret = min(ret, b + dfs(h - a, j))
        if i is not None:
            memo[h][i] = ret
        return ret

    print(dfs(H))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

AB = [list(map(int, input().split())) for _ in range(N)]
#print(AB)
#print(AB[0])
dp = [[0]*10000000 for _ in range(N+1)]
#print(dp)
ans = 1000000
for i in range(1, N+1):
    for j in range(1, 10000000):
        if j >= AB[i-1][1]:
            dp[i][j] = max(dp[i][j-AB[i-1][1]]+AB[i-1][0], dp[i-1][j])
        else:
            dp[i][j] = dp[i][j-1]
        if dp[i][j] >= H:
            if ans > j:
                ans = j
            break

#print(dp)
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

def solve():
    INF = float('inf')

    def min2(x, y): return x if x <= y else y

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

    items.sort()

    dp = [INF] * (H+1)
    dp[0] = 0
    for vi, wi in items:
        for j in range(H-vi+1):
            dp[j+vi] = min2(dp[j+vi], dp[j]+wi)
        for j in range(H-vi+1, H+1):
            dp[H] = min2(dp[H], dp[j]+wi)
#        print(dp)

    print(dp[H])


solve()