Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 9)

H,N=map(int,input().split())
L=[]
for i in range(N):
    T=[0,0,0]
    T[1],T[2]=map(int,input().split())
    T[0]=T[2]/T[1]
    L.append(T)
L=sorted(L)
n=1+H//L[0][1]
m=n*L[0][2]
L=sorted(L,key=lambda x: x[2],reverse=True)
def DP(MAX,minM,i,T,M):
    t=T
    m=M
    if(T>=MAX):
        return M
    if(m<minM):        
        tm=DP(MAX,minM,i,t+L[i][1],m+L[i][2])
        if(minM>tm):
            minM=tm
        if(len(L)-1 > i):
            tm=DP(MAX,minM,i+1,t,m)
            if(minM>tm):
                minM=tm
    return minM

tm=DP(H,m,0,0,0)

print(tm)



Fixed submission:
H,N=map(int,input().split())
L=[]
m=0
for i in range(N):
    T=[0,0]
    T[0],T[1]=map(int,input().split())
    L.append(T)
    m=max(m,T[0])
L=sorted(L,reverse=True)
L.insert(0,[0,0])
m+=1
DP=[[10**10 for i in range(H+1+m)] for j in range(N+1)]
DP[0][0]=0

for i in range(1,N+1):
    t=0
    DP[i][0]=0
    for j in range(H+1):
        DP[i][j]=min(DP[i][j],DP[i-1][j])
        t=min(DP[i][j],DP[i-1][j])+L[i][1]
        DP[i][j+L[i][0]]=min(DP[i][j+L[i][0]],t)
    DP[i][H]=min(DP[i][H:-1])
print(min(DP[N][H:-1]))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 9)

H,N=map(int,input().split())
L=[]
for i in range(N):
    T=[0,0,0]
    T[1],T[2]=map(int,input().split())
    T[0]=T[2]/T[1]
    L.append(T)
L=sorted(L)
n=1+H//L[0][1]
m=n*L[0][2]

def DP(MAX,minN,minM,i,T,M):
    t=T
    m=M
    if(T>=MAX):
        return M
    if(T<MAX):
        t+=L[i][1]
        m+=L[i][2]
        if(m<minM):        
            tm=DP(MAX,minN,minM,i,t,m)
            if(minM>tm):
                minM=tm
    if(len(L)-1 > i):
        t=T
        m=M
        if(m<minM):
            tm=DP(MAX,minN,minM,i+1,t,m)
            if(minN>tm):
                minM=tm
    return minM

tm=DP(H,10**10,m,0,0,0)

print(tm)



Fixed submission:
H,N=map(int,input().split())
L=[]
m=0
for i in range(N):
    T=[0,0]
    T[0],T[1]=map(int,input().split())
    L.append(T)
    m=max(m,T[0])
L=sorted(L,reverse=True)
L.insert(0,[0,0])
m+=1
DP=[[10**10 for i in range(H+1+m)] for j in range(N+1)]
DP[0][0]=0

for i in range(1,N+1):
    t=0
    DP[i][0]=0
    for j in range(H+1):
        DP[i][j]=min(DP[i][j],DP[i-1][j])
        t=min(DP[i][j],DP[i-1][j])+L[i][1]
        DP[i][j+L[i][0]]=min(DP[i][j+L[i][0]],t)
    DP[i][H]=min(DP[i][H:-1])
print(min(DP[N][H:-1]))

Buggy python submission (verdict: Runtime Error):
H,N=map(int,input().split())
L=[]
for i in range(N):
    T=[0,0,0]
    T[1],T[2]=map(int,input().split())
    T[0]=T[2]/T[1]
    L.append(T)
L=sorted(L)
n=1+H//L[0][1]
m=n*L[0][2]

def DP(MAX,minN,minM,i,T,M):
    t=T
    m=M
    if(T>=MAX):
        return M
    if(T<MAX):
        t+=L[i][1]
        m+=L[i][2]
        if(m<minM):        
            tm=DP(MAX,minN,minM,i,t,m)
            if(minM>tm):
                minM=tm
    if(len(L)-1 > i):
        t=T
        m=M
        if(m<minM):
            tm=DP(MAX,minN,minM,i+1,t,m)
            if(minN>tm):
                minM=tm
    return minM

tm=DP(H,10**10,m,0,0,0)

print(tm)



Fixed submission:
H,N=map(int,input().split())
L=[]
m=0
for i in range(N):
    T=[0,0]
    T[0],T[1]=map(int,input().split())
    L.append(T)
    m=max(m,T[0])
L=sorted(L,reverse=True)
L.insert(0,[0,0])
m+=1
DP=[[10**10 for i in range(H+1+m)] for j in range(N+1)]
DP[0][0]=0

for i in range(1,N+1):
    t=0
    DP[i][0]=0
    for j in range(H+1):
        DP[i][j]=min(DP[i][j],DP[i-1][j])
        t=min(DP[i][j],DP[i-1][j])+L[i][1]
        DP[i][j+L[i][0]]=min(DP[i][j+L[i][0]],t)
    DP[i][H]=min(DP[i][H:-1])
print(min(DP[N][H:-1]))