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

Solution code:
# ABC153 E Crested Ibis vs Monster
f=lambda:map(int,input().split())
H,N=f()
# dp[n][h]:=nthまでで体力をh削るときの最小魔力
INF=10**9
dp=[[INF]*(H+1) for _ in [0]*(N+1)]

for i in range(N+1):
    if i!=0:
        a,b=f()
    else:
        a,b=0,0
    for j in range(H+1):
        if i==0:
            if j==0:
                dp[i][j]=0
            else:
                dp[i][j]=INF
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][max(j-a,0)]+b)

print(dp[N][H])

Submission status: Time Limit Exceeded

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

lld = [(v,k) for k, v in d.items()]
ld = [(v,k) for (k, v) in sorted(lld)[::-1]]
len_d = len(ld)
memo = {}
ans = 99999999999999999999999999
def f(index, current, damage):
  global ans
  if memo.get(current, 0) > damage or current >= ans:
    return
  memo[current] = damage
  if damage >= h:
    ans = min(ans, current)
  else:
    for i in range(index, len_d):
      f(i, current+ld[i][0], damage+ld[i][1])

f(0, 0, 0)
print(ans)

Submission status: Time Limit Exceeded

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 = {}
ans = 99999999999999999999999999
def f(index, current, damage):
  global ans
  if memo.get(current, 0) > damage or current > ans:
    return
  memo[current] = damage
  if damage >= h:
    ans = min(ans, current)
  else:
    for i in range(index, len_d):
      f(i, current+ld[i][0], damage+ld[i][1])

f(0, 0, 0)
print(ans)

Submission status: Time Limit Exceeded

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 = {}
ans = 99999999999999999999999999
def f(index, current, damage):
  global ans
  if memo.get(current, 0) > damage:
    return
  memo[current] = damage
  if damage >= h:
    ans = min(ans, current)
  else:
    for i in range(index, len_d):
      f(i, current+ld[i][0], damage+ld[i][1])

f(0, 0, 0)
print(ans)

Submission status: Time Limit Exceeded

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):
  if memo.get(current, 0) > damage:
    return
  memo[current] = damage
  if damage < h:
    for i in range(index, len_d):
      f(i, current+ld[i][0], damage+ld[i][1])

f(0, 0, 0)
for k in sorted(memo):
  if memo[k] >= h:
    print(k)
    exit()

Submission status: Time Limit Exceeded

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

Solution code:
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [0] + [10000000000] * h
ret = 10000000000
for i in range(h):
    for j in range(n):
        a, b = ab[j]
        if i + a >= h:
            ret = min(ret, dp[i] + b)
        else:
            dp[i + a] = min(dp[i + a], dp[i] + b)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import math
H, N = map(int, input().split())
dp = [[0 for _ in range(H + 1)] for _ in range(N)]
A, B = map(int, input().split())
for i in range(H + 1):
    cnt = math.ceil(i / A)
    dp[0][i] = B * cnt

for i in range(1, N):
    A, B = map(int, input().split())
    for j in range(H + 1):
        dp[i][j] = min(dp[i - 1][j], dp[i][max(j - A, 0)] + B)
# print(*dp, sep='\n')
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

#dpテーブル　dp[i+1][j]=i番目までの魔法を用いて体力をj以上減らす時の消耗の最小値
dp=[[float("INF") for i in range(h+1)] for j in range(n+1)]
#初期条件
dp[0][0]=0
for i in range(n):
  for j in range(h+1):
    #i番目の魔法を使わない時
    if a[i]>j:
      dp[i+1][j]=min(dp[i][j],dp[i+1][0]+b[i])
    else:
      dp[i+1][j]=min(dp[i][j],dp[i+1][j-a[i]]+b[i])

