Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
# 解答ちらっと見た
# 問題のキモは Cx,Cy,Hがそれぞれ100通り、
# 全探索をCx,Cy,Hに対して試みると 入力された情報のcheckを入れて101*101*100*100でTLEする。
# でもよく考えてみると、Cx,CyがわかればHはそのあとで出せるので Cx,Cyに対して全探索をする(101*101*100+100の計算量で済む)


def check(x, y, h, cx, cy):
    return h + abs(x - cx) + abs(y - cy)


def checks(x, y, eh, cx, cy, h):
    cah = max(h - abs(x - cx) - abs(y - cy), 0)
    return cah == eh


N = int(input())
H = {}

checkers = [(list(map(int, input().split()))) for _ in range(N)]
for x,y,h in checkers:
    if h>0:
        lockx=x
        locky=y
        lockh=h

for icx in range(101):
    for icy in range(101):
        H = set({})
        for checker in checkers:
            H.add(lockh + abs(lockx - icx) + abs(locky - icy))

        if len(H) == 1:
            # print('{} {} {}'.format(icx, icy, H[0]))
            ok = True
            for c in checkers:
                if not checks(c[0], c[1], c[2], icx, icy, H[0]):
                    # print('failedin {} {} {} {} {} {}'.format(c[0], c[1], c[2], icx, icy, H[0]))
                    ok = False
                    break
            if ok:
                print('{} {} {}'.format(icx, icy, H[0]))
                exit(0)


Fixed submission:
# 解答ちらっと見た
# 問題のキモは Cx,Cy,Hがそれぞれ100通り、
# 全探索をCx,Cy,Hに対して試みると 入力された情報のcheckを入れて101*101*100*100でTLEする。
# でもよく考えてみると、Cx,CyがわかればHはそのあとで出せるので Cx,Cyに対して全探索をする(101*101*100+100の計算量で済む)


def get_H(Cx, Cy):
    for x, y, h in L:
        if h > 0:
            return abs(x - Cx) + abs(y - Cy) + h


def check_H(Cx, Cy, H):
    for x, y, h in L:
        if h != max(H - abs(x - Cx) - abs(y - Cy), 0):
            return False
    return True


N = int(input())

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

for Cx in range(101):
    for Cy in range(101):
        H = get_H(Cx, Cy)
        if check_H(Cx, Cy, H):
            print('{} {} {}'.format(Cx, Cy, H))
            exit(0)
Buggy python submission (verdict: Runtime Error):
N,M,X,Y=map(int,input().split())
x_list =list(map(int,input().split()))
y_list=list(map(int,input().split()))

for i in range(1,100):

     if(max(x_list)<i and i<=min(y_list)):
        print('No War')
        exit(0)
print('War')
exit(0)

Fixed submission:
lists=input().split()

for i in range(len(lists)):
    lists[i]=int(lists[i])

lists=sorted(lists,reverse=True)
print(lists[0]*10+lists[1]+lists[2])
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
print(1 if N%K != 0 else 0)

Fixed submission:
S=list(input())
K=int(input())
#print(S)
for i in range(K):
    n=int(S[i])
    if n==1:
        if K-1==i:
            print(1)
            exit(0)
    else:
        print(n)
        exit(0)
Buggy python submission (verdict: Runtime Error):
class Need(object):
    def __init__(self,arg1,arg2):
        self.island1=int(arg1)
        self.island2=int(arg2)
        self.bridge=[]
        for i in range(arg1,arg2):
            self.bridge.append(i)
    def GETbridge(self):
        return self.bridge
deadbridges=0
islands,needsnum=map(int,input().split())
bridge=[0 for _ in range(islands-1)]
box = []
for i in range(needsnum):
    arg1,arg2=map(int,input().split())
    box.append(Need(arg1,arg2))
#ここから投票をする。
while(len(box)!=1):
    bridge = [0 for _ in range(islands - 1)]
    for need in box:
        list=need.GETbridge()
        for ing in list:
            bridge[ing-1]=bridge[ing-1]+1
    #集計終わり
    maxi=0
    for i in range(len(bridge)):
        if(bridge[i]>bridge[maxi]):
            maxi=i
    #橋を削除
    deadbridges=deadbridges+1
    #要望を削除
    kill=False
    for i in range(len(box)):
        try:
            s=box[i].GETbridge()
        except:
            break
        for k in s:
            if(k==bridge[maxi]):
                kill=True
                break
        if(kill):
            box.pop(i)
            i=i-1
