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

data = []

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

dp = [0] * (H+1)

for i in range(1,H+1):
    dp[i] = min([dp[max(0,i-data[j][0])] + data[j][1] for j in range(N)])
    #print(dp)
print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout

def sol2():
	H, N = (int(x) for x in stdin.readline().split())
	dp = [float('inf') for _ in range(H+1)]
	dp[0] = 0
	for line in stdin:
		dmg, cost = [int(x) for x in line.split()]
		for i in range(len(dp)):
			new = min(H, i + dmg)
			dp[new] = min(dp[new], dp[i] + cost)
	stdout.write(str(dp[-1]))

if __name__ == "__main__":
	sol2()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout

def main():
	H, N = (int(x) for x in stdin.readline().split())
	spells = [] #dmg, cost
	for line in stdin:
		spells.append([int(x) for x in line.split()])
	dp = [float('inf') for _ in range(H+1)]
	dp[0] = 0
	for i in range(1, len(dp)):
		for dmg, cost in spells:
			dp[i] = min(dp[max(0, i-dmg)]+cost, dp[i])
	stdout.write(str(dp[-1]))

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout

def main():
	H, N = (int(x) for x in stdin.readline().split())
	spells = [] #dmg, cost
	for _ in range(N):
		spells.append([int(x) for x in stdin.readline().split()])
	dp = [float('inf') for _ in range(H+1)]
	dp[0] = 0
	for i in range(1, len(dp)):
		for dmg, cost in spells:
			dp[i] = min(dp[max(0, i-dmg)]+cost, dp[i])
	stdout.write(str(dp[-1]))

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

magics = []
max_cost = 0
for _ in range(n):
    at, cost = map(int, input().split())
    max_cost = max(max_cost, cost)
    magics.append((at, cost))

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(len(dp)):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

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

dmg = mahou[:, 0]
mp = mahou[:, 1]

dp = np.full(H+1, float("inf"))
dp[0] = 0

for h in range(H):
  for d, m in zip(dmg, mp):
    new_hp = min(h + d, H)
    dp[new_hp] = min(dp[new_hp], dp[h] + m)
print(int(dp[-1]))

Submission status: Time Limit Exceeded

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

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

print(dp[-1])

Submission status: Time Limit Exceeded

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

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

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    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 = [0] * (H+1)
    for x in range(1, H+1):
        dp[x] = min(dp[max(x-a, 0)] + b for a, b in zip(A, B))

    print(dp[H])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

