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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    h, n = (int(x) for x in input().split())
    ab = []
    for _ in range(n):
        a, b = (int(x) for x in input().split())
        ab.append([a, b])
    dp = [float('inf')] * (h)
    for a, b in ab:
        for i in range(h):
            if i < a:
                dp[i] = min(dp[i], b)
            else:
                dp[i] = min(dp[i], dp[i - a] + b)
    print(dp[h - 1])
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h, n = (int(x) for x in input().split())
    ab = []
    for _ in range(n):
        a, b = (int(x) for x in input().split())
        ab.append([a, b])
    dp = [float('inf')] * (h)
    for a, b in ab:
        for i in range(h):
            if i < a:
                dp[i] = min(dp[i], b)
            else:
                dp[i] = min(dp[i], dp[i - a] + b)
    print(dp[h - 1])
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h, n = (int(x) for x in input().split())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
dp = [float('inf')] * (h)
for a, b in ab:
    for i in range(h):
        if i < a:
            if dp[i] > b:
                dp[i] = b
        else:
            if dp[i] > dp[i - a] + b:
                dp[i] =  dp[i - a] + b
print(dp[h - 1])

Submission status: Time Limit Exceeded

Solution code:
h, n = (int(x) for x in input().split())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
dp = [float('inf')] * (h)
for a, b in ab:
    for i in range(h):
        if i < a:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i - a] + b)
print(dp[h - 1])

Submission status: Time Limit Exceeded

Solution code:
h, n = (int(x) for x in input().split())
w = []
v = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    w.append(a)
    v.append(b)
dp = [float('inf')] * (h)
for i in range(n):
    for j in range(h):
        if j < w[i]:
            dp[j] = min(dp[j], v[i])
        else:
            dp[j] = min(dp[j], dp[j - w[i]] + v[i])
print(dp[h - 1])

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    H, N = read_values()
    M = [read_list() for _ in range(N)]

    dp = [10 ** 12] * (H + max(M, key=lambda m: m[0])[0] + 10)
    dp[0] = 0
    for h in range(H + 1):
        for a, b in M:
            dp[h + a] = min(dp[h + a], dp[h] + b)
    
    print(min(dp[H:]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
  return sys.stdin.readline()[:-1]
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 = [float('inf')]*(h+max(a))
dp[0] = 0 
for i in range(1, h+max(a)):
  for j in range(n):
    dp[i] = min(dp[i], dp[i-a[j]]+b[j])
print(min(dp[h:]))

Submission status: Time Limit Exceeded

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 = [float('inf')]*(h+max(a))
dp[0] = 0 
for i in range(1, h+max(a)):
  for j in range(n):
    dp[i] = min(dp[i], dp[i-a[j]]+b[j])
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
import math

temp = input().split(' ')
hp = int(temp[0])
magic = int(temp[1])

cost_list = []
damage_list = []

for i in range(magic):
    l = list(map(int, input().split(' ')))
    damage_list.append(l[0])
    cost_list.append(l[1])
    
dp = [[float("inf")]*(hp+1)]*(magic+1)
dp[0][0] = 0

for i in range(magic):
    for j in range(hp+1):
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
        if dp[i+1][min(j+damage_list[i],hp)] > dp[i+1][j] + cost_list[i]:
            dp[i+1][min(j+damage_list[i],hp)] = dp[i+1][j] + cost_list[i]
  
print(dp[magic][hp])

Submission status: Time Limit Exceeded

Solution code:
h, n = (int(x) for x in input().split())
w = []
v = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    w.append(a)
    v.append(b)
dp = [[float('inf')] * (h) for _ in range(n + 1)]
for i in range(n):
    for j in range(h):
        if j < w[i]:
            dp[i + 1][j] = min(dp[i][j], v[i])
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - w[i]] + v[i])
print(dp[n][h - 1])

Submission status: Time Limit Exceeded