print(deadbridges)

Fixed submission:
list=input().split()
for i in list:
    i=int(i)
list.sort()
sumcosts=0
costs=0
first=True
mae=0
for i in list:
    i = int(i)
    if(first):
        first=False
        mae=i
    else:
        sumcosts=sumcosts+abs((i-mae))
        mae=i
print(sumcosts)

Buggy python submission (verdict: Runtime Error):
class Need(object):
    def __init__(self,arg1,arg2):
        self.island1=int(arg1)
        self.island2=int(arg2)
        self.bridge=[]
        for i in range(arg1,arg2):
            self.bridge.append(i)
    def GETbridge(self):
        return self.bridge
deadbridges=0
islands,needsnum=map(int,input().split())
bridge=[0 for _ in range(islands-1)]
box = []
for i in range(needsnum):
    arg1,arg2=map(int,input().split())
    box.append(Need(arg1,arg2))
#ここから投票をする。
while(len(box)!=1):
    bridge = [0 for _ in range(islands - 1)]
    for need in box:
        list=need.GETbridge()
        for ing in list:
            bridge[ing-1]=bridge[ing-1]+1
    #集計終わり
    maxi=0
    for i in range(len(bridge)):
        if(bridge[i]>bridge[maxi]):
            maxi=i
    #橋を削除
    deadbridges=deadbridges+1
    #要望を削除
    kill=False
    for i in range(len(box)):
        try:
            s=box[i].GETbridge()
        except:
            break
        for k in s:
            if(k==bridge[maxi]):
                kill=True
                break
        if(kill):
            box.pop(i)
            i=i-1
print(deadbridges)

Fixed submission:
list=input().split()
for i in list:
    i=int(i)
list.sort()
sumcosts=0
costs=0
first=True
mae=0
for i in list:
    i = int(i)
    if(first):
        first=False
        mae=i
    else:
        sumcosts=sumcosts+abs((i-mae))
        mae=i
print(sumcosts)
Buggy python submission (verdict: Runtime Error):
def sig(x):
    return 1 if x==1 else sig(x-1)+x


a,b=map(int,input().split())

upper=int(sig(b-a))
print(upper-b)




Fixed submission:
print('ABD' if int(input())>999 else 'ABC')
Buggy python submission (verdict: Runtime Error):
def sig(x):
    return 1 if x==1 else sig(x-1)+x


a,b=map(int,input().split())

upper=int(sig(b-a))
print(upper-b)




Fixed submission:
import sys

sys.setrecursionlimit(10**6)

def sig(x):
    return 1 if x==1 else sig(x-1)+x


a,b=map(int,input().split())

upper=int(sig(b-a))
print(upper-b)

Buggy python submission (verdict: Runtime Error):
def sig(x):
    return 1 if x==1 else sig(x-1)+x


a,b=map(int,input().split())

upper=int(sig(b-a))
print(upper-b)


Fixed submission:
import sys

sys.setrecursionlimit(10**6)

def sig(x):
    return 1 if x==1 else sig(x-1)+x


a,b=map(int,input().split())

upper=int(sig(b-a))
print(upper-b)

Buggy python submission (verdict: Runtime Error):
def sigx(x):
    if(x==1):
        return 1
    else:
        return sigx(x-1)+x

a,b=map(int,input().split())

upper=int(sigx(b-a))
print(upper-b)




Fixed submission:
import sys

sys.setrecursionlimit(10**6)

def sig(x):
    return 1 if x==1 else sig(x-1)+x


a,b=map(int,input().split())

upper=int(sig(b-a))
print(upper-b)

Buggy python submission (verdict: Runtime Error):
def sigx(x):
    if(x==0):
        return 0
    else:
        return sigx(x-1)+x

a,b=map(int,input().split())

upper=int(sigx(b-a))
print(upper-b)




Fixed submission:
import sys

sys.setrecursionlimit(10**6)

def sig(x):
    return 1 if x==1 else sig(x-1)+x


a,b=map(int,input().split())

upper=int(sig(b-a))
print(upper-b)

Buggy python submission (verdict: Runtime Error):
def sigx(x):
    if(x==0):
        return 0
    else:
        return sigx(x-1)+x

a,b=map(int,input().split())

upper=sigx(b-a)
print(upper-b)


Fixed submission:
import sys

sys.setrecursionlimit(10**6)