inf = 10 ** 10
minmp = [inf for _ in range(h+1)]
minmp[0] = 0
for i in range(n):
  for j in range(h+1):
    minmp[j] = min([minmp[k] + (j-k+a[i]-1)//a[i] * b[i] for k in range(j+1)])
print(minmp[-1])

Submission status: Time Limit Exceeded

Solution code:
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append((a,b))

max_a = max(AB[i][0] for i in range(N))
DP = [float('inf') for i in range(H + max_a + 1)]
DP[0] = 0
for i in range(1, H + max_a):
    DP[i] = min(DP[i - a] + b for a, b in AB)

print(min(DP[H:]))

Submission status: Time Limit Exceeded

Solution code:
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append((a,b))
AB.sort()

max_a = max(AB[i][0] for i in range(N))
DP = [float('inf') for i in range(H + max_a + 1)]
DP[0] = 0
for i in range(1, H + max_a):
    DP[i] = min(DP[i - a] + b for a, b in AB)

print(min(DP[H:]))

Submission status: Time Limit Exceeded

Solution code:
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append((a,b))
AB.sort()

DP = [float('inf') for i in range(2*10**4 + 1)]
DP[0] = 0
for i in range(H):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print(min(DP[H:]))

Submission status: Time Limit Exceeded

Solution code:
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append([a,b])
AB.sort()

DP = [float('inf') for i in range(2*10**4 + 1)]
DP[0] = 0
for i in range(H):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print(min(DP[H:]))

Submission status: Time Limit Exceeded

Solution code:
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append([a,b])
AB.sort()

DP = [float('inf') for i in range(2* 10**4+1)]
DP[0] = 0
for i in range(10**4):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print(min(DP[H:]))

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
magics = sorted([list(map(int, input().split())) for _ in range(n)])
max_cost = max(magic[1] for magic in magics)

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

dp[0] = 0
for i in range(len(dp)):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
magics = [list(map(int, input().split())) for _ in range(n)]
max_cost = max(magic[1] for magic in magics)

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

dp[0] = 0
for i in range(len(dp)):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())

magics = []
max_cost = 0
for _ in range(n):
    at, cost = map(int, input().split())
    max_cost = max(max_cost, cost)
    magics.append((at, cost))

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(len(dp)):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:

def main():
    h, n = map(int, input().split())

    magics = []
    max_cost = 0
    for _ in range(n):
        at, cost = map(int, input().split())
        max_cost = max(max_cost, cost)
        magics.append((at, cost))

    dp = [float('inf')] * (h+max_cost)
    dp[0] = 0
    for i in range(len(dp)):
        for at, cost in magics:
            if at <= i:
                dp[i] = min(dp[i], dp[i-at] + cost)
    print(min(dp[h:]))

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, B = map(int, input().split())
    a[i] = A
    b[i] = B

ans = [-1] * (h + 1)
ans[0] = 0

for i in range(h):
    if (ans[i] >= 0):
        for j in range(n):
            next = min(h, i + a[j])
            if ans[next] < 0:
                ans[next] = ans[i] + b[j]
            else:
                ans[next] = min(ans[next], ans[i] + b[j])

print(ans[h])

Submission status: Time Limit Exceeded

Solution code:
Mx = 9999999999999

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

D = [Mx] * 40000

D[0] = 0

for i in range(H+1):
    for spell in L:
        if D[i] + spell[1] < D[i+spell[0]]:
            D[i+spell[0]] = D[i] + spell[1]

print(min(D[H:]))

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc153/tasks/abc153_e
# コイン問題の応用で解けそう
# ナップサック解法をあとでちゃんと確認

# INFで初期化したdpテーブルでコイン問題を解いて、ピッタリ勝てないときは最小コストにmin(B)を足す
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, N = read_ints()
A, B = read_col(N, 2)
minb = min(B)
maxa = max(A)
INF = 10**10 + 1

dp = [INF] * (H + 1 + maxa)
dp[0] = 0

for i in range(1, H + 1 + maxa):
    for a, b in zip(A, B):
        if i - a < 0:
            continue
        dp[i] = min(dp[i], dp[i - a] + b)

# if dp[H] < INF:
#     print(dp[H])
#     exit()

print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
c = [0]*n
m = [0]*n

mc = 0
for i in range(n):
    c[i], m[i] = map(int, input().split())
    if mc < c[i]:
        mc = c[i]
    
dp = [10**10]*(h+mc)
dp[0] = 0

for i in range(1, h + mc):
    for j in range(n):
        dp[i] = min(dp[i-c[j]] + m[j], dp[i])
        
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
c = [0]*n
m = [0]*n

mc = 0
for i in range(n):
    c[i], m[i] = map(int, input().split())
    if mc < c[i]:
        mc = c[i]
    
dp = [0]*(h+1+mc)
dpn = [0]*(h+1+mc)

while True:
    for i in range(len(dp)):
        for j in range(n):
            if i == c[j]:
                if dp[i] == 0 and dpn[i] == 0:
                    dpn[i] = m[j]
                elif dpn[i] > 0:
                    dpn[i] = min(m[j], dpn[i])
            elif i > c[j]:
                if dp[i-c[j]] > 0:
                    if dpn[i] == 0:
                        dpn[i] = dp[i-c[j]] + m[j]
                    else:
                        dpn[i] = min(dp[i-c[j]] + m[j], dpn[i])
    if dp == dpn:
        break
    dp = dpn
    dpn = dpn[:]

mi = 10**9    
for i in dpn[h:]:
    if i > 0 and i < mi:
        mi = i

print(mi)

Submission status: Time Limit Exceeded

Solution code:
def main():
    h, n = map(int, input().split())
    magic_list = []

    for _ in range(n):
        a, b = map(int, input().split())
        magic_list.append((a, b))

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    # 1-origin
    inf = 1 << 40
    max_attack = max(magic_list)[0]
    dp = [inf] * (h + max_attack)
    dp[0] = 0

    # time O(HN)
    for hp in range(1, h + max_attack):
        for attack, mp in magic_list:
            if hp >= attack:
                dp[hp] = min(dp[hp], dp[hp - attack] + mp)

    return min(dp[h:])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h, n = map(int, input().split())
    magic_list = []

    for _ in range(n):
        a, b = map(int, input().split())
        magic_list.append((a, b))

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    # 1-origin
    inf = 1 << 40
    max_attack = max(magic_list)[0]
    dp = [inf] * (h + max_attack)
    dp[0] = 0

    # time O(HN)
    for hp in range(1, h + max_attack):
        for attack, mp in magic_list:
            if hp >= attack and dp[hp - attack] < inf:
                dp[hp] = min(dp[hp], dp[hp - attack] + mp)

    return min(dp[h:])


main()

Submission status: Time Limit Exceeded

Solution code:
D = 0

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

dp = [1e17 if i else 0 for i in range(h+1)]
m = {}

l = []

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

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

print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

h,n = m()

a = [l() for i in range(n)]

a.sort(reverse = True)

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

dp[0] = 0

for i in range(n):
    z,x = a[i]
    
    for j in range(z,h+1):
        dp[j] = min(dp[j],dp[j-z] + x)
    mi = mod
    for j in range(max(0,h-z),h+1):
        mi = min(mi,dp[j])

    dp[-1] = min(dp[-1],mi+x)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
ls = []
x = 0
for i in range(N):
  a, b = map(int, input().split())
  ls += [(a,b)]
  if a>x:
    x = a

L = x+H+1
dp = [10**9]*L
dp[0] = 0
for i in range(L):
  for j in range(N):
    a, b = ls[j]
    if i>=a:
      dp[i] = min(dp[i], dp[i-a]+b)

ans = min(dp[H:])

print(ans)

Submission status: Time Limit Exceeded

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

max_ab = max(AB)
dp = [-1]*(H+max_ab[0]+1)
dp[0] = 0

for i in range(1, H + max_ab[0]):
    lst = [dp[i-AB[j][0]] + AB[j][1] for j in range(N) if (i >= AB[j][0] and dp[i-AB[j][0]]!=-1)]
    if lst!=[]:dp[i] = min(lst)

print(min([i for i in dp[H:-1] if i!=-1]))

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

def ibis(H, A, B):
    dp = [max(B) * H] * (H + 1)
    dp[0] = 0
    for h in range(H):
        for n in range(N):
            hp = min(h + A[n], H)
            dp[hp] = min(dp[hp], dp[h] + B[n])
    return dp[H]

print(ibis(H, A, B))

Submission status: Time Limit Exceeded

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

dp = [0] * (h+max(a for a,b in ab))
for i in range(1, len(dp)):
    dp[i] = min([float('inf')] + [(dp[i-a]+b) for a, b in ab if i-a >= 0])
print(min(dp[h:]))

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

def ibis(H, A, B):
    minB = min(B)
    dp = [max(B) * H] * (H + 1)
    dp[0] = 0
    for h in range(H):
        for n in range(N):
            dp[h + 1] = min(dp[h + 1], dp[h] + minB)
            hp = min(h + A[n], H)
            dp[hp] = min(dp[hp], dp[h] + B[n])
    return dp[H]

print(ibis(H, A, B))

Submission status: Time Limit Exceeded

Solution code:
H, N = 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) for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(H+1):
        if j - a[i] <= 0:
            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])

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
magic = [0]*(h+1)
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h+1):
        if (magic[j] or j == 0):
            if j == h:
                continue
            key = min([j+a, h])
            if magic[key] == 0:
                magic[key] = magic[j] + b
            else:
                magic[key] = min([magic[key], magic[j]+b])