Solution code:
h,n=[int(j) for j in input().split()]
ab=[[int(j) for j in input().split()] for i in range(n)]
dp=[10**18]*(h+1)
dp[0]=0
ans=10**18
for a,b in ab:
    for i in range(h+1):
        if dp[i]!=10**18:
            if i+a<h:
                if dp[i]+b<dp[i+a]:
                    dp[i+a]=dp[i]+b
            else:
                if dp[i]+b<ans:
                    ans=dp[i]+b

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,n = map(int, input().split())
magic = []
INF = 10**8

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

dp = [[INF for j in range(h+1)] for i in range(n+1)] #体力がjのモンスターをi番目の魔法までを使って倒せる消費魔力の最小値

for i in range(n):
    for j in range(h):
        if j+1 > magic[i][0]:
            dp[i+1][j+1] = min(dp[i][j+1], dp[i][j+1-magic[i][0]] + magic[i][1], dp[i+1][j+1-magic[i][0]] + magic[i][1])
        else:
            dp[i+1][j+1] = min(dp[i][j+1], magic[i][1])
            
print(dp[n][h])

Submission status: Time Limit Exceeded

Solution code:


hp, magicNum = map(int, input().split())

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

dp = [ float('inf') for _ in range(hp + 10** 4 + 1) ]
dp[0] = 0

for i in range(hp):
    if dp[i] == float('inf'):
        continue
    for damage, cost in magics:
        x = dp[i] + cost
        if dp[i+damage] > x:
            dp[i+damage] = x

# for i in range(hp+10):
#     print(dp[i], end=' ')
#     if (i+1)%10 == 0:
#         print()
# print()


print(min(dp[hp:]))

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
INF=10**9
dp=[INF]*(h+10)
A=[list(map(int,input().split())) for i in range(n)]
dp[0]=0
for a,b in A:
  for i in range(h):
    index=min(h,i+a)
    x=dp[i]+b; y=dp[index]
    dp[index]=min(x,y)
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
h,n = map(int, input().split())
magic = []
INF = 10**12

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

dp = [[INF for j in range(h+1)] for i in range(n+1)] #体力がjのモンスターをi番目の魔法までを使って倒せる消費魔力の最小値

for i in range(n):
    for j in range(h):
        if j+1 > magic[i][0]:
            dp[i+1][j+1] = min(dp[i][j+1], dp[i][j+1-magic[i][0]] + magic[i][1], dp[i+1][j+1-magic[i][0]] + magic[i][1])
        else:
            dp[i+1][j+1] = min(dp[i][j+1], magic[i][1])
            
print(dp[n][h])

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
INF=10**9
A=[]; dp=[INF]*(h+10)
for i in range(n):
  x,y=map(int,input().split())
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h):
    index=h if i+a>h else i+a
    x=dp[i]+b; y=dp[index]
    dp[index]=y if y<x else x
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
def run():
  H, N = map(int, input().split())
  ab = [list(map(int, input().split())) for n in range(N)]
  dp = [float('inf')]*(H+1)
  for h in range(H+1):
    for n in range(N):
      a, b = ab[n]
      if h <= a:
        dp[h] = min(dp[h], b)
      else:
        dp[h] = min(dp[h], dp[h-a]+b)
  print(dp[-1])
    
if __name__ == '__main__':
    run()

Submission status: Time Limit Exceeded

Solution code:
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):
  dp[i] = min(dp[i-a]+b+ 0*max(1,2) for a,b in ls)

print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
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):
  dp[i] = min(dp[max(0,i-a)]+b for a,b in ls)

print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
inf = 10**9

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):
  m = inf
  for a,b in ls:
    tmp = dp[max(0,i-a)] + b
    m = min(m,tmp)
  dp[i] = m

print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
inf = 10**9

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 = [inf]*(h+amax)
dp[0] = 0

for i in range(1,h+amax):
  m = inf
  for a,b in ls:
    tmp = dp[max(0,i-a)] + b
    m = min(m,tmp)
  dp[i] = m

print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys

H,N = [int(i) for i in input().rstrip().split(' ')]
M = [[int(i) for i in input().rstrip().split(' ')] for _ in range(N)]

sys.setrecursionlimit(10**9)
DP = [0]*(H+1)

for x in range(1,H+1):
    DP[x] = min(DP[max(x-a,0)] + b for a,b in M)

print(DP[H])

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys

