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:
def main():
  h,n = [int(i) for i in input().split()]
  ab = []
  for i in range(n):
    a,b = [int(i) for i in input().split()]
    ab.append([a,b])
  dp = [[10**8]*((h+1)+10**4) for i in range(n+1)]
  dp[0][0]=0
  for i in range(n):
    for j in range(h+1+10**4):
      if j>=ab[i][0]:
        dp[i+1][j]=min(dp[i][j],dp[i+1][j-ab[i][0]]+ab[i][1])
      else:
        dp[i+1][j]=dp[i][j]

  ans = 10**8    
  for i in range(n+1):
    for j in range(h,h+1+10**4):
      ans = min(ans,dp[i][j])
  print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
a, b = [0], [0]
for _ in range(n):
    s, t = map(int, input().split())
    a.append(s)
    b.append(t)
dp = [[0 for _ in range(h + max(a))] for _ in range(n + 1)]
for i in range(n + 1):
    for j in range(1, h + max(a)):
        if i == 0:
            dp[i][j] = 10 ** 9
        elif a[i] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - a[i]] + b[i])
ans = 10 ** 9
for i in range(h, h + max(a)):
    if ans > dp[n][i]:
        ans = dp[n][i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import time


t = time.time()
def iip():
    return [int(i) for i in input().split()]

def main():
    H, N = iip()
    mp_for_damage = [10**9 for i in range(H+1)]
    mp_for_damage[0] = 0
    ab = []

    for i in range(N):
        ab.append(iip())

    ab= sorted(ab, key=lambda x:x[0]/x[1], reverse=True)

    for i in range(N):
        a, b = ab[i]
        for j in range(H+1):
            if a < H and mp_for_damage[a] < b:
                continue

            for k in range(1, a):
                if k > H:
                    break
                mp_for_damage[k] = min(mp_for_damage[k], b)

            if j + a > H:
                break
            mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

    #print(mp_for_damage)
    print(mp_for_damage[H])

    #print(time.time() - t)

main()

Submission status: Time Limit Exceeded

Solution code:
import math
import time

t = time.time()
def iip():
    return [int(i) for i in input().split()]

H, N = iip()
mp_for_damage = [10**9 for i in range(H+1)]
mp_for_damage[0] = 0
ab = []

for i in range(N):
    ab.append(iip())

ab= sorted(ab, key=lambda x:x[0]/x[1], reverse=True)

for i in range(N):
    a, b = ab[i]
    for j in range(H+1):
        if a < H and mp_for_damage[a] < b:
            continue

        for k in range(1, a):
            if k > H:
                break
            mp_for_damage[k] = min(mp_for_damage[k], b)

        if j + a > H:
            break
        mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

#print(mp_for_damage)
print(mp_for_damage[H])

#print(time.time() - t)

Submission status: Time Limit Exceeded

Solution code:
import math
import time

t = time.time()
def iip():
    return [int(i) for i in input().split()]

H, N = iip()
mp_for_damage = [10**9 for i in range(H+1)]
mp_for_damage[0] = 0
ab = []

for i in range(N):
    ab.append(iip())

ab= sorted(ab, key=lambda x:x[0], reverse=True)

for i in range(N):
    a, b = ab[i]
    for j in range(H+1):
        if a < H and mp_for_damage[a] < b:
            continue

        for k in range(1, a):
            if k > H:
                break
            mp_for_damage[k] = min(mp_for_damage[k], b)

        if j + a > H:
            break
        mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

#print(mp_for_damage)
print(mp_for_damage[H])

#print(time.time() - t)

Submission status: Time Limit Exceeded

Solution code:
import math
import time

t = time.time()
def iip():
    return [int(i) for i in input().split()]

H, N = iip()
mp_for_damage = [10**9 for i in range(H+1)]
mp_for_damage[0] = 0
ab = []

for i in range(N):
    ab.append(iip())

ab= sorted(ab, key=lambda x:x[1], reverse=True)

for i in range(N):
    a, b = ab[i]
    for j in range(H+1):
        if a < H and mp_for_damage[a] < b:
            continue

        for k in range(1, a):
            if k > H:
                break
            mp_for_damage[k] = min(mp_for_damage[k], b)

        if j + a > H:
            break
        mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

#print(mp_for_damage)
print(mp_for_damage[H])

#print(time.time() - t)

Submission status: Time Limit Exceeded

Solution code:
import math
import time

t = time.time()
def iip():
    return [int(i) for i in input().split()]

H, N = iip()
mp_for_damage = [10**9 for i in range(H+1)]
mp_for_damage[0] = 0
ab = []

for i in range(N):
    ab.append(iip())

ab= sorted(ab, key=lambda x:x[1])

for i in range(N):
    a, b = ab[i]
    for j in range(H+1):
        if a < H and mp_for_damage[a] < b:
            continue

        for k in range(1, a):
            if k > H:
                break
            mp_for_damage[k] = min(mp_for_damage[k], b)

        if j + a > H:
            break
        mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

#print(mp_for_damage)
print(mp_for_damage[H])

#print(time.time() - t)

Submission status: Time Limit Exceeded

Solution code:
import math
import time

t = time.time()
def iip():
    return [int(i) for i in input().split()]

H, N = iip()
mp_for_damage = [10**9 for i in range(H+1)]
mp_for_damage[0] = 0

for i in range(N):
    a, b = iip()
    for j in range(H+1):
        if a < H and mp_for_damage[a] < b:
            continue

        for k in range(1, a):
            if k > H:
                break
            mp_for_damage[k] = min(mp_for_damage[k], b)

        if j + a > H:
            break
        mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

#print(mp_for_damage)
print(mp_for_damage[H])

#print(time.time() - t)

Submission status: Time Limit Exceeded

Solution code:
import math
import time

t = time.time()
def iip():
    return [int(i) for i in input().split()]

H, N = iip()
mp_for_damage = [10**9 for i in range(H+1)]
mp_for_damage[0] = 0

for i in range(N):
    a, b = iip()
    for j in range(H+1):
        for k in range(1, a):
            if k > H:
                break
            mp_for_damage[k] = min(mp_for_damage[k], b)

        if j + a > H:
            break
        mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

#print(mp_for_damage)
print(mp_for_damage[H])

#print(time.time() - t)

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

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

for i in range(n):
    for j in range(h+1)[::-1]:
        if dp[j] != -1:
            for k in range((h-j)//a[i] + 1):
                dj = a[i] * (k+1)
                if j + dj >= h :
                    nj = h
                else:
                    nj = j+dj
                if dp[nj] == -1:
                    dp[nj] = dp[j] + b[i]*(k+1)
                    continue
                dp[nj] = min(dp[nj],dp[j] + b[i]*(k+1))
print(dp[h])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# 1-index
from sys import stdin
H, N = [int(x) for x in stdin.readline().rstrip().split()]

data = [0]*N

for i in range(N):
    A, B = [int(x) for x in stdin.readline().rstrip().split()]
    data[i] = (A, B)
dp = [10**9]*(H+1)
dp[0] = 0

for h in range(0,H+1):
    for a,b in data:
        if h+a >= H:
            dp[H] = min(dp[h]+b,dp[H])
        else:
            dp[h+a] = min(dp[h]+b,dp[h+a])
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
hp,m=map(int,input().split())
l=[list(map(int,input().split())) for  i in range(m)]
dp=[10**9 for i in range(hp+1)]
dp[0]=0
for i in range(hp+1):
  for at,mp in l:
    dp[i]=min(dp[i],mp+(0 if i-at<0 else dp[i-at]))
print(dp[hp])

Submission status: Time Limit Exceeded

Solution code:
H,N=map(int,input().split())
dp = [10**10]*(H+1)
dp[0]=0
for _ in range(N):
    A,B=map(int,input().split())
    for idx in range(H):
        nidx = min(idx+A,H)
        dp[nidx]=min(dp[nidx],dp[idx]+B)
print(dp[-1])

Submission status: Time Limit Exceeded

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

dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        temp = i - a
        if temp < 0:
            temp = 0
        need_magic = dp[temp] + b
        if need_magic < dp[i]:
            dp[i] = need_magic
        # dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        # print(i, j, a, b, dp)
print(dp[-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    mp = [0] * (H + 1)
    for i in range(1, len(mp)):
        ml = [0 for j in range(N)]
        for j in range(N):
            if i - A[j] < 0:
                ml[j] = mp[0] + B[j]
            else:
                ml[j] = mp[i - A[j]] + B[j]
        mp[i] = min(ml)
    print(mp[-1])   


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
###二次元DP
# dp = [[0] * (h + 1) for i in range(n+1)]
# for i in range(n):
#     for j in range(h+1):
#         a = ab[i][0]
#         b = ab[i][1]
#         # print(i, j)
#         if i == 0:
#             if j <= a and j > 0:
#                 dp[i+1][j] = b
#             elif j > a:
#                 dp[i+1][j] = dp[i+1][j-a] + b
#         else:
#             if j <= a:
#                 dp[i+1][j] = min(dp[i][j], b)
#             else:
#                 dp[i+1][j] = min(dp[i][j], dp[i+1][j-a] + b)
# # for i in dp:
# #     print(i)
# print(dp[-1][-1])

#一次元DP
dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        # print(i, j, a, b, dp)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from collections import defaultdict

def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    MAX = 10**16
    minCurrent = defaultdict(lambda :MAX)
    minCurrent[0] = 0
    currentPos = [0]
    heapq.heapify(currentPos)
    visited = set()
    while len(currentPos) > 0:
        cp = heapq.heappop(currentPos)
        if cp in visited:
            continue
        if cp > H:
            break
        visited.add(cp)
        cc = minCurrent[cp]
        for i in range(N):
            heapq.heappush(currentPos, cp + A[i])
            minCurrent[cp + A[i]] = min(minCurrent[cp + A[i]],cc+B[i])
    c = MAX
    for key in minCurrent:
        if key >=H:
            c = min(c,minCurrent[key])
    print(c)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Time Limit Exceeded

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


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    mp = [0] * (H + 1)
    for i in range(1, len(mp)):
        ml = []
        for j in range(N):
            if i - A[j] < 0:
                ml.append(mp[0] + B[j])
            else:
                ml.append(mp[i - A[j]] + B[j])
        mp[i] = min(ml)
    print(mp[-1])   


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Time Limit Exceeded

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


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    mp = [0] * (H + 1)
    for i in range(1, len(mp)):
        m = 10 ** 9
        for j in range(N):
            if i - A[j] < 0:
                m = min(m, mp[0] + B[j])
            else:
                m = min(m, mp[i - A[j]] + B[j])
        mp[i] = m
    print(mp[-1])   


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Time Limit Exceeded

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

max_A=max(AB)[0]+h
DP=[float("inf")]*max_A
DP[0]=0

for i in range(h):
    for a,b in AB:
        DP[i+a]=min(DP[i+a],DP[i]+b)

print(min(DP[h:]))

Submission status: Time Limit Exceeded

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)

dp = [1e9]*(H+max(A))
dp[0] = 0
for h in range(H):
  for n in range(N):
    dp[h+A[n]] = min(dp[h+A[n]], dp[h]+B[n])
print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
#一次元DP
dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        if i <= a:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i-a] + b)
        # print(i, j, a, b, dp)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
dp = [[0] * (h + 1) for i in range(n+1)]
for i in range(n):
    for j in range(h+1):
        a = ab[i][0]
        b = ab[i][1]
        # print(i, j)
        if i == 0:
            if j <= a and j > 0:
                dp[i+1][j] = b
            elif j > a:
                dp[i+1][j] = dp[i+1][j-a] + b
        else:
            if j <= a:
                dp[i+1][j] = min(dp[i][j], b)
            else:
                dp[i+1][j] = min(dp[i][j], dp[i+1][j-a] + b)
# for i in dp:
#     print(i)
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    monster_health, spells = map(int, input().split())
    attack = []
    damage = []
    for _ in range(spells):
        a, b = map(int, input().split())
        attack.append(a)
        damage.append(b)
    dp = [[float("inf") for _ in range(monster_health + 1)] for _ in range(spells + 1)]
    dp[0][0] = 0
    for i in range(1, spells + 1):
        for j in range(monster_health + 1):
            ind = min(j + attack[i - 1], monster_health)
            dp[i][j] = min(dp[i][j], dp[i - 1][j])
            dp[i][ind] = min(dp[i][ind], dp[i][j] + damage[i - 1])
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import numpy as np
  


for n in range(N):
  a,b=map(int, input().split())
  A.append(a)
  B.append(b)

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

Submission status: Time Limit Exceeded

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

length=h+max(AB)[0]
DP=[float("inf")]*length
DP[0]=0

for i in range(h):
    for a,b in AB:
        DP[i+a]=min(DP[i+a],DP[i]+b)

print(min(DP[h:]))

Submission status: Time Limit Exceeded

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

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

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

print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
INF=10**12
a=[]
b=[]
for i in range(n):
    A,B=map(int,input().split())
    a.append(A)
    b.append(B)
dp=[INF]*20010
dp[0]=0
for i in range(20010):
    for j in range(n):
        if i>=a[j]:
            dp[i]=min(dp[i],dp[i-a[j]]+b[j])
ans=min(dp[h:])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
INF=10**15
a=[]
b=[]
for i in range(n):
    A,B=map(int,input().split())
    a.append(A)
    b.append(B)
dp=[INF]*20010
dp[0]=0
for i in range(20010):
    for j in range(n):
        if i>=a[j]:
            dp[i]=min(dp[i],dp[i-a[j]]+b[j])
ans=min(dp[h:])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
# mod = 10**9 + 7

# n = int(input())
h, n = map(int, input().split())
# a = list(map(int, input().split()))
a, b = [0] * n, [0] * n

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

dp = [10**9+7] * (h+1)
dp[0] = 0

for i in range(n):

    for j in range(h):

        dp[min(j+a[i], h)] = min(dp[min(j+a[i],h)], dp[j]+b[i])


print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
# mod = 10**9 + 7

# n = int(input())
h, n = map(int, input().split())
# a = list(map(int, input().split()))
a, b = [0] * n, [0] * n

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

dp = [float('inf')] * (h+1)
dp[0] = 0

for i in range(n):

    for j in range(h):

        dp[min(j+a[i], h)] = min(dp[min(j+a[i],h)], dp[j]+b[i])


print(dp[h])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(N):
    data.append([0, 0])
    a, b = map(int,input().split())
    data[i][0] = a
    data[i][1] = b
data.sort(key=lambda x: x[0])
cost = [float("inf")] * (H + data[-1][0])
cost[0] = 0
for i in range(1, H + data[-1][0]):
    for magic in data:
        if i < magic[0]:
            break
        if cost[i] > cost[i - magic[0]] + magic[1]:
            cost[i] = cost[i - magic[0]] + magic[1]
print(min(cost[H:]))

Submission status: Time Limit Exceeded

Solution code:
"""
dp[与えたダメージ] = 使用した魔力
"""
h, n = map(int, input().split())
attacks = []
INF = 10000000000000
dp = [INF for _ in range(h + 1)]
dp[0] = 0
for i in range(n):
    a, b = map(int, input().split())
    attacks.append([a, b])
for i in range(h):
    for j in range(n):
        dp[min(h,i + attacks[j][0])] = min(dp[min(h, i + attacks[j][0])], dp[i] + attacks[j][1])
print(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())

def battle(hp,magic=0):
  #print(hp,magic)
  if hp==0:
    return magic
  min_power = min([DP[max(hp-A[i],0)]+B[i] for i in range(N)])
  return magic+min_power

DP = [0]*(H+1)
for i in range(H+1):
  DP[i] = battle(i)
  #print(DP[i])
ans = DP[H]
print(ans)

#print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

dp = [10**9 for _ in range(h+1)]
dp[0] = 0
for i in range(1, h+1):
    for a, b in ab:
        if a < i:
            dp[i] = min(dp[i], dp[i-a]+b)
        else:
            dp[i] = min(dp[i], b)
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [-1 for _ in range(h+1)]
dp[0] = 0
for i in range(1,h+1):
    dp[i] = min([dp[max(0, i-pw)]+ma for pw, ma in ab])
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [10**5 for _ in range(h+1)]
dp[0] = 0
for i in range(1,h+1):
    dp[i] = min([dp[max(0, i-pw)]+ma for pw, ma in ab])
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,n=LI()
  w=[]
  v=[]
  for _ in range(n):
    _w,_v=LI()
    w.append(_w)
    v.append(_v)

  dp=[[inf]*(h+10**4+1) for _ in range(n+1)]
  dp[0][0]=0
  for i in range(n):
    for j in range(h+10**4):
      if j<w[i]:
        dp[i+1][j]=dp[i][j]
      else:
        dp[i+1][j]=min(dp[i][j],dp[i+1][j-w[i]]+v[i])
  ans=inf
  for i in range(n+1):
    for j in range(h,h+10**4):
      ans=min(ans,dp[i][j])

  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A, B = [0]*N, [0]*N

for i in range(N):
	A[i], B[i] = MAP()

max_A = max(A)
dp = [INF]*(H+max_A+1)
dp[0] = 0
for i in range(N):
	for j in range(A[i], H+max_A+1):
		dp[j] = min(dp[j], dp[j-A[i]]+B[i])

print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A, B = [0]*N, [0]*N

for i in range(N):
	A[i], B[i] = MAP()

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

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

Submission status: Time Limit Exceeded

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

ml = magicL
dp = [10**9 for i in range(H +1)]
dp [0] = 0
for i in range(N):
    for w in range(H +1):
        dp[min(w+ml[i][0],H)] = min(dp[min(w+ml[i][0],H)],dp[w]+ml[i][1])
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:

H,N = map(int,input().split())
magicL =[]
for x in range(N):
    magic = list(int(i) for i in input().split())
    magicL.append(magic)
magicE = []
for x in range(N):
    magicE.append(magicL[x][0]/magicL[x][1])
c = list(zip(magicE,magicL))
mel , ml = zip(*c)
dp =[[10000000000 for x in range(N+1)]for y in range(H+1)]
dp[0][0] = 0
for i in range(len(dp[0])-1):
    for w in range(H+1):
        dp[w][i+1] = min(dp[w][i],dp[w][i+1])
        dp[min(w+ml[i][0],H)][i+1] = min(dp[min(w+ml[i][0],H)][i+1],dp[w][i+1]+ml[i][1])
print(dp[H][N])

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
inf = 10**11

# dp[i]: 体力iを減らす魔力の最小値
dp = [inf] * 20000
dp[0] = 0

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

print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
inf = 1000000000
dp = [inf] * 20000

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

amax = 0
dp[0] = 0
for j in range(n):
    a, b = map(int, input().split())

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

print(min(dp[h:h+amax]))

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[10**9]*(h+max(l)[0])
dp[0]=0
for i in range(1,len(dp)):
  for a,b in l:
    if i-a>=0:
      dp[i]=min(dp[i],dp[i-a]+b)
print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

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

inf = 10 ** 9
max_h = 2 * 10**4 + 10
dp = [inf] * max_h
dp[0] = 0
for a, b in ab:
    for i in range(max_h - a + 1):
        dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[h:]))

Submission status: Time Limit Exceeded

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

inf = 10 ** 9
max_h = 2 * 10**4 + 10
dp = [inf] * max_h
dp[0] = 0
for a, b in ab:
    for i in range(max_h - a + 1):
        dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[h:]))