Problem:


Score : 500 points

Problem Statement

Ibis is fighting with a monster.

The health of the monster is H.

Ibis can cast N kinds of spells. Casting the i-th spell decreases the monster's health by A_i, at the cost of B_i Magic Points.

The same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.

Ibis wins when the health of the monster becomes 0 or below.

Find the minimum total Magic Points that have to be consumed before winning.

Constraints

1 \leq H \leq 10^4

1 \leq N \leq 10^3

1 \leq A_i \leq 10^4

1 \leq B_i \leq 10^4

All values in input are integers.

Input

Input is given from Standard Input in the following format:

H N
A_1 B_1
:
A_N B_N

Output

Print the minimum total Magic Points that have to be consumed before winning.

Sample Input 1

9 3
8 3
4 2
2 1

Sample Output 1

4

First, let us cast the first spell to decrease the monster's health by 8, at the cost of 3 Magic Points. The monster's health is now 1.

Then, cast the third spell to decrease the monster's health by 2, at the cost of 1 Magic Point. The monster's health is now -1.

In this way, we can win at the total cost of 4 Magic Points.

Sample Input 2

100 6
1 1
2 3
3 9
4 27
5 81
6 243

Sample Output 2

100

It is optimal to cast the first spell 100 times.

Sample Input 3

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461

Sample Output 3

139815



Sample input:
9 3
8 3
4 2
2 1


Sample output:
4

Submission status: Time Limit Exceeded

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

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

    MAX_V = 10**8+1
    dp = [MAX_V] * (H+1)
    dp[0] = 0
    for a, b in AB:
        for i in range(1, H+1):
            if i - a >= 0:
                v = dp[i-a] + b
            else:
                v = b
            if dp[i] > v:
                dp[i] = v

    print(dp[H])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

def main():
    h, n = map(int, input().split())
    ab = []
    for _ in range(n):
        ab.append(list(map(int, input().split())))
    
    inf = 100000000000
    # indexがモンスターに与えたダメージで、中身がトキのダメージ
    damages = [0] + [inf] * h
    for i in range(1, h + 1):
        for j in range(n):
            damage_monster = ab[j][0]
            damage_toki = ab[j][1]
            
            damages[i] = min(damages[max(0, i - damage_monster)] + damage_toki, damages[i])


    print(min(damages[h:]))
main()

Submission status: Time Limit Exceeded

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

cost = {}
cost[0] = 0
que = [0]
dmg = [0]*N
mp = [0]*N

for i in range(N):
    dmg[i], mp[i] = list(map(int,input().split()))

while que != [] :
        target = que.pop(0)
        for i in range(N):
            crnt_dmg = target+dmg[i]
            crnt_cost = cost[target] + mp[i]
            if crnt_dmg <= H: 
                if crnt_dmg in cost:
                    if cost[crnt_dmg] > crnt_cost:
                        cost[crnt_dmg] = crnt_cost
                        if crnt_dmg in que:
                            que.remove(crnt_dmg)
                        que.append(crnt_dmg)
                else :
                    cost[crnt_dmg] = crnt_cost
                    que.append(crnt_dmg)
            else :
                if H in  cost:
                    if cost[H] > crnt_cost:
                        cost[H] = crnt_cost
                else :
                    cost[H] = crnt_cost
    