H,N = [int(i) for i in input().rstrip().split(' ')]
M = [[int(i) for i in input().rstrip().split(' ')] for _ in range(N)]
#print(*M, sep='\n') #配列開業表示の仕方
sys.setrecursionlimit(10**9)
@lru_cache(maxsize=None)
def DP(hp):
    global M
    if hp <= 0:
        return 0
    res = min([DP(hp-a)+b for a,b in M])
    return res

print(DP(H))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

dp = [0] * (H + 1)

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

print(dp[H])

Submission status: Time Limit Exceeded

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

h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
dp = [float("inf")]*(h+1)
dp[0] = 0
for i in range(n):
  a, b = AB[i]
  for j in range(h+1):
    if j <= a:
      dp[j] = min(dp[j], b)
    else:
      dp[j] = min(dp[j], dp[j-a]+b)
print(dp[h])

Submission status: Time Limit Exceeded

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

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

  for i in range(h+1):
    for j in range(n):
      if l[j][0] >= i:
        if dp[i] > l[j][1]:
          dp[i] = l[j][1]
      else:
        if dp[i] > l[j][1] + dp[i-l[j][0]]:
          dp[i] = l[j][1] + dp[i-l[j][0]]


  print(dp[h])

main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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+1):
  if dp[i] == 10 ** 8 + 1:
      continue
  for j in range(n):
    x = dp[i] + l[j][1]
    if dp[i + l[j][0]] > x:
      dp[i + l[j][0]] = x

print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
INF = 100100100

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

#dp = [[INF for i in range(h+1)] for j in range(n+1)]
dp = [INF for i in range(h+maxA+1)]
dp[0] = 0
for i in range(n) :
    for j in range(h+1) :
        dp[j+ab[i][0]] = min(dp[j+ab[i][0]], dp[j]+ab[i][1])

print(min(dp[h:]))


'''
for i in range(n) :
    for j in range(h+1) :
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][min(j+ab[i][0], h)] = min(dp[i+1][min(j+ab[i][0], h)], dp[i+1][j]+ab[i][1])
'''
#for i in range(n+1) :
#    print(dp[i])

Submission status: Time Limit Exceeded

Solution code:
def main():
  from sys import stdin
  readline = stdin.readline
  h, n = map(int, readline().split())
  l = [list(map(int, readline().split())) for i in range(n)]

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

  for i in range(h+1):
    for j in range(n):
      if l[j][0] >= i:
        if dp[i] > l[j][1]:
          dp[i] = l[j][1]
      else:
        if dp[i] > l[j][1] + dp[i-l[j][0]]:
          dp[i] = l[j][1] + dp[i-l[j][0]]

  print(dp[h])


main()

Submission status: Time Limit Exceeded

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

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

  for i in range(h+1):
    for j in range(n):
      if l[j][0] >= i:
        if dp[i] > l[j][1]:
          dp[i] = l[j][1]
      else:
        if dp[i] > l[j][1] + dp[i-l[j][0]]:
          dp[i] = l[j][1] + dp[i-l[j][0]]

  print(dp[h])


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h, n = map(int, input().split())
l = []
for i in range(n):
  a, b = map(int, input().split())
  l.append([a, b])

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

for i in range(h+1):
  for j in range(n):
    if l[j][0] >= i:
      if dp[i] > l[j][1]:
        dp[i] = l[j][1]
    else:
      if dp[i] > l[j][1] + dp[i-l[j][0]]:
        dp[i] = l[j][1] + dp[i-l[j][0]]


print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
INF = 100100100

h, n = map(int, input().split())
dp = [INF for i in range(h+1)]
dp[0] = 0

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

print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
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+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(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
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(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
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+1)]
dp[0] = 0

for i in range(h+1):
  for j in range(n):
    y = max(i-l[j][0], 0)
    if dp[i] > l[j][1] + dp[y]:
      dp[i] = l[j][1] + dp[y]


print(dp[h])

Submission status: Time Limit Exceeded

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

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

for i in range(h+1):
  for j in range(n):
    y = max(i-l[j][0], 0)
    if dp[i] > l[j][1] + dp[y]:
      dp[i] = l[j][1] + dp[y]