print(magic[h])

Submission status: Time Limit Exceeded

Solution code:
n = input()    
m = n.split()
p = [int(i) for i in m] # p[0]体力p[1]魔法
list = []
for i in range(p[1]): #因数注意！
    n = input()    
    m = n.split()
    q = [int(i) for i in m] #1列の数列をリスト化
    list.append(q)
list.sort()

def knapsack(H,mahou):
    #期化
    inf=float("inf")
    dp=[inf for i in range(H+mahou[-1][0]+1)]
    dp[0]= 0
    A = inf
    #DP
    for i in range(H+mahou[-1][0]):
        mindp = inf
        for j in mahou:
            if j[0] > i + 1:
                break
            else:
                mindp = min(mindp,dp[i+1-j[0]]+j[1])
        dp[i+1] = mindp
        if i + 1 >= H:
            A = min(A,mindp)

    return A
print(knapsack(p[0],list))

Submission status: Time Limit Exceeded

Solution code:
H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(Magic[i][0]-1):
            DP[i][j] = DP[i-1][j]
        DP[i][Magic[i][0]] = min(DP[i-1][Magic[i][0]],Magic[i][1])
        for j in range(Magic[i][0]+1,(MAX_A+1)):
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
print(min(DP[N-1][H:MAX_A]))

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([a for a, _b in AB])