print(dp[n][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 = [0]*20001

for i in range(1, h + 1):
    ref = 10**10
    for a, b in l:
        temp = dp[i - a] + b
        ref = min(ref, temp)
    dp[i] = ref

print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
a=[]
b=[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa)
  b.append(bb)
inf=10**10
f=h+max(a)+1
dp=[f*[inf]for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  dp[i]=dp[i-1]
  for j in range(f):
    if j+a[i-1]<f:
      dp[i][j+a[i-1]]=min(dp[i][j+a[i-1]],dp[i][j]+b[i-1])
  for j in range(f-1,0,-1):
    dp[i][j-1]=min(dp[i][j-1],dp[i][j])
print(dp[-1][h])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np

H,N = map(int, input().split())
M = [list(map(int, stdin.readline().split())) for i in [0]*N]
M = np.array(M)

def main(h,n,m):
    dp = [10**8+1]*(10**4+1)
    dp = np.array(dp)
    dp[0] = 0

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

    print(dp[h])

if __name__=="__main__":
    main(H,N,M)

Submission status: Time Limit Exceeded

Solution code:
import math

H, N = list(map(int, input().split()))
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = list(map(int, input().split()))

dp = [0]*(H+1)

dp[0] = 0

for i in range(1,H+1):
    dp_min = math.inf
    for j in range(N):
        dp_min = min(dp_min, dp[max(0,i-A[j])] + B[j])
    dp[i] = dp_min

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:


def read_input():
    h, n = map(int, input().split())
    magic = {}
    for i in range(n):
        a, b = map(int, input().split())
        magic[i] = (a, b)

    return h, n, magic


def submit():
    h, n, magic = read_input()

    dp = [float('inf') for _ in range(h + 1)]
    dp[h] = 0

    for i in reversed(range(1, h + 1)):
        for a, b in magic.values():
            # 更新する
            # max(0, i - a)のHPにより少ない魔力消費量で行き着ければ更新する
            rest = max(0, i - a)
            if dp[rest] > dp[i] + b:
                dp[rest] = dp[i] + b

    print(dp[0])


submit()

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, b = list(map(int, input().split()))
  A[i] = a
  B[i] = b
  
#モンスターの体力を i 減らすため消耗する魔力の最小値  
DP = [float("inf")] * (H + max(A) + 1)
DP[0] = 0  
for i in range(len(DP)):
  for j in range(N):
    if i - A[j] >= 0:
      DP[i] = min(DP[i], DP[i - A[j]] + B[j])
#print(DP) 
print(min(DP[H:H + max(A) + 1]))

Submission status: Time Limit Exceeded

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

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

for n in range(1, N + 1):
    a, b = map(int, input().split())
    for h in range(1, H + 1):
        tmp_min = dp[n - 1][h]
        i = 1
        while True:
            if h - i * a <= 0:
                tmp_min = min(tmp_min, dp[n - 1][0] + i * b)
                break
            tmp_min = min(tmp_min, dp[n - 1][h - i * a] + i * b)
            i += 1
        dp[n][h] = tmp_min

print(dp[N][H])

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
magic=[list(map(int,input().split())) for _ in range(n)]
dp=[10**9]*(h+10**5)
#dp[i]:敵の体力をi減らすのに必要な魔力の最小値
dp[0]=0
for i in range(h):
    for damage,cost in magic:
        dp[i+damage]=min(dp[i+damage],dp[i]+cost)
ans=10**9
for i in range(10**5):
    ans=min(ans,dp[i+h])
print(ans)

Submission status: Time Limit Exceeded

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

# dp[damage] := モンスターに damage を与えるために必要な最小コスト

# damage = 0,1,2,...,H
dp = [10**9] * (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)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    h, n = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    dp = [[float("inf")]*(2*10**4+1) for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        p, a, b = i+1, arr[i][0], arr[i][1]
        for j in range(2*10**4+1):
            if j < a:
                dp[p][j] = dp[p-1][j]
            else:
                if dp[p][j-a] + b < dp[p-1][j]:
                    dp[p][j] = dp[p][j-a] + b
                else:
                    dp[p][j] = dp[p-1][j]
    print(min(dp[-1][h:2*10**4+1]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
(h, n), *m = [[*map(int, i.split())] for i in open(0)]
dp = [0] + [10**9] * h
for i in range(1, h + 1):
    dp[i] = min(dp[max(i - a, 0)] + b for a, b in m)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import islice


def resolve(in_):
    H, N = map(int, next(in_).split())
    AB = tuple(tuple(map(int, line.split())) for line in islice(in_, N))
    
    dp = [1 << 31] * (H + 1)
    dp[0] = 0

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

    return dp[H]


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

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 = [99999999999]*(H+1)
dp[0]=0
for h in range(H):
  for i in range(N):
    dp[min(H,h+A[i])]=min(dp[h] + B[i], dp[min(H,h+A[i])])
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,N=map(int,input().split())
A=np.array([0]*N)
B=np.array([0]*N)
for i in range(N):
  A[i],B[i]=map(int,input().split())
dp = [np.inf]*(H+1)
dp[0]=0
for h in range(H):
  for i in range(N):
    dp[min(H,h+A[i])]=min(dp[h] + B[i], dp[min(H,h+A[i])])
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

H, N = map(int, input().split())
A = [0] * N
B = [0] * N

for i in range(N):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    A[i] = a
    B[i] = b

max_A = max(A)
INF = 10**18
dp = [INF] * (H + max_A)
dp[0] = 0

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

print(min(dp[H:H + max_A]))

Submission status: Time Limit Exceeded

Solution code:
import sys

H, N = map(int, input().split())
A = [0] * N
B = [0] * N

for i in range(N):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    A[i] = a
    B[i] = b

max_A = max(A)
INF = 10**18
dp = [INF] * (H + max_A)
dp[0] = 0

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

print(min(dp[H:H + max_A]))

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    input = sys.stdin.buffer.readline
    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())
    max_a = max(a)
    # dp[j]:jダメージ与える魔力の最小値
    dp = [1e9] * (h + max_a + 1)
    dp[0] = 0
    for i in range(n):
        for j in range(1, h + max_a + 1):
            dp[j] = min(dp[j], dp[max(j - a[i], 0)] + b[i])
    print(min(dp[h:]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    input = sys.stdin.buffer.readline
    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())
    max_a = max(a)
    # dp[j]:jダメージ与える魔力の最小値
    dp = [1e9] * (h + max_a + 1)
    dp[0] = 0
    for i in range(n):
        for j in range(1, h + max_a + 1):
            dp[j] = min(dp[j], min(dp[max(j - a[i], 0) : j]) + b[i])
    print(min(dp[h:]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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=[np.inf]*(H+1)
dp[0]=0
for h in range(H):
  for i in range(N):
    dp[min(H,h+A[i])]=min(dp[h] + B[i], dp[min(H,h+A[i])])
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main():
    H, N = map(int, input().split())
    AB = [None] * N
    for i in range(N):
        AB[i] = tuple(map(int, input().split()))

    INF = 10 ** 18
    dp = [INF] * (H + 1)
    dp[0] = 0
    for A, B in AB:
        for d in range(H + 1):
            if d < A:
                dp[d] = min(dp[d], B)
            else:
                dp[d] = min(dp[d], dp[d - A] + B)

    ans = dp[-1]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H,N =[int(i) for i in input().split()]
AAA = []
BBB = []
for i in range(N):
    buff = [int(i) for i in input().split()]
    AAA.append(buff[0])
    BBB.append(buff[1])

#dp[i]は体力をi減らすまでに必要な魔力の最小値
dp = [10000000000 for i in range(H+5)]
dp[0] = 0
for i in range(H+5):
    for j in range(N):
        A = AAA[j]
        B = BBB[j]
        if i-A>=0:
            dp[i]=min(dp[i],dp[i-A]+B)
        else:
            dp[i]=min(dp[i],B)

#print(dp)
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
H, N = map(int, input().split(' '))
nums = [float('inf') for _ in range(H+1)]
nums[0] = 0

for _ in range(N):
    a, b = map(int, input().split(' '))
    for i in range(H + 1):
        j = min(H, i+a)
        nums[j] = min(nums[j], nums[i] + b)

print(nums[H])

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

H,N=list(map(int,input().split()))
AB = []
amax = 0
for _ in range(N):
    a,b=map(int,input().split())
    amax = max(amax,a)
    AB.append([a,b])
HN = [float('inf')]*(H+amax+1)
HN[0] = 0
for i in range(H+amax+1):
    for j in range(N):
        if AB[j][0]<=i:
            tmp = HN[i-AB[j][0]]+AB[j][1]
            HN[i] = min(HN[i],tmp)
        else:
            tmp = AB[j][1]
            HN[i] = min(HN[i],tmp)
print(min(HN[H:]))

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
inf=10**9
dp=[inf]*(h+10**5)
dp[0]=0
#dp[i]=モンスターの体力をi減らすのに魔力が最低でいくつ必要か
for i in range(h):
    for a,b in l:
        dp[i+a]=min(dp[i+a],dp[i]+b)
ans=10**9
for i in range(10**5):
    ans=min(ans,dp[i+h])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,n = map(int,input().split())
p = []
inf = 10**9
for i in range(n):
    a,b = map(int,input().split())
    p.append([a,b])
m = [[0 for i in range(h)]for i in range(n+1)]
for i in range(n+1):
    for j in range(h):
        m[i][j] = inf
for i in range(n):
    for j in range(h):
        if p[i][0] >= j+1:
            m[i+1][j] = min(m[i][j],p[i][1])
        else:
            m[i+1][j] = min(m[i][j],m[i+1][j-p[i][0]]+p[i][1])
print(m[n][h-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()

    h, n = map(int, input().split())
    a = [0]*h
    b = [0]*h
    for i in range(n):
        a[i], b[i] = map(int, input().split())
    inf = 10 ** 9
    dp = [inf]*(h+1)
    dp[0]= 0
    for i in range(h):
        for j in range(n):
            idx = min(h, i+a[j])
            dp[idx] = min(dp[idx], dp[i]+b[j])
    print(dp[h])
            


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,n = map(int,input().split())
spel = [list(map(int,input().split())) for i in range(n)]
dp = [float('inf')]*(h+1)
dp[0] = 0
for i in range(h):
  for damage,cost in spel:
    n_i = min(i+damage,h)
    dp[n_i] = min(dp[n_i],dp[i]+cost)
print(dp[h])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

for k in range(N):
  magic[k] = list(map(int, input().split()))
  magic[k].append(magic[k][0]/magic[k][1])

magic.sort(key = lambda x: x[2], reverse=True)
ans = [0 for _ in range(H+1)]
visited = [0]
anskouho = []

def solve(start, power, point, maryoku):
  if start >= H:
    anskouho.append(point)
    visited.sort(reverse=True)
    return 0
  elif ans[start] != 0:
    visited.sort(reverse=True)
    return 0
  else:
    visited.append(start)
    ans[start] = point
    solve(start+power, power, point+maryoku, maryoku)

for k in range(N):
  for item in visited:
    solve(item+magic[k][0], magic[k][0], ans[item] + magic[k][1], magic[k][1])

print(min(anskouho))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

for k in range(N):
  magic[k] = list(map(int, input().split()))
  magic[k].append(magic[k][0]/magic[k][1])

magic.sort(key = lambda x: x[2], reverse=True)
ans = [0 for _ in range(H+1)]
visited = [0]
anskouho = []

def solve(start, power, point, maryoku):
  if start >= H:
    anskouho.append(point)
    visited.sort(reverse=True)
    return 0
  elif ans[start] != 0:
    visited.sort(reverse=True)
    return 0
  else:
    visited.append(start)
    ans[start] = point
    solve(start+power, power, point+maryoku, maryoku)

for k in range(N):
  for item in visited:
    solve(item+magic[k][0], magic[k][0], ans[item] + magic[k][1], magic[k][1])

print(min(anskouho))

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(n)]
hls = [0]
for i in range(h + max(magic, key = lambda x:x[0])[0]):
    pre = []
    for j in range(n):
        hres = i + 1 - magic[j][0]
        if hres >= 0:
            pre.append(hls[hres] + magic[j][1])
        else:
            pre.append(magic[j][1])
    hls.append(min(pre))
print(min(hls[h:]))

Submission status: Time Limit Exceeded

Solution code:
#

import sys
input=sys.stdin.readline
MOD=10**9+7

def main():
    H,N=map(int,input().split())
    AB=[list(map(int,input().split())) for i in range(N)]
    dp=[10**9]*(H+1+10**4)
    dp[0]=0
    for i in range(H+10**4):
        for j in range(N):
            if 0<=i+AB[j][0]<=H+10**4:
                dp[i+AB[j][0]]=min(dp[i+AB[j][0]],dp[i]+AB[j][1])
    ans=10**9
    for i in range(H,H+1+10**4):
        ans=min(ans,dp[i])
    print(ans)
    
        
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

dp = [ float( "Inf" ) ] * ( h + 1 )
# dp[ d ] = dを与える最小マナ
dp[ 0 ] = 0
for i in range( h ):
    for j in range( n ):
        update_index = min( i + a[ j ], h )
        dp[ update_index ] = min( dp[ update_index ], dp[ i ] + b[ j ] )

print( dp[ h ] )

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
H, N=map(int, input().split())
dp=[0]+[float('inf') for _ in range(2*10**4)]
for _ in range(N):
  a, b=map(int, input().split())
  for i in range(a, H+a):
    dp[i]=min(dp[i-a]+b, dp[i])
    
print(min(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=[0]+[float('inf') for _ in range(2*10**4)]
for a, b in AB:
  for i in range(a, H+a):
    dp[i]=min(dp[i-a]+b, dp[i])
    
print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = 10**9

# 個数制限なしナップザック問題
h,n = map(int, input().split())

# 二次元配列で
a,b = [],[]
for i in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

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

# 一次元配列で
# dp = [INF]*(h+1)
# dp[0] = 0
# for i in range(n):
#     a,b = map(int, input().split())
#     for j in range(h):
#         nj = min(a+j, h)
#         dp[nj] = min(dp[nj], dp[j]+b)
# print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,comb,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, n = MAP()
a = [0]*n
b = [0]*n
dp = [inf]*(h+1)
dp[0] = 0
# dp[j]: ダメージ>=jとするために必要な魔力の最小値

for i in range(n):
    a[i], b[i] = MAP()

for i in range(n):
    for j in range(0,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())
list_AB = [ list(map(int,input().split(" "))) for _ in range(n)]
dp = [pow(10, 8)] * (h+1)
dp[0] = 0

for atk, mp in list_AB:
    for j in range(h+1):
        dp[min(j+atk, h)] = min(dp[min(j+atk, h)], dp[j] + mp)

print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    h,n=map(int, input().split())
    ab=[list(map(int, input().split())) for i in range(n)]
    ans=[0]*(h+1)
    for i in range(1,h+1):
        li = [ans[max(i-j[0],0)]+j[1] for j in ab]
        ans[i]=min(li)
    print(ans[h])

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
h,n=[int(x) for x in stdin.readline().rstrip().split()]
ab=[]
for i in range(n):
    ab.append([int(x) for x in stdin.readline().rstrip().split()])

ans=[0]*(h+1)
for i in range(1,h+1):
    li = [ans[max(i-j[0],0)]+j[1] for j in ab]
    ans[i]=min(li)

print(ans[h])

Submission status: Time Limit Exceeded

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

ans=[0]*(h+1)
for i in range(1,h+1):
    li = [ans[max(i-j[0],0)]+j[1] for j in ab]
    ans[i]=min(li)

print(ans[h])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [10**9] * (H + 1)
dp[0] = 0
for i in range(H + 1):
    for a, b in ab:
        if i - a < 0:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i - a] + 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 = [0] * (H + 1 + 10**4)
for i in range(1, H + 1):
    dp[i] = 10 ** 9
for i in range(H + 1):
    for a, b in ab:
        dp[i] = min(dp[i], dp[i - a] + b)
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
damage = [0 for _ in range(n)]
use = [0 for _ in range(n)]
for i in range(n) :
    a, b = map(int, input().split())
    damage[i] = a
    use[i] = b

DP = [1<<30 for _ in range(h + 1)]
DP[0] = 0
for i in range(1, h + 1) :
    for j in range(n) :
        if i >= damage[j] :
            DP[i] = min(DP[i], (DP[i - damage[j]] + use[j]))
        else :
            DP[i] = min(DP[i], use[j])

print(DP[h])

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
damage = [0 for _ in range(n)]
use = [0 for _ in range(n)]
for i in range(n) :
    a, b = map(int, input().split())
    damage[i] = a
    use[i] = b

DP = [1<<30 for _ in range(h + 1)]
DP[0] = 0
for i in range(1, h + 1) :
    for j in range(n) :
        if i >= damage[j] :
            if DP[i] > (DP[i - damage[j]] + use[j]) :
                DP[i] = DP[i - damage[j]] + use[j]
        else :
            if DP[i] > use[j] :
                DP[i] = use[j]

print(DP[h])

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
damage = [0 for _ in range(n)]
use = [0 for _ in range(n)]
for i in range(n) :
    a, b = map(int, input().split())
    damage[i] = a
    use[i] = b

DP = [1<<60 for _ in range(h + 1)]
DP[0] = 0
for i in range(1, h + 1) :
    for j in range(n) :
        if i >= damage[j] :
            if DP[i] > (DP[i - damage[j]] + use[j]) :
                DP[i] = DP[i - damage[j]] + use[j]
        else :
            if DP[i] > use[j] :
                DP[i] = use[j]

print(DP[h])

Submission status: Time Limit Exceeded

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

DP = [1<<60 for _ in range(h + 1)]
DP[0] = 0
for i in range(1, h + 1) :
    for j in range(n) :
        if i >= damage[j] :
            if DP[i] > (DP[i - damage[j]] + use[j]) :
                DP[i] = DP[i - damage[j]] + use[j]
        else :
            if DP[i] > use[j] :
                DP[i] = use[j]

print(DP[h])

Submission status: Time Limit Exceeded

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

DP = [1<<60 for _ in range(h + 1)]
DP[0] = 0
for i in range(1, h + 1) :
    for j in range(n) :
        if i >= damage[j] :
            DP[i] = min(DP[i], DP[i - damage[j]]+use[j])
        else :
            if DP[i] > use[j] :
                DP[i] = use[j]

print(DP[h])

Submission status: Time Limit Exceeded

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

DP = [1<<60 for _ in range(h)]
DP.insert(0, 0)
for i in range(1, h + 1) :
    for j in range(n) :
        if i >= damage[j] :
            DP[i] = min(DP[i], DP[i - damage[j]]+use[j])
        else :
            if DP[i] > use[j] :
                DP[i] = use[j]

print(DP[h])