print(dp[h])

Submission status: Time Limit Exceeded

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

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

for i in range(h+1):
  for j in range(n):
    if dp[i] > l[j][1] + dp[max(i-l[j][0], 0)]:
      dp[i] = l[j][1] + dp[max(i-l[j][0], 0)]


print(dp[h])

Submission status: Time Limit Exceeded

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

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

for i in range(h+1):
  for j in range(n):
    if l[j][0] >= i:
      if dp[i] > l[j][1]:
        dp[i] = l[j][1]
    else:
      if dp[i] > l[j][1] + dp[i-l[j][0]]:
        dp[i] = l[j][1] + dp[i-l[j][0]]


print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
INF = 100100100

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

#dp = [[INF for i in range(h+1)] for j in range(n+1)]
dp = [INF for i in range(h+1)]
dp[0] = 0
for i in range(n) :
    for j in range(h+1) :
        ind = min(j+ab[i][0], h)
        dp[ind] = min(dp[ind], dp[j]+ab[i][1])



'''
for i in range(n) :
    for j in range(h+1) :
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][min(j+ab[i][0], h)] = min(dp[i+1][min(j+ab[i][0], h)], dp[i+1][j]+ab[i][1])
'''
#for i in range(n+1) :
#    print(dp[i])

print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools

#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

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



def main():
    h,n=map(int,input().split()) #n yen, m types
    ab=[list(map(int,input().split())) for i in range(n)]
    maxa = max(a for a, b in ab)
    dp=[INFI for i in range(h+maxa)]
    dp[0]=0


    def f(h):

        for a,b in ab:
            for j in range(h+maxa):
                dp[j]=min(dp[j],dp[j-a]+b)
        return min(dp[h:])

    print(f(h))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools

#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

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



def main():
    h,n=map(int,input().split()) #n yen, m types
    ab=[list(map(int,input().split())) for i in range(n)]

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


    def f(h):

        for a,b in ab:
            for j in range(h+1):
                if j-a<0:
                    dp[j] = min(dp[j],b)
                else:
                    dp[j]=min(dp[j],dp[j-a]+b)
        return dp[h]

    print(f(h))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools

#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

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



def main():
    h,n=map(int,input().split()) #n yen, m types
    a=[]
    b=[]
    for i in range(n):
        x,y=map(int,input().split())
        a.append(x)
        b.append(y)

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

    @lru_cache(maxsize=None)
    def f(h):

        for i in range(n):
            for j in range(h+1):
                if j-a[i]<0:
                    dp[j] = min(dp[j], dp[0] + b[i])
                else:
                    dp[j]=min(dp[j],dp[j-a[i]]+b[i])
        return dp[h]

    print(f(h))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools

#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

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


@lru_cache(maxsize=None)
def main():
    h,n=map(int,input().split()) #n yen, m types
    a=[]
    b=[]
    for i in range(n):
        x,y=map(int,input().split())
        a.append(x)
        b.append(y)

    dp=[INFI for i in range(h+1)]
    dp[0]=0
    for i in range(n):
        for j in range(h+1):
            if j-a[i]<0:
                dp[j] = min(dp[j], dp[0] + b[i])
            else:
                dp[j]=min(dp[j],dp[j-a[i]]+b[i])

    print(dp[h])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def minus(x, y):
    if x - y >= 0:
        return x - y
    else:
        return 0

[H, N] = [int(i) for i in input().split()]
mgc = [[int(i) for i in input().split()] for j in range(N)]

dp = [0]*(H+1)

for i in range(H):
    MIN = sys.maxsize
    for j in range(N):
        MIN = min(MIN, dp[minus(i+1, mgc[j][0])] + mgc[j][1])
    dp[i+1] = MIN

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
def minus(x, y):
    if x - y >= 0:
        return x - y
    else:
        return 0

[H, N] = [int(i) for i in input().split()]
mgc = [[int(i) for i in input().split()] for j in range(N)]

dp = [0]*(H+1)

for i in range(H):
    opt = [0]*N
    for j in range(N):
        opt[j] = dp[minus(i+1, mgc[j][0])] + mgc[j][1]
    dp[i+1] = min(opt)

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools

