Buggy python submission (verdict: Runtime Error):
h,n=map(int,input().split())

ab=[]
dp=[10**9]*(10**4)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    ab.append((a,b))
    dp[a]=b
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)



    
    



Fixed submission:
h,n=map(int,input().split())

ab=[]
dp=[10**9]*(10**5)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    dp[a]=min(dp[a],b)
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)

Buggy python submission (verdict: Runtime Error):
h,n=map(int,input().split())

ab=[]
dp=[10**9]*(h*2)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    ab.append((a,b))
    dp[a]=b
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)



    
    



Fixed submission:
h,n=map(int,input().split())

ab=[]
dp=[10**9]*(10**5)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    dp[a]=min(dp[a],b)
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)

Buggy python submission (verdict: Time Limit Exceeded):
h,n=map(int,input().split())

ab=[]
dp=[0]*(10**5)

for _ in range(n):
    a,b=map(int,input().split())
    ab.append((a,b))
    dp[b]=a

#dp[b]は、自分がダメージをｂ受けた時の、相手に与えたダメージ
i=1
while 1:

    dp[i]=max(dp[i],dp[i-1])
    for k in range((i-1)//2+2):
        dp[i]=max(dp[i],dp[k]+dp[i-k])
    
    #print(dp)
    if dp[i]>=h:
        print(i)
        exit()
    i+=1

    
    



Fixed submission:
h,n=map(int,input().split())

ab=[]
dp=[10**9]*(10**5)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    dp[a]=min(dp[a],b)
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)

Buggy python submission (verdict: Runtime Error):
h,n=map(int,input().split())

ab=[]
dp=[0]*(263)

for _ in range(n):
    a,b=map(int,input().split())
    ab.append((a,b))
    dp[b]=a

#dp[b]は、自分がダメージをｂ受けた時の、相手に与えたダメージ
i=1
while 1:

    dp[i]=max(dp[i],dp[i-1])
    for k in range((i-1)//2+2):
        dp[i]=max(dp[i],dp[k]+dp[i-k])
    
    #print(dp)
    if dp[i]>=h:
        print(i)
        exit()
    i+=1

    
    



Fixed submission:
h,n=map(int,input().split())

ab=[]
dp=[10**9]*(10**5)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    dp[a]=min(dp[a],b)
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)

Buggy python submission (verdict: Runtime Error):
h, n = map(int, input().split())

abKeys = set([])
result = [10**9] * (h+1)
for _ in range(n):
    a, b = map(int, input().split())
    result[a] = min(result[a],b)

for i in range(1,h+1):
    j = 1
    while j <= i // 2:
        result[i] = min(result[i], result[j] + result[i - j])

        j += 1


print(result[-1])


Fixed submission:
h,n=map(int,input().split())

ab=[]
dp=[10**9]*(10**5)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    dp[a]=min(dp[a],b)
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)

Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())

abKeys = set([])
result = [0] * (10 ** 8)
for _ in range(n):
    a, b = map(int, input().split())
    result[b] = a

for i in range(10 ** 8):
    j = 1
    while j <= i // 2:
        result[i] = max(result[i], result[j] + result[i - j])

        j += 1

    #if i % 100 == 0:
        #print(result[i], i, j, i - j)
    if result[i] >= h:
        print(i)
        exit()

#print(max(result))

Fixed submission:
h,n=map(int,input().split())

ab=[]
dp=[10**9]*(10**5)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    dp[a]=min(dp[a],b)
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)