dp = [10**18] * (H+max_A)
dp[0] = 0
#print(dp)

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

Submission status: Time Limit Exceeded

Solution code:
H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(1,(MAX_A+1)):
#            KARI = []
            DP[i][j]=DP[i-1][j]
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
            r = j // Magic[i][0]
            for k in range(r):
                DP[i][j]=min(DP[i][j],(DP[i-1][j-k*Magic[i][0]]+k*Magic[i][1]))
print(min(DP[N-1][H:MAX_A]))

Submission status: Time Limit Exceeded

Solution code:
H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(1,(MAX_A+1)):
#            KARI = []
            DP[i][j]=DP[i-1][j]
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
            r = j // Magic[i][0]
            for k in range(r):
                DP[i][j]=min(DP[i][j],(DP[i-1][j-k*Magic[i][0]]+k*Magic[i][1]))
print(min(DP[N-1][H:MAX_A]))

Submission status: Time Limit Exceeded

Solution code:
import math

H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = math.ceil(MAX_A/E_MIN) +1
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(1,(MAX_A+1)):
            KARI = []
            KARI.append(DP[i-1][j])
            if j % Magic[i][0] == 0:
                KARI.append((j//Magic[i][0]) * Magic[i][1])
            r = j // Magic[i][0]
            for k in range(r):
                KARI.append(DP[i-1][j-k*Magic[i][0]]+k*Magic[i][1])
            DP[i][j] = min(KARI)
print(min(DP[N-1][H:MAX_A]))

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())

max_da=max(da)*10  
dp = [float("inf") for i in range(H+max_da)]
dp[0]=0

for j in range(N):
    for i in range(H+max_da):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())
max_da=max(da)  
dp = [float("inf") for i in range(H*1000)]
dp[0]=0

for j in range(N):
    for i in range(H*1000):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

ans=0
for i in range(H,H*1000):
    if dp[i]!=float("inf"):
        ans=dp[i]
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())
max_da=max(da)  
dp = [float("inf") for i in range(H*10000)]
dp[0]=0

for j in range(N):
    for i in range(H*10000):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

ans=0
for i in range(H,H*10000):
    if dp[i]!=float("inf"):
        ans=dp[i]
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h, n = [int(x) for x in input().strip().split()]
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = [int(x) for x in input().strip().split()]

dp = [float('inf')] * (h + 1)
dp[0] = 0
for i in range(1, h+1):
    for aa, bb in zip(a, b):
        dp[i] = min(dp[i], dp[max(0, i-aa)]+bb)
print(dp[h])

Submission status: Time Limit Exceeded

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

c = [min(b)] + [h*max(b)]*(h-1)

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

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
input = sys.stdin.readline
def main():
	H,N = map(int,input().split())
	A,B = [],[]
	ap = A.append
	bp = B.append
	for _ in range(N):
		a,b = map(int,input().split())
		ap(a)
		bp(b)
	
	dp = [[0 for _ in range(H+1)] for _ in range(N)]
	
	for i in range(1,H+1):
		dp[0][i] = math.ceil(i/A[0])*B[0]

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

	print(dp[N-1][H])
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
input = sys.stdin.readline
def main():
	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 = [[0 for _ in range(H+1)] for _ in range(N)]
	
	for i in range(1,H+1):
		dp[0][i] = math.ceil(i/A[0])*B[0]

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

	print(dp[N-1][H])
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import math
def main():
	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 = [[0 for _ in range(H+1)] for _ in range(N)]
	
	for i in range(1,H+1):
		dp[0][i] = math.ceil(i/A[0])*B[0]

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

	print(dp[N-1][H])
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())

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