#import bisect

import copy


def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

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



def main():
    h,n=map(int,input().split()) #n yen, m types
    a=[]
    b=[]
    for i in range(n):
        x,y=map(int,input().split())
        a.append(x)
        b.append(y)

    dp=[INFI for i in range(h+1)]
    dp[0]=0
    for i in range(n):
        for j in range(len(dp)):
            if j-a[i]<0:
                dp[j] = min(dp[j], dp[0] + b[i])
            else:
                dp[j]=min(dp[j],dp[j-a[i]]+b[i])

    print(dp[h])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
H, N = [int(_) for _ in stdin.readline().rstrip().split()]
A = []
B = []

def chmin(a, b):
    if a > b:
        return b
    return a

for i in range(N):
    a, b = [int(_) for _ in stdin.readline().rstrip().split()]
    A.append(a)
    B.append(b)
dp = [float('inf')] * (H + 1)
dp[0] = 0
for i in range(N):
    for j in range(H+1):
        dp[min(j+A[i], H)] = chmin(dp[min(j+A[i], H)], dp[j]+B[i])
print(dp[H])

Submission status: Time Limit Exceeded

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 h in range(1, H+1):
    min_mp = dp[max(h - A[0],0)] + B[0]
    for n in range(1, N):
        min_mp = min(min_mp, dp[max(h - A[n],0)] + B[n])
    dp.append(min_mp)

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
HP,n = map(int,input().split())
s = [tuple(map(int,input().split())) for i in range(n)]

dp = [float('inf')]*(HP+1) #0~HP
dp[0] = 0
for damage, cost in s:
    for hp in range(HP):
        next_idx = min(hp+damage, HP)
        dp[next_idx] = min(dp[next_idx], dp[hp]+cost)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    HP,n = map(int,input().split())
    s = [tuple(map(int,input().split())) for i in range(n)]
    max_s = max(s)

    #dp[damage] := モンスターにdamageを与える最小コスト
    dp = [float('inf')]*(HP+1) #0~HP
    dp[0] = 0
    for hp in range(HP):
        for damage, cost in s:
            next_idx = min(hp+damage, HP)
            dp[next_idx] = min(dp[next_idx], dp[hp]+cost)
    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

dp = [[float('inf') for _ in range(H + max(AB)[0] + 1)] for _ in range(N + 1)]
dp[0][0] = 0
for n in range(N):
    for h in range(H + max(AB)[0] + 1):
        if h - AB[n][0] >= 0:
            dp[n + 1][h] = min(dp[n + 1][h - AB[n][0]] + AB[n][1], dp[n][h])
        else:
            dp[n + 1][h] = dp[n][h]

print(min(dp[N][H:]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

dp = [[float('inf') for _ in range(H + max(AB)[0] + 1)] for _ in range(N + 1)]
dp[0][0] = 0
for n in range(N):
    for h in range(H + max(AB)[0] + 1):
        if h - AB[n][0] >= 0:
            dp[n + 1][h] = min(dp[n + 1][h - AB[n][0]] + AB[n][1], dp[n][h])
        else:
            dp[n + 1][h] = dp[n][h]

print(min(dp[N][H:]))

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

H,N=map(int,input().split())
A_list=[]
B_list=[]
for i in range(N):
    A,B=map(int,input().split())
    A_list.append(A)
    B_list.append(B)

amax=max(A_list)

inf=float('inf')
dp=np.array([0]+[inf]*(H+amax))

for i in range(N):
    A=A_list[i]
    B=B_list[i]
    for j in range(A,1+H+amax):
        if dp[j-A]+B < dp[j]:
            dp[j]=dp[j-A]+B

    #if A > H and B < dp[-1]:
    #    dp[-1]=B
    #else:
    #    for j in range(A,1+H):
    #        if dp[j-A]+B<dp[j]:
    #            dp[j]=dp[j-A]+B
    
    #    minA=np.amin(dp[H-A:])+B
    #    if minA < dp[-1]:
    #        dp[-1]=minA

print(int(np.amin(dp[H:])))