def sig(x):
    return 1 if x==1 else sig(x-1)+x


a,b=map(int,input().split())

upper=int(sig(b-a))
print(upper-b)
Buggy python submission (verdict: Runtime Error):
X=int(input())

if X<4:
    print('1')
    exit(0)

n=2
p=2
max=0
b_flag=True
while True:
    n+=1
    #print(n)
    while b_flag:
        if n**p>X:
            b_flag=False
        elif max<n**p:
            max=n**p
        p+=1

    p = 2
    b_flag=True
    if n**p>X:
        break
print(max)

Fixed submission:
a,b,c,d=map(int,input().split())
direct_distance=abs(c-a)
AtB=abs(b-a)
BtC=abs(c-b)

if direct_distance<=d or (AtB <= d and BtC <= d):
    print('Yes')
else:
    print('No')

Buggy python submission (verdict: Runtime Error):
X=int(input())

if X<4:
    print('1')
    exit(0)

n=2
p=2
max=0
b_flag=True
while True:

    #print(n)
    while b_flag:
        if n**p>X:
            b_flag=False
        elif max<n**p:
            max=n**p
        p+=1
    n+=1
    p = 2
    b_flag=True
    if n**p>X:
        break
print(max)

Fixed submission:
a,b,c,d=map(int,input().split())
direct_distance=abs(c-a)
AtB=abs(b-a)
BtC=abs(c-b)

if direct_distance<=d or (AtB <= d and BtC <= d):
    print('Yes')
else:
    print('No')

Buggy python submission (verdict: Runtime Error):
X=int(input())

if X<4:
    print('1')
    exit(0)

n=2
p=2
max=0
b_flag=True
while True:

    #print(n)
    while b_flag:
        if n**p>X:
            b_flag=False
        elif max<n**p:
            max=n**p
        p+=1
    n+=1
    p = 2
    b_flag=True
    if n**p>X:
        break
print(max)

Fixed submission:
a,b,c,d=map(int,input().split())
direct_distance=abs(c-a)
AtB=abs(b-a)
BtC=abs(c-b)

if direct_distance<=d or (AtB <= d and BtC <= d):
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache
import sys

sys.setrecursionlimit(1000000)

@lru_cache(maxsize=1000000)
def dp(rest,score):
    ansbox=[]
    scorebox=[]
    for i in m_list:
        if (rest-i)>0:
            ansbox.append(dp(rest-i,score+1))
            scorebox.append(dp(rest-i, score+1)[1])
    if ansbox:
        max_index=scorebox.index(max(scorebox))
        return ansbox[max_index][0],ansbox[max_index][1]
    else:

        return rest,score
    pass

N,X=map(int,input().split())
m_list=[]
newX=X
sum=0
for i in range(N):
    inp=int(input())
    m_list.append(inp)
    newX-=inp

score=dp(newX,N)

print(score[1])