dp = [[float('inf') for _ in range(h+1)] for _ in range(n+1)]
dp[0][0] = 0
#print(attack, magic)
for i in range(n):
    for j in range(h+1):
        #print(max(dp[i][j], dp[i][j-attack[i]] + magic[i]))
        if dp[i+1][j] > dp[i][j]: dp[i+1][j] = dp[i][j]
        if dp[i+1][min(j+attack[i], h)] > dp[i+1][j]+magic[i]: dp[i+1][min(j+attack[i], h)] = dp[i+1][j]+magic[i]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
#import bisect
input = sys.stdin.buffer.readline
#lb = bisect.bisect_left

def main():
	H,N=map(int,input().split())
	#vA=list(map(int, input().split()))
	INF = 1001001001
	#H=int(input())
	mAB=[tuple(map(int,input().split())) for _ in [0,]*N]
	
	vN = [INF,]*(H+2)
	vN[0] = 0
	#mD = []
	#apD = mD.append
	#apD(vI)
	
	for h in range(H+2):
		#vN = mD[-1][:]
		for a,b in mAB:
			j = min(h+a,H+1)
			vN[j] = min(vN[h]+b, vN[j])
		#apD(vN)
		
	#res = min(mD[-1][-1],mD[-1][-2])
	res = min(vN[-2:])
	print(res)

main()

Submission status: Time Limit Exceeded

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

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

for i in range(h):
    for d, c in magic:
        next_index = min(i+d, h)
        dp[next_index] = min(dp[next_index], dp[i]+c)
        #print(d, c, dp)

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
ab=[]
h,n=map(int,input().split())
dp=[10**9]*(h+10001)
dp[0]=0
for i in range(n):
	x,y=map(int,input().split())
	ab.append([x,y])
for i in range(1,h+10001):
	for j in range(n):
		if i>=ab[j][0]:
			dp[i]=min(dp[i],dp[i-ab[j][0]]+ab[j][1])
ans=min(dp[h:])
print(ans)

Submission status: Time Limit Exceeded

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

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

for i in range(h):
    for d, c in magic:
        next_index = min(i+d, h)
        dp[next_index] = min(dp[next_index], dp[i]+c)
        #print(d, c, dp)

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:

def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    # print(magic)
    max_a = max(a for a, _ in magic)
    dp = [10**18 for _ in range(H + max_a)]
    dp[0] = 0

    for i in range(1, H+max_a):
        dp[i] = min([dp[i-a] + b for a, b in magic if i-a>=0], default=dp[i])

    ans = min(dp[H:H+max_a])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    # print(magic)
    max_a = max(a for a, _ in magic)
    dp = [float("inf") for _ in range(H + max_a)]
    dp[0] = 0

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

    ans = min(dp[H:H+max_a])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    # print(magic)
    max_a = max(a for a, _ in magic)
    dp = [float("inf") for _ in range(H + max_a)]
    dp[0] = 0

    for i in range(1, H+max_a):
        dp[i] = min([dp[i-a] + b for a, b in magic if i-a >= 0], default=dp[i])

    ans = min(dp[H:H+max_a])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
intLine=lambda:map(int,input().split())
h,n=intLine()
dp=[10**9]*(h+1)
dp[0]=0
for _ in range(n):
  a,b=intLine()
  for j in range(h+1):
    dp[j]=min(dp[j],dp[max(0,j-a)]+b)
print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
p = [0] * n
c = [0] * n

inf = 1e9 + 1

for i in range(n):
    pp, cc = map(int, input().split())
    p[i] = pp
    c[i] = cc
    
dp = [inf] * (h + max(p))
dp[0] = 0

for i in range(n):
    for j in range(h):
        dp[j + p[i]] = min(dp[j + p[i]], dp[j] + c[i])
    
print(min(dp[h:]))