print(cost[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 = [100000000] * (10 ** 5)
dp[0] = 0
for i in range(H):
    if dp[i] == 100000000:
        continue
    for j in range(N):
        a, b = AB[j]
        if dp[i] + b < dp[i + a]:
            dp[i + a] = dp[i] + b
print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
#E

def main():
    import numpy as np
    H, N = map(int, input().split())
    a = []
    b = []
    a.append(10**9)
    b.append(10**9)

    for i in range(N):
        a_i, b_i = map(int, input().split())
        a.append(a_i)
        b.append(b_i)

    dp = np.zeros((N+1,H+1))

    a = np.array(a)
    b = np.array(b)


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

    for i in range(1,N+1):
        for h in range(1,H+1):
            if h > a[i]:
                dp[i][h] = min(dp[i][h-a[i]]+b[i],dp[i-1][h])
            else:
                dp[i][h] = min(dp[i][0],dp[i-1][h])
    print(int(dp[N][H]))
if __name__ == '__main__':
    main()

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 = [tuple(map(int, input().split())) for _ in range(N)]

    MAX_V = 10**9+1
    dp = [MAX_V] * (H+1)
    dp[0] = 0
    for a, b in AB:
        for i in range(1, H+1):
            if i - a >= 0:
                v = dp[i-a] + b
            else:
                v = b
            if dp[i] > v:
                dp[i] = v

    print(dp[H])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

dp = [10**9] * (H + 5)
dp[0] = 0

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

print(dp[H])

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

def main():
    h, n = map(int, input().split())
    ab = []
    for _ in range(n):
        ab.append(list(map(int, input().split())))
    
    inf = 100000000000
    # indexがモンスターに与えたダメージで、中身がトキのダメージ
    damages = [inf for _ in range(100000)]
    damages[0] = 0
    for i in range(1, h + 1):
        for j in range(n):
            damage_monster = ab[j][0]
            damage_toki = ab[j][1]
            
            damages[i] = min(damages[max(0, i - damage_monster)] + damage_toki, damages[i])


    print(min(damages[h:]))
main()

Submission status: Time Limit Exceeded

Solution code:
h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
MOD = 10 ** 18
D = [MOD] * (h + 10 ** 4)
D[0] = 0
 
for i in range(h):
    for a, b in AB:
        D[i + a] = min(D[i + a], D[i] + b)
print(min(D[h:]))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import numpy as np
    h, n = map(int, input().split())
    lab = np.zeros((n, 2), dtype=np.int)
    i = 0
    while True:
        try:
            a, b = map(int, input().split())
            lab[i][0] = a
            lab[i][1] = b
        except:
            break
        i += 1
    ma = np.max(lab[:, 0])
    dp = np.ones((n + 1, h + ma), dtype=np.int) * np.inf
    dp[0][0] = 0
    for i in range(n):
        for j in range(h + ma):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if j >= lab[i][0]:
                dp[i+1][j] = min(dp[i+1][j-lab[i][0]] + lab[i][1], dp[i+1][j])
    print(np.int(np.min(dp[n, h:])))
resolve()

Submission status: Time Limit Exceeded

Solution code:
H,N = map(int,input().split())
A = []
for i in range(N):
    a,b = map(int,input().split())
    A.append((a,b))
A.sort()
MAXH = H+10**4
DP = [float("inf")]*(MAXH)
DP[0] = 0
for i in range(MAXH):
    for j in range(N):
        if i+A[j][0]>MAXH-1:break
        DP[i+A[j][0]] = min(DP[i]+A[j][1],DP[i+A[j][0]])
print(min(DP[H:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, N = map(int, readline().split())
m = map(int, read().split())
AB = zip(m, m)

INF = 10**18

dp = [INF] * (H + (10**4))
dp[0] = 0
for a, b in AB:
    for n in range(H):
        if dp[n + a] > dp[n] + b:
            dp[n + a] = dp[n] + b

print(min(dp[H:]))

Submission status: Time Limit Exceeded

Solution code:
def sol():
    h,n=map(int,input().split())
    l=[]
    ans=0
    for i in range(n):
        a,b=map(int,input().split())
        l.append((a,b))
    d=[0]*20005
    for i in range(h):
        for j in l:
            a,b=j[0],j[1]
            x=d[i]+b
            if i==0 or (d[i]!=0 and d[i+a]==0):
                if d[i+a]==0:
                    d[i+a]=x
                else:
                    d[i+a]=min(d[i+a],x)
            elif d[i]!=0 and d[i+a]!=0:
                d[i+a]=min(d[i+a],x)

    for i in range(h,20005):
        if ans==0:
            ans=d[i]
        elif d[i]!=0:
            ans=min(ans,d[i])
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)

H, N = map(int, input().split())

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


@lru_cache(maxsize=None)
def f(h):
    if h <= 0:
        return 0
    best = float("inf")
    for a, b in AB:
        val = b + f(h - a)
        if val < best:
            best = val
        #else:
        #    break
    return best


AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)
bestA, bestB = AB[0]

print(f(H))

Submission status: Time Limit Exceeded

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

inf = float('inf')
memo = [inf for _ in range(h+1)]
memo[0] = 0
for i in range(h+1):
    for x,y in l:
        # これめっちゃ大事やん
        j = min(i+x, h)
        memo[j] = min(memo[j],memo[i] + y)
print(memo[-1])

Submission status: Time Limit Exceeded

Solution code:
H,N = map(int,input().split())
AiBi= []
Ai = []
Bi = []
cosper = []
i=0


while True:
    try:
        AiBi.append(list(map(int,input().split())))
        Ai.append(AiBi[i][0])
        Bi.append(AiBi[i][1])
        cosper.append(AiBi[i][0] / AiBi[i][1])
        i+=1
    except:
        break

#bubble sort for B        
#H = int(input())

def bubbleSort(arr, brr, crr):
  n = len(arr)
  # Traverse through all array elements
  for i in range(n):
    # Last i elements are already in place
    for j in range(0, n-i-1):
      # traverse the array from 0 to n-i-1
      # Swap if the element found is greater
      # than the next element
      if arr[j] > arr[j+1] :
        arr[j], arr[j+1] = arr[j+1], arr[j]
        brr[j], brr[j+1] = brr[j+1], brr[j]
        crr[j], crr[j+1] = crr[j+1], crr[j]
        

bubbleSort(cosper,Bi,Ai)

damage = 0
j = 0
cost = 0
while(1):
  damage += Ai[j]
  cost += Bi[j]
  h= H - damage
  if(h < Ai[j]):
    temp = j
    while(h >= Ai[j]):
      j+=1
      if(j >= N):
        j=temp
        break
  elif(h <= 0):
    break

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
#"""
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))
ma=[]
for _ in range(n):
    tmp=list(map(int,input().split()))
    ma.append(tmp)


#"""
#h=10**4
#n=10**3
#ma=[[i,i+1] for i in range(n)]

#ma=sorted(ma,key=lambda x:x[1])
#ma.reverse()
dp=[[float("inf") for _ in range(h+1)] for _ in range(n)]
for i in range(n):
    dp[i][0]=0
for i in range(1,h+1):
    dp[0][i]=math.ceil(i/ma[0][0])*ma[0][1]
#print(np.array(ma))
for i in range(1,n):
    #print("number:{},magic:{}".format(i,ma[i]))
    for j in range(1,h+1):
        if j<ma[i][0]:
            cal=ma[i][1]
        else:
            #print("sansyo before")
            cal=ma[i][1]+dp[i][j-ma[i][0]]
        #print("j:{},cal:{}".format(j,cal))
        dp[i][j]=min(dp[i-1][j],cal)
    #print()


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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    H, N = map( int, input().split())
    AB = [ list( map( int, input().split())) for _ in range(N)]
    dp = [10**9]*H + [0]*(10**4+1)
    T = H+10**4
    for a, b in AB:
        for i in range(T,a-1,-1):
            if dp[i-a] > dp[i]+b:
                dp[i-a] = dp[i]+b
    print(dp[0])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,N = map(int,input().split())
A = []
for i in range(N):
    a,b = map(int,input().split())
    A.append((a,b))
MAXH = H+10**4
DP = [float("inf")]*(MAXH)
DP[0] = 0
for i in range(MAXH):
    for j in range(N):
        if i+A[j][0]>MAXH-1:continue
        DP[i+A[j][0]] = min(DP[i]+A[j][1],DP[i+A[j][0]])
print(min(DP[H:]))

Submission status: Time Limit Exceeded

Solution code:
import math

H, N = map(int,input().split()) # 複数の数字を変数に格納
List = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

#for i in range(N):
#    List[i].append(List[i][0] / List[i][1])
    
#List.sort(key=lambda x: x[2], reverse=True)

table = [[0] * H for i in range(N)]

for i in range(H):
    table[0][i] = List[0][1] * (math.ceil((i+1) / List[0][0]))
    
for j in range(1,N):
    attack = List[j][0]
    MP = List[j][1]
    for i in range(H):
        if (i+1) < attack:
            table[j][i] = min(table[j-1][i], MP)
        else:
            table[j][i] = min(table[j-1][i], table[j][i-attack]+MP)
            
print(table[N-1][H-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 19 20:52:57 2020

@author: over-
"""


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

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

M=sum(A)
dp1=[0]*(H+1)
#dp2=[0]*(H+1)

for i in range(1,H+1):
    dp1[i]=i//A[0]*B[0]
    #dp2[i]=i//A[0]*B[0]
    if i%A[0]!=0: 
        dp1[i]+=B[0]
        #dp2[i]+=B[0]
#print(dp1)
if N>1:
    for a,b in zip(A[1:],B[1:]):
        for i in range(H,0,-1):
            m=[dp1[i]]
            for j in range(1,int(i//a)+1):
                m.append(dp1[i-a*j]+b*j)
            if i%a!=0:  m.append(b*(i//a+1))
            dp1[i]=min(m)
        #print(dp1)

    
print(dp1[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,N=map(int,input().split())
X=np.array([0,0])
Q=np.array([X for i in range(N)])

for i in range(N):
	A,B=map(int,input().split())
	Q[i]=np.array([A,B])
	
P=np.array([0 for i in range(20002)])
P[0]=0
for k in range(1,H+1):
	P[k]=1+H*N*100001
	for i in range(N):
		P[k]=min(P[k-Q[i][0]]+Q[i][1],P[k])
print(P[H])

Submission status: Time Limit Exceeded

Solution code:
H,N = map(int, input().split())
DP = [0]*(H+1)
dp_ = [0]+[float("inf")]*H
for n in range(N):
  A,B = map(int, input().split())
  dp = list(DP)
  for h in range(1,H+1): dp[h] = min(dp_[h], dp[max(0,h-A)]+B)
  dp_ = dp
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 i in range(1, 1+H):
  dp[i] = 10 ** 8
  for A, B in AB:
    if i >= A:
      t = dp[i - A] + B
      if t < dp[i]:
        dp[i] = t
    else:
      if B < dp[i]:
        dp[i] = B

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
H,N = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[10**18]*(10**4+1) for _ in range(N+1)]
for i in range(N+1):
  dp[i][0]=0
mi=10**9
for i in range(N):
  for w in range(10**4+1):
    dp[i+1][w]=min(dp[i+1][w],dp[i][w])
    if w-AB[i][0]>=0:
      dp[i+1][w]=min(dp[i+1][w],dp[i + 1][w - AB[i][0]] + AB[i][1])
for i in range(H,10**4+1):
  mi = min(mi,dp[N][i])
print(mi)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import numpy as np
    h, n = map(int, input().split())
    lab = np.zeros((n, 2), dtype=np.int)
    i = 0
    while True:
        try:
            a, b = map(int, input().split())
            lab[i][0] = a
            lab[i][1] = b
        except:
            break
        i += 1
    ma = np.max(lab[:, 0])
    dp = np.ones((n + 1, h + ma), dtype=np.int) * np.inf
    dp[0][0] = 0
    for i in range(n):
        for j in range(h + ma):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if j >= lab[i][0]:
                dp[i+1][j] = min(dp[i+1][j-lab[i][0]] + lab[i][1], dp[i+1][j])
    print(np.int(np.min(dp[1:, h:])))
resolve()

Submission status: Time Limit Exceeded

Solution code:
import math

H, N = map(int,input().split()) # 複数の数字を変数に格納
List = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

for i in range(N):
    List[i].append(List[i][0] / List[i][1])
    
List.sort(key=lambda x: x[2], reverse=True)

table = [[0] * H for i in range(N)]

for i in range(H):
    table[0][i] = List[0][1] * (math.ceil((i+1) / List[0][0]))
    
for j in range(1,N):
    attack = List[j][0]
    MP = List[j][1]
    for i in range(H):
        if (i+1) < attack:
            table[j][i] = min(table[j-1][i], MP)
        else:
            table[j][i] = min(table[j-1][i], table[j][i-attack]+MP)
            
print(table[N-1][H-1])

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 6)
Hitpoint, N = map(int, input().split())
magic_damage = []
magic_point = []
for _ in range(N):
    A, B = map(int, input().split())
    magic_damage.append(A)
    magic_point.append(B)

@lru_cache(maxsize=None)
def solve(i, now_HP):
    if now_HP <= 0:
        retval = 0
    elif i == N:
        retval = float('inf')
    else:
        retval = min(solve(i + 1, now_HP), solve(i, now_HP - magic_damage[i]) + magic_point[i])
    return retval


print(solve(0, Hitpoint))

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

INF = 10 ** 15
dp = [INF] * H
dp[0] = 0
answer = INF
for a, b in AB:
  for i in range(H):
    if dp[i] != INF:
      if i + a < H:
        dp[i + a] = min(dp[i + a], dp[i] + b)
      else:
        answer = min(dp[i] + b, answer)

print(answer)

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

Submission status: Time Limit Exceeded

Solution code:
h,n=map(int,input().split())
M=[list(map(int,input().split())) for _ in range(n)]
res=[0]
f=0
for j in range(1,h+1):
    
    i=0
    if 0>=j-M[i][0]:
        ind=0
    else:
        ind=j-M[i][0]
    ff=res[ind]+M[i][1]
    
    for i in range(1,n):
        if 0>=j-M[i][0]:
            ind=0
        else:
            ind=j-M[i][0]
        kari=res[ind]+M[i][1]
        
        ff=min(ff,kari)
    res.append(ff)
print(res[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
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　使う魔力がk以下 の時の最大攻撃力で漸化式を立てる
# dp[i] = max(dp[i-a[j]]+b[j]) # i-a[j] >= 0となる全てのa[j]に対して
max_magic = b[0]*((h-1)//a[0]+1)
#print(max_magic)
dp = [0]*(max_magic+6)
dp[0] = 0
ans = 0
for i in range(1,max_magic+5):
    dp[i] = dp[i-1] #上書きされない時、それ以下の魔力で与えられた攻撃はいける
    for j in range(n):#すべての種類の魔法に対してループ
        if i -b[j] >= 0:#魔法が使えるなら
            dp[i] = max(dp[i],dp[i-b[j]]+a[j])
    #print(i,dp[i])
    if dp[i] >= h:
        ans = i
        print(ans)
        exit(0)

Submission status: Time Limit Exceeded

Solution code:
INF = 10**8

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

    a_list = [0] * n
    b_list = [0] * n
    for i in range(n):
        a_list[i], b_list[i] = map(int, input().split())
    a_max = max(a_list)

    length = h + a_max*2
    dp = [INF] * length
    dp[0] = 0
    times = 0
    while True:
        for i in range(length):
            if dp[i] == INF:
                continue
            for j in range(n):
                idx = i + a_list[j]
                if idx >= length:
                    continue
                temp1 = dp[idx]
                temp2 = min(temp1, dp[i] + b_list[j])
                dp[idx] = temp2
            times += 1
            if times > h:
                ans = min(dp[h:])
                if ans == INF:
                    pass
                else:
                    print(ans)
                    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

use_clipboard=True
bbn=1000000007
	
#+++++

		
def main():
	h, n = map(int, input().split())
	ii=[]
	for i in range(n):
		a,b=map(int, input().split())
		ii.append([a/b, a, b])
	#ii.sort()
	
	_,ma,mb = ii[0]
	tn = (h + ma-1)//ma
	tc = tn * mb
	
	vv=[bbn]*(h+1)
	vv[0]=0
	for i in range(h+1):
		for c,a,b in ii:
			nn = min(i + a, h)
			vv[nn]= min(vv[i] + b, vv[nn])
	
	print(vv[-1])
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
class input_clipboard:
	def __init__(self,s):
		self.input_l=s.splitlines()
		self.ii=0
		
	def input(self):
		ret = self.input_l[self.ii]
		self.ii+=1
		return ret

if __name__ == "__main__":
	if sys.platform =='ios':
		if use_clipboard:
			import clipboard
			input_text=clipboard.get()
			ic=input_clipboard(input_text)
			input = lambda : ic.input()
		else:
			sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, n = map(int, input().split())
dp = np.zeros((n+1, h+1))
dp[0] = np.inf
for i in range(1, n+1):
    a, b = map(int, input().split())
    for j in range(1, h+1):
        if j >= a:
            dp[i][j] += min(
                dp[i-1][j], dp[i][j-a] + b,
            )
        else:
            dp[i][j] += min(
                dp[i-1][j], b
            )
print(int(dp[n][h]))

Submission status: Time Limit Exceeded

Solution code:
import sys

use_clipboard=True
bbn=1000000007
	
#+++++

		
def main():
	h, n = map(int, input().split())
	ii=[]
	for i in range(n):
		a,b=map(int, input().split())
		ii.append([a/b, a, b])
	ii.sort()
	
	_,ma,mb = ii[0]
	tn = (h + ma-1)//ma
	tc = tn * mb
	
	vv=[bbn]*(h+1)
	vv[0]=0
	for i in range(h+1):
		for c,a,b in ii:
			nn = min(i + a, h)
			vv[nn]= min(vv[i] + b, vv[nn])
	
	print(vv[-1])
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
class input_clipboard:
	def __init__(self,s):
		self.input_l=s.splitlines()
		self.ii=0
		
	def input(self):
		ret = self.input_l[self.ii]
		self.ii+=1
		return ret

if __name__ == "__main__":
	if sys.platform =='ios':
		if use_clipboard:
			import clipboard
			input_text=clipboard.get()
			ic=input_clipboard(input_text)
			input = lambda : ic.input()
		else:
			sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

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

dp = [float("inf")] * (H + AB[-1][0])
dp[0] = 0
for i in range(1, len(dp)):
    for a, b in AB:
        if i - a >= 0:
            dp[i] = min(dp[i], dp[i - a] + b)
        else:
            break

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

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter as it
from math import ceil

h, n = map(int, input().split(' '))
a_l = [list(map(int, input().split(' '))) for _ in range(n)]
a_s = sorted(a_l,key=it(0))
x = a_s[-1][0] + h
b = [10**20] * x
b[0] = 0
for i in range(h):
    for j,k in a_s:
        if b[i+j] > b[i] + k:
            b[i+j] = b[i] + k
print(min(b[h:]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,N=map(int,input().split())
X=np.array([0,0])
Q=np.array([X for i in range(N)])
maxA=0
maxC=0
for i in range(N):
	A,B=map(int,input().split())
	Q[i]=np.array([A,B])

Qmax=np.max(Q,axis=0)
Bmax=min(Qmax[0],H)
	
P=np.array([1+H*N*100001 for i in range(H+1)])
P[0]=0
for k in range(1,Bmax+1):
	for i in range(N):
		P[k]=min(P[max(0,k-Q[i][0])]+Q[i][1],P[k])
for k in range(Bmax+1,H+1):
	for i in range(N):
		P[k]=min(P[k-Q[i][0]]+Q[i][1],P[k])
print(P[H])

Submission status: Time Limit Exceeded

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

eff = 0
eff_index = 0
for i in range(n):
    a[i], b[i] = [int(_) for _ in input().split()]
    if eff < a[i]/b[i]:
        eff = a[i]/b[i]
        eff_index = i

max_kaisuu = - (-h//a[eff_index])

ans = float('inf')
H = max_kaisuu * b[eff_index]
dp = [[0] * (H+1) for _ in range(n+1)]
# dp[i][j] i番目までの魔法で消費魔力がjを超えないように選んだときのダメージの最大値
for i in range(n):
    for j in range(H+1):
        if j < b[i]:# i番目の魔法消費b[i]がjを超えているので，入れる可能性がない

            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-b[i]]+a[i])# 入れ場合と入れない場合を比較

        if dp[i+1][j] >= h:
            ans = min(ans, j)
            H = j
            continue
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy

hp, n = map(int, input().split())
aList = [0] * n
mpList = [0] * n
eList = [0] * n
for i in range(n):
  aList[i], mpList[i] = map(int, input().split())
  eList = aList[i] / mpList[i]

# E means Efficient
maxEIndex = numpy.argmax(eList)
kariMinMp = math.ceil(hp / aList[maxEIndex]) * mpList[maxEIndex]
dp = [[0 for j in range(kariMinMp + 1)] for i in range(n + 1)]

for i in range(n):
  for m in range(kariMinMp + 1):
    if m < mpList[i]:
      dp[i+1][m] = dp[i][m]
    elif mpList[i] > kariMinMp:
      dp[i+1][m] = dp[i][m]
    else:
      dp[i][m] = max(dp[i][m - mpList[i]] + aList[i], dp[i][m])
      dp[i+1][m] = dp[i][m]

for (mp, a) in enumerate(dp[n]):
  if hp <= a:
    print(mp)
    break

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()
dp = [float("inf")] * (H + AB[-1][0])
dp[0] = 0
for i in range(1, len(dp)):
    for a, b in AB:
        if i - a >= 0:
            dp[i] = min(dp[i], dp[i - a] + b)
        else:
            break

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

Submission status: Time Limit Exceeded

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

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

min_cost = min([b for a, b in ab_list])

for i, cost in enumerate(dp):
    if dp[i] == -1:
        dp[i] = dp[i-1] + min_cost
        continue

    for a, b in ab_list:
        if i+a <= h:
            target = i+a
        else:
            target = -1

        if dp[target] == -1:
            dp[target] = cost + b
        else:
            dp[target] = min(dp[target], cost+b)

print(dp[-1])

Submission status: Time Limit Exceeded

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

L.sort()

dp=[100000000 for i in range(h+1)]
dp[0]=0
for i in range(h):
    for q in range(n):
        power=L[q][1]
        magic=L[q][2]
        dp[min(h,i+power)]=min(dp[min(h,i+power)],dp[i]+magic)

print(dp[h])

Submission status: Time Limit Exceeded

Solution code:
H,N = map(int, input().split())
dp_ = [0]+[float("inf")]*H
for n in range(N):
  A,B = map(int, input().split())
  dp = [0]*(H+1)
  for h in range(1,H+1): dp[h] = min(dp_[h], dp[max(0,h-A)]+B)
  dp_ = dp
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
H, N = map(int, input().split())
AB = [0] * N
damage = [0] * N
for i in range(N):
  AB[i] = list(map(int, input().split()))
  damage[i] = AB[i][0]
  
x = min(AB, key = lambda x:x[1])
x = x[1]
  
DP = [10 ** 10] * (10 ** 4 + 1)#ダメージを与える最小魔力
DP[0] = 0

for i in range(1, 10 ** 4 + 1):
  for j in range(i):
    if j in damage:
      p = damage.index(j)
      DP[i] = min(DP[i], DP[i - j] + AB[p][1])
  if DP[i] == 10 ** 10:
    DP[i] = x
  
print(DP[H])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))

    @lru_cache(maxsize=10000)
    def rec(h):
        if h <= 0:
            return 0
        return min(rec(h - a) + b for a, b in AB)

    print(rec(H))

main()

Submission status: Time Limit Exceeded

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

eff = 0
eff_index = 0
for i in range(n):
    a[i], b[i] = [int(_) for _ in input().split()]
    if eff < a[i]/b[i]:
        eff = a[i]/b[i]
        eff_index = i

max_kaisuu = - (-h//a[eff_index])

ans = float('inf')
H = max_kaisuu * b[eff_index]
dp = [[0] * (H+1) for _ in range(n+1)]
# dp[i][j] i番目までの魔法で消費魔力がjを超えないように選んだときのダメージの最大値
for i in range(n):
    for j in range(H+1):
        if j < b[i]:# i番目の魔法消費b[i]がjを超えているので，入れる可能性がない

            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-b[i]]+a[i])# 入れ場合と入れない場合を比較

        if dp[i+1][j] >= h:
            ans = min(ans, j)
            continue
print(ans)

Submission status: Time Limit Exceeded

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

def solve(ab, hp, memo):
  if hp <= 0:
    return 0, -hp
  else:
    err = 0
    if not hp in memo:
      c_min = 10**10
      for attack, cost in ab:
        c, e = solve(ab, hp-attack, memo)
        if c+cost < c_min:
          c_min = c+cost
          err = e
      for i in range(err+1):
        memo[hp+i] = c_min
    return memo[hp], err

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
print(solve(AB, H, {})[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))
    d = defaultdict(int)
    for h in range(H):
        for i in range(N):
            p_use = d[(h-AB[i][0], i)]+AB[i][1] if h-AB[i][0] >= 0 else AB[i][1]
            p_not = d[(h,i-1)] if i>0 else INF
            d[(h,i)] = min(p_use,p_not)
    print(d[(H-1, N-1)])

main()