Fixed submission:
N,X=map(int,input().split())
M=[int(input()) for _ in range(N)]
print(len(M)+(X-sum(M))//min(M))

Buggy python submission (verdict: Runtime Error):
from functools import lru_cache

@lru_cache(maxsize=100000)
def dp(rest,score):
    ansbox=[]
    scorebox=[]
    for i in m_list:
        if (rest-i)>0:
            ansbox.append(dp(rest-i,score+1))
            scorebox.append(dp(rest-i, score+1)[1])
    if ansbox:
        max_index=scorebox.index(max(scorebox))
        return ansbox[max_index][0],ansbox[max_index][1]
    else:

        return rest,score
    pass

N,X=map(int,input().split())
m_list=[]
newX=X
sum=0
for i in range(N):
    inp=int(input())
    m_list.append(inp)
    newX-=inp

score=dp(newX,N)

print(score[1])


Fixed submission:
N,X=map(int,input().split())
M=[int(input()) for _ in range(N)]
print(len(M)+(X-sum(M))//min(M))
Buggy python submission (verdict: Runtime Error):
#include <iostream>
using namespace std;
int main(){
    int A,B,X;
    cin >> A >> B >> X;
    if( (B-X)>0 && (X-A)>=(B-X) )
    {
        cout<<"YES"<<endl;

    }
    else
    {
        cout<<"NO"<<endl;
    }

    return 0;
}

Fixed submission:
A,B,X=map(int,input().split())

need_neko_in_b=X-A

print('YES' if B >= need_neko_in_b and not A>X else 'NO')
Buggy python submission (verdict: Runtime Error):
from scipy.special import comb
import itertools
N=int(input())
S=[input() for _ in range(N)]
M=0
A=0
R=0
C=0
H=0
alives=0
march=['M','A','R','C','H']
for i in S:
    if i.startswith('M'):
        M+=1
    elif i.startswith('A'):
        A+=1
    elif i.startswith('R'):
        R+=1
    elif i.startswith('C'):
        C+=1
    elif i.startswith('H'):
        H+=1

if M==0:
    march.pop(march.index('M'))
if A==0:
    march.pop(march.index('A'))
if R==0:
    march.pop(march.index('R'))
if C==0:
    march.pop(march.index('C'))
if H==0:
    march.pop(march.index('H'))

if len(march)<3:
    print(0)

seq=list(itertools.combinations(march,3))

ans=0
for i in seq:
    temp=1
    for ch in i:
        if ch=='M':
            temp*=M
        if ch=='A':
            temp*=A
        if ch=='R':
            temp*=R
        if ch=='C':
            temp*=C
        if ch=='H':
            temp*=H
    ans+=temp

print(ans)

Fixed submission:
import itertools
N=int(input())
S=[input() for _ in range(N)]
M=0
A=0
R=0
C=0
H=0
alives=0
march=['M','A','R','C','H']
for i in S:
    if i.startswith('M'):
        M+=1
    elif i.startswith('A'):
        A+=1
    elif i.startswith('R'):
        R+=1
    elif i.startswith('C'):
        C+=1
    elif i.startswith('H'):
        H+=1

if M==0:
    march.pop(march.index('M'))
if A==0:
    march.pop(march.index('A'))
if R==0:
    march.pop(march.index('R'))
if C==0:
    march.pop(march.index('C'))
if H==0:
    march.pop(march.index('H'))

if len(march)<3:
    print(0)
    exit(0)

seq=list(itertools.combinations(march,3))

ans=0
for i in seq:
    temp=1
    for ch in i:
        if ch=='M':
            temp*=M
        if ch=='A':
            temp*=A
        if ch=='R':
            temp*=R
        if ch=='C':
            temp*=C
        if ch=='H':
            temp*=H
    ans+=temp

print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy
a,b=map(int,input().split())
print('Odd' if a*b%2==1 else 'Even')

Fixed submission:
a,b=map(int,input().split())
print('Odd' if a*b%2==1 else 'Even')
Buggy python submission (verdict: Runtime Error):
alphabets = [i for i in range(ord('a'), ord('z') + 1)]
lists = [ord(i) for i in input()]
lists=list(set(lists))
lists.sort()
for i in range(len(alphabets)):
    if i+1>=len(lists):
        if alphabets[i] == lists[i]:
            print(chr(alphabets[i+1]))
            exit(0)
    if alphabets[i]!=lists[i]:
        print(chr(alphabets[i]))
        exit(0)


print('None')


Fixed submission:
alphabets = [i for i in range(ord('a'), ord('z') + 1)]
lists = [ord(i) for i in input()]
lists=list(set(lists))
lists.sort()
for i in range(len(alphabets)):
    if i+1>=len(lists) and i!=25:
        if alphabets[i] == lists[i]:
            print(chr(alphabets[i+1]))
            exit(0)
    if alphabets[i]!=lists[i]:
        print(chr(alphabets[i]))
        exit(0)


print('None')

Buggy python submission (verdict: Runtime Error):
alphabets = [i for i in range(ord('a'), ord('z') + 1)]
lists = [ord(i) for i in input()]
lists=list(set(lists))
lists.sort()
for i in range(len(alphabets)):
    if alphabets[i]!=lists[i]:
        print(chr(alphabets[i]))
        exit(0)

print('None')


Fixed submission:
alphabets = [i for i in range(ord('a'), ord('z') + 1)]
lists = [ord(i) for i in input()]
lists=list(set(lists))
lists.sort()
for i in range(len(alphabets)):
    if i+1>=len(lists) and i!=25:
        if alphabets[i] == lists[i]:
            print(chr(alphabets[i+1]))
            exit(0)
    if alphabets[i]!=lists[i]:
        print(chr(alphabets[i]))
        exit(0)


print('None')
Buggy python submission (verdict: Runtime Error):
S=[for i in input()]
print('yes' if len(S)==len(set(S)) else 'no')


Fixed submission:
S = [i for i in input()]
print('yes' if len(S) == len(set(S)) else 'no')
Buggy python submission (verdict: Runtime Error):
print('YES' if (lambda poles=input().split(): True if (int(poles[1])-input(poles[0]))==(int(poles[2])-input(poles[1])) else False)() else 'NO')

Fixed submission:
a, b, c = map(int, input().split())
print('YES' if (b - a) == (c - b) else 'NO')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
power = 1
for i in range(1, N + 1):
    power *= i

print(power % (10 ** 9 + 7))


Fixed submission:
N = int(input())
power = 1
for i in range(1, N + 1):
    power = (i*power)%(10**9+7)

print(power)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
power = 1
for i in range(1, N + 1):
    power *= i

print(power % (10 ** 9 + 7))


Fixed submission:
N = int(input())
power = 1
for i in range(1, N + 1):
    power = (i*power)%(10**9+7)

print(power)
Buggy python submission (verdict: Time Limit Exceeded):
K, S = map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if x + y + z == S and 0 <= z <= K:
            #print('{} {} {}'.format(x,y,z))
            count += 1

print(count)


Fixed submission:
K, S = map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if x + y + z == S and 0 <= z <= K:
            #print('{} {} {}'.format(x,y,z))
            count += 1

print(count)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
sum = 0
for each in range(1,n):
    for other in range(each):
        sum += (a[each] % (10**9 + 7)) * (a[other] % (10**9 + 7))
        sum = sum % (10**9 + 7)
print(sum)

Fixed submission:
d,t,s = map(int, input().split())
time = d / s
if t >= time:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
target = input()
sum = 0
for each in all:
  sum += int(each)
if sum % 9 == 0:
  print("Yes")
else:
  print("No")

Fixed submission:
target = input()
sum = 0
for each in target:
  sum += int(each)
if sum % 9 == 0:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
number = int(input())
tall = list(map(int, input().split()))
addition = 0
for each in range(1, number + 1):
  difference = tall[each - 1] - tall[each]
  if difference > 0:
    addition += difference
    tall[each] += difference
print(addition)

Fixed submission:
number = int(input())
tall = list(map(int, input().split()))
addition = 0
for each in range(1, number):
    difference = tall[each - 1] - tall[each]
    if difference >= 0:
        addition += difference
        tall[each] += difference
print(addition)
Buggy python submission (verdict: Time Limit Exceeded):
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
from itertools import permutations
def solve(N):
    return sum(find_factors(i) for i in range(1,N))

def find_factors(num):
    i=1
    count=0
    while i*i<=num:
        if num%i==0:
            count+=1
            if num//i!=i:
                count+=1
        i+=1
    return count
N=readInt()
print(solve(N))

Fixed submission:
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
from itertools import permutations
def solve(N):
    count=0
    for i in range(1,N):
        count+=(N-1)//i
    return count

N=readInt()
print(solve(N))

Buggy python submission (verdict: Time Limit Exceeded):
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
from itertools import permutations
def solve(N):
    return sum(len(find_factors(i)) for i in range(1,N))

def find_factors(num):
    A=[]
    for i in range(1,num+1):
        if num%i==0:
            A.append(i)
    return A
N=readInt()
print(solve(N))

Fixed submission:
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
from itertools import permutations
def solve(N):
    count=0
    for i in range(1,N):
        count+=(N-1)//i
    return count

N=readInt()
print(solve(N))
Buggy python submission (verdict: Time Limit Exceeded):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

H,N = imn()
AB = [iln() for _ in range(N)]

DP = [10 ** 10 for _ in range(10**4*2)]
DP[0] = 0
for i in range(N):
    for j in range(10**4*2):
        if j - AB[i][0] >= 0:
            DP[j] = min(DP[j], DP[j-AB[i][0]] + AB[i][1])
ans = 10**10
for i in range(H, 10**4*2):
    ans = min(ans, DP[i])
print(ans)



Fixed submission:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

H,N = imn()
AB = [iln() for _ in range(N)]
MAX_H = 10**4+1
dp = [10**10 for _ in range(MAX_H)]
dp[0] = 0

for i in range(N):
    for j in range(MAX_H):
        if j - AB[i][0] >= 0:
            dp[j] = min(dp[j], dp[j-AB[i][0]]+AB[i][1])
ans = 10 ** 10
for i in range(H, MAX_H):
    ans = min(ans, dp[i])
print(ans)