Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
line1= input().split(' ')
n= int(line1[0])
m= int(line1[1])

line2= input().split(' ')
hs= []
for h in line2:
	hs.append(int(h))

roads= []
for _ in range(0, m):
	line= input().split(' ')
	roads.append(line)

def is_good(x):
	height= hs[x-1]
	for road in roads:
		if road[0]==str(x):
			if hs[int(road[1])-1]>=height:
				return False
		if road[1]==str(x):
			if hs[int(road[0])-1]>=height:
				return False
	return True

ans= []
for o in range(1,n+1):
	if is_good(o):
		ans.append(o)
print(len(ans))

Fixed submission:
line1= input().split(' ')
n= int(line1[0])
m= int(line1[1])

line2= input().split(' ')
hs= []
for h in line2:
	hs.append(int(h))

roads= []
for _ in range(0, m):
	line= input().split(' ')
	roads.append([int(line[0]),int(line[1])])

graph= {}
for o in range(1, n+1):
	graph[o]=[]

for road in roads:
	graph[road[0]].append(road[1])
	graph[road[1]].append(road[0])


def is_good(x):
	height= hs[x-1]
	for adj in graph[x]:
		if hs[adj-1]>= height:
			return False
	return True
	'''height= hs[x-1]
	for road in roads:
		if road[0]==str(x):
			if hs[int(road[1])-1]>=height:
				return False
		if road[1]==str(x):
			if hs[int(road[0])-1]>=height:
				return False
	return True'''

ans= []
for o in range(1,n+1):
	if is_good(o):
		ans.append(o)

print(len(ans))
Buggy python submission (verdict: Runtime Error):
n= int(input())
l= {}
for _ in range(n):
	s= input()
	l.add(s)
print(len(l))

Fixed submission:
n= int(input())
l= set()
for _ in range(n):
	s= input()
	l.add(s)
print(len(l))

Buggy python submission (verdict: Time Limit Exceeded):
n= int(input())
l= []
for _ in range(n):
	s= input()
	if s in l:
		continue
	else:
		l.append(s)
print(len(l))

Fixed submission:
n= int(input())
l= set()
for _ in range(n):
	s= input()
	l.add(s)
print(len(l))

Buggy python submission (verdict: Time Limit Exceeded):
n= int(input())
l= []
for _ in range(n):
	s= input()
	if s in l:
		pass
	else:
		l.append(s)
print(len(l))

Fixed submission:
n= int(input())
l= set()
for _ in range(n):
	s= input()
	l.add(s)
print(len(l))
Buggy python submission (verdict: Time Limit Exceeded):
import sys

N = int(sys.stdin.readline().strip())
vs = [int(a) for a in sys.stdin.readline().strip().split(" ")]

M = 1000000000 + 7

ret = 0
for j in range(N):
    for i in range(j):
        ret += vs[j] * vs[i]
        ret %= M
print(ret)
	

Fixed submission:
import sys

N = int(sys.stdin.readline().strip())
vs = [int(a) for a in sys.stdin.readline().strip().split(" ")]

M = 1000000000 + 7

ret = 0
sum = 0
for j in range(1, N):
    sum += vs[j - 1]
    ret += (vs[j] * sum) % M
    ret = ret % M
print(ret)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))

result = 0
for i in range(N-1): 
  tmp = 0
  for j in range(i+1, N): 
    tmp += A[j]
  result += tmp * A[i]
print(result%1000000007)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))

sum = sum(A)
result = 0

for i in range(N): 
  sum -= A[i]
  result += sum*A[i]

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

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))

result = 0

for i in range(1, N): 
  for j in range(i+1, N+1): 
    result += A[i-1]*A[j-1]

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

Fixed submission:
N = int(input())
A = list(map(int,input().split()))

sum = sum(A)
result = 0

for i in range(N): 
  sum -= A[i]
  result += sum*A[i]

print(result%(10**9+7))
Buggy python submission (verdict: Runtime Error):
n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    res = 0
for x in ls:
    res *= x
    if res > 10**18:
        res = -1
     	break
print(res)

Fixed submission:
n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    print(0)
    quit()
for x in ls:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    res = 0
for x in ls:
    res *= x
    if res > 10**18:
        res = -1
print(res)

Fixed submission:
n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    print(0)
    quit()
for x in ls:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
a = 0
li = []
for x in range(n):
    li.append(input().split())
    if n - k == 0:
        a = n - 1
    else:
        a = n - k
print(a)

Fixed submission:
N, K = map(int, input().split())
j = 0
ls1 = []
ls2 = []

for i in range(1, K+1):
    d = int(input())
    ls1.append(input().split())
for i in range(len(ls1)):
    for j in ls1[i]:
        ls2.append(j)
        x = set(ls2)
print(N - len(x))
Buggy python submission (verdict: Runtime Error):
a, b, c, d = map(int, input().split())
while True:
	c -= b
	a -= d
    if c <= 0:
        print('Yes')
        break
    if a <= 0:
        print('No')
        break

Fixed submission:
a, b, c, d = map(int, input().split())
while True:
    c -= b
    if c <= 0:
        print('Yes')
        break
    a -= d
    if a <= 0:
        print('No')
        break
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = list(map(int, input().split()))
daytofinish = sum(A)
print(N-daytofinish)
N, M = map(int, input().split())
A = list(map(int, input().split()))
daytofinish = sum(A)
if N-daytofinish < 0:
    print(-1)
else:
    print(N-daytofinish)

Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
daytofinish = sum(A)
if N-daytofinish < 0:
    print(-1)
else:
    print(N-daytofinish)

Buggy python submission (verdict: Runtime Error):
n, m = map(int, input.split())
a = list(map(int, input.split()))
final = sum(a)
if n > 0:
    print(n - a)
else:
    print(-1)
    

Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
daytofinish = sum(A)
if N-daytofinish < 0:
    print(-1)
else:
    print(N-daytofinish)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
N = (N - K)
container = []
result = 0
for i in range(int(N)):
    result = abs(i - N)
    container.append(result)
print(container[-1])

Fixed submission:
n, k = map(int, input().split())
if n==0 or k==1:
    print(0)
    exit()
elif n<k:
    print(min(n, abs(n-k)))
    exit()
elif n % k == 0:
    print(0)
    exit()
else:
    mx = n%k
print(min(abs(mx-k), mx))

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
N = (N - K)
container = []
result = 0
for i in range(int(N)):
    result = abs(i - N)
    container.append(result)
print(min(container))

Fixed submission:
n, k = map(int, input().split())
if n==0 or k==1:
    print(0)
    exit()
elif n<k:
    print(min(n, abs(n-k)))
    exit()
elif n % k == 0:
    print(0)
    exit()
else:
    mx = n%k
print(min(abs(mx-k), mx))
Buggy python submission (verdict: Runtime Error):
container = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
unser = int(input())
print(container[unser])

Fixed submission:
container = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
unser = int(input())
print(container[unser - 1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
table = [[int(i) for i in input().split()] for N in range(N)]

n = 0
for i in range(N):
    for j in range(i):
        if n < abs(table[i][0]-table[j][0]) + abs(table[i][1]-table[j][1]):
            n = abs(table[i][0]-table[j][0]) + abs(table[i][1]-table[j][1])

print(n)


Fixed submission:
N = int(input())
table = [[int(i) for i in input().split()] for N in range(N)]

a = -1
b = 10**10
c = -10**10
d = 10**10
for i in range(N):
    p = table[i][0]
    q = table[i][1]
    if a < p+q:
        a = p+q
    if b > p+q:
        b = p+q
    if c < p-q:
        c = p-q
    if d > p-q:
        d = p-q

print(max(a-b,c-d))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(x) for x in input().split()]

gokei = 0
for i in range(len(A)):
    gokei += A[i] * sum(A)
    gokei -= A[i] * A[i]
gokei = gokei // 2
ans = gokei % 1000000007
print(ans)


Fixed submission:
N = int(input())
A = [int(x) for x in input().split()]

gokei = sum(A) ** 2
for i in range(len(A)):
    gokei -= A[i] * A[i]
gokei = gokei // 2
ans = gokei % 1000000007
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
B = [[int(i) for i in input().split()] for Q in range(Q)]

p = [0]*100000
for i in range(N):
    p[A[i]] += 1

cnt = 0
for j in range(100000):
    cnt += p[j]*j

for i in range(Q):
    cnt = cnt + (B[i][1]- B[i][0]) * p[B[i][0]]
    
    p[B[i][1]] += p[B[i][0]]
    p[B[i][0]] = 0

    print(cnt)


Fixed submission:
N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
B = [[int(i) for i in input().split()] for Q in range(Q)]

p = [0]*100001
for i in range(N):
    p[A[i]] += 1

cnt = 0
for j in range(100001):
    cnt += p[j]*j

for i in range(Q):
    cnt = cnt + (B[i][1]- B[i][0]) * p[B[i][0]]

    p[B[i][1]] += p[B[i][0]]
    p[B[i][0]] = 0

    print(cnt)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
B = [[int(i) for i in input().split()] for Q in range(Q)]

p = [0]*100000
for i in range(N):
    p[A[i]] += 1

for i in range(Q):
    p[B[i][1]] += p[B[i][0]]
    p[B[i][0]] = 0

    cnt = 0
    for j in range(100000):
        cnt += p[j]*j
    print(cnt)


Fixed submission:
N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
B = [[int(i) for i in input().split()] for Q in range(Q)]

p = [0]*100001
for i in range(N):
    p[A[i]] += 1

cnt = 0
for j in range(100001):
    cnt += p[j]*j

for i in range(Q):
    cnt = cnt + (B[i][1]- B[i][0]) * p[B[i][0]]

    p[B[i][1]] += p[B[i][0]]
    p[B[i][0]] = 0

    print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
list1 = []
for i in range(N):
    taisho = input()
    if not taisho in list1:
        list1.append(taisho)
print(len(list1))


Fixed submission:
N = int(input())
list1 = set()
for i in range(N):
    taisho = input()
    if not taisho in list1:
        list1.add(taisho)
print(len(list1))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
num = 0
list1 = []
for i in range(N):
    taisho = input()
    if not taisho in list1:
        num += 1
        list1.append(taisho)
print(num)


Fixed submission:
N = int(input())
list1 = set()
for i in range(N):
    taisho = input()
    if not taisho in list1:
        list1.add(taisho)
print(len(list1))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
num = 0
list1 = []
for i in range(N):
    list1.append(input())
    flg = 0
    for j in range(i):
        if list1[i]==list1[j]:
            flg = 1
    if flg == 0:
        num += 1
print(num)


Fixed submission:
N = int(input())
list1 = set()
for i in range(N):
    taisho = input()
    if not taisho in list1:
        list1.add(taisho)
print(len(list1))
Buggy python submission (verdict: Runtime Error):
X,Y,A,B,C = (int(x) for x in input().split())
p = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
r = [int(x) for x in input().split()]

p = sorted(p, reverse=True)
q = sorted(q, reverse=True)
r = sorted(r, reverse=True)

r.append(0)
for i in range(X,A):
    p[i] = 0
for i in range(Y,B):
    q[i] = 0

a = 0
b = 0
c = 0
cnt = 0

for i in range(X+Y):
    if (not a == X) and p[a] >= q[b] and p[a] >= r[c]:
        cnt += p[a]
        a += 1
    elif (not b == Y) and q[b] >= r[c]:
        cnt += q[b]
        b += 1
    else:
        cnt += r[c]
        c += 1
print(cnt)


Fixed submission:
X,Y,A,B,C = (int(x) for x in input().split())
p = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
r = [int(x) for x in input().split()]

p = sorted(p, reverse=True)
q = sorted(q, reverse=True)
r = sorted(r, reverse=True)

p.append(0)
q.append(0)
r.append(0)
for i in range(X,A):
    p[i] = 0
for i in range(Y,B):
    q[i] = 0

a = 0
b = 0
c = 0
cnt = 0

for i in range(X+Y):
    if (not a == X) and p[a] >= q[b] and p[a] >= r[c]:
        cnt += p[a]
        a += 1
    elif (not b == Y) and q[b] >= r[c]:
        cnt += q[b]
        b += 1
    else:
        cnt += r[c]
        c += 1
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
# input
N, K = map(int, input().split())
A = list(map(int, input().split()))

# process
l = [1]
now = A[0]
while not now in l:
    l.append(now)
    now = A[now-1]

ti = l.index(now)

ans = 0
if K < ti:
    ans = l[K]
else:
    k = (K-ti)%(len(l)-ti)
    ans = l[ti+k]

# output
print(ans)


Fixed submission:
# input
N, K = map(int, input().split())
A = [0]
A.extend(list(map(int, input().split())))

# process
l = [0]*(N+1)
now = 1
i = 1
while l[now] == 0:
    l[now] = i
    now = A[now]
    i += 1

ans = 0
if K < l[now]:
    ans = l.index(K+1)
else:
    k = (K-l[now]+1)%(len([x for x in l if x!=0])-l[now]+1)
    ans = l.index(l[now]+k)

# output
print(ans)
Buggy python submission (verdict: Runtime Error):
# input
N = int(input())
S = [input() for _ in range(N)]

# process
l1 = []
l2 = []
for s in S:
    i=0
    a = 0
    b = 0
    while i < len(s) and s[i] == ')':
        a += 1
        i += 1
    while i < len(s):
        if s[i] == '(':
            b += 1
        else:
            b -= 1
        i += 1
    
    if a+b != 0:
        if a <= b:
            l1.append((a, b))
        else:
            l2.append((b, a))

l1.sort()
l2.sort(reverse=True)

result = False
x = 0
if l1[0][0] == 0 and l2[-1][0] == 0:
    for a, b in l1:
        x += b-a
    for b, a in l2:
        x += b-a

    if x == 0:
        result = True

# output
print("Yes" if result else "No")


Fixed submission:
# input
N = int(input())
S = [input() for _ in range(N)]

# process
T = []
for s in S:
    while '()' in s:
        s = s.replace('()', '')
    T.append(s)

l1 = []
l2 = []
for t in T:
    op = t.find('(')
    if op < 0:
        op = len(t)
    cl = len(t) - op
    
    if cl+op != 0:
        if cl <= op:
            l1.append((cl, op))
        else:
            l2.append((op, cl))

l1.sort()
l2.sort(reverse=True)

result = False
x = 0
if len(l1)+len(l2) == 0:
    result = True
elif len(l1)>0 and len(l2)>0 and l1[0][0]+l2[-1][0] == 0:
    for cl, op in l1:
        x -= cl
        if x < 0:
            break
        x += op
    
    if x >= 0:
        for op, cl in l2:
            x -= cl
            if x < 0:
                break
            x += op
            
        if x == 0:
            result = True

# output
print("Yes" if result else "No")
Buggy python submission (verdict: Runtime Error):
# input
X = int(input())

# process
a, b = 0, 0

nl = []
i = 0
np = 0
n = i**5
while n - np <= 10**9:
    nl.append(n)
    i += 1
    np = n
    n = i**5

for i in range(len(nl)):
    t = X-nl[i]
    if t in nl:
        a = i
        b = -(nl.index(X-nl[i]))
        break

    if -t in nl:
        a = i
        b = nl.index(X-nl[i])
        break

# output
print("{} {}".format(a, b))


Fixed submission:
# input
X = int(input())

# process
a, b = 0, 0

nl = []
i = 0
np = 0
n = i**5
while n - np <= 10**9:
    nl.append(n)
    i += 1
    np = n
    n = i**5

for i in range(len(nl)):
    t = X-nl[i]
    if t in nl:
        a = i
        b = -(nl.index(t))
        break

    if -t in nl:
        a = i
        b = nl.index(-t)
        break

# output
print("{} {}".format(a, b))
Buggy python submission (verdict: Time Limit Exceeded):
# input
N = int(input())
A = list(map(int, input().split()))

# define combination
fact = [1, 1]
combs = [0, 0]
for i in range(2, N+1):
    fact.append(fact[-1]*i)
    combs.append(fact[i] // (fact[i - 2] * 2))

# process
nums = [0]*(N+1)
for a in A:
    nums[a] += 1

sumall = 0
for n in nums:
    sumall += combs[n]

ans = [sumall]*N
for i, a in enumerate(A):
    ans[i] += combs[nums[a]-1] - combs[nums[a]]

# output
for a in ans:
    print(a)


Fixed submission:
# input
N = int(input())
A = list(map(int, input().split()))

# define combination
combs = [0, 0]
for i in range(2, N+1):
    combs.append(i*(i-1)//2)

# process
nums = [0]*(N+1)
for a in A:
    nums[a] += 1

sumall = 0
for n in nums:
    sumall += combs[n]

ans = [sumall]*N
for i, a in enumerate(A):
    n = nums[a]
    ans[i] += combs[n-1] - combs[n]

# output
for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
# input
N = int(input())
A = list(map(int, input().split()))

# define combination
fact = [1, 1]
for i in range(2, N+1):
    fact.append(fact[-1]*i)
combs = [0, 0]
for n in range(2, N+1):
    combs.append(fact[n] // (fact[n - 2] * 2))

# process
nums = [0]*(N+1)
for a in A:
    nums[a] += 1

sumall = 0
for n in nums:
    sumall += combs[n]

ans = []
for i, a in enumerate(A):
    ans.append(sumall - combs[nums[a]] + combs[nums[a]-1])

# output
for a in ans:
    print(a)


Fixed submission:
# input
N = int(input())
A = list(map(int, input().split()))

# define combination
combs = [0, 0]
for i in range(2, N+1):
    combs.append(i*(i-1)//2)

# process
nums = [0]*(N+1)
for a in A:
    nums[a] += 1

sumall = 0
for n in nums:
    sumall += combs[n]

ans = [sumall]*N
for i, a in enumerate(A):
    n = nums[a]
    ans[i] += combs[n-1] - combs[n]

# output
for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
# input
N = int(input())
A = list(map(int, input().split()))

# define combination
fact = [1, 1]
for i in range(2, N+1):
    fact.append(fact[-1]*i)
def comb(n, r):
    return fact[n] // (fact[n - r] * fact[r])

# process
nums = [0]*(N+1)
combs = [0]*(N+1)
for a in A:
    nums[a] += 1

for i, n in enumerate(nums):
    combs[i] = comb(n, 2)

sumall = sum(combs)

ans = []
for i, a in enumerate(A):
    ans.append(sumall - combs[a] + comb(nums[a]-1, 2))

# output
for a in ans:
    print(a)


Fixed submission:
# input
N = int(input())
A = list(map(int, input().split()))

# define combination
combs = [0, 0]
for i in range(2, N+1):
    combs.append(i*(i-1)//2)

# process
nums = [0]*(N+1)
for a in A:
    nums[a] += 1

sumall = 0
for n in nums:
    sumall += combs[n]

ans = [sumall]*N
for i, a in enumerate(A):
    n = nums[a]
    ans[i] += combs[n-1] - combs[n]

# output
for a in ans:
    print(a)
Buggy python submission (verdict: Runtime Error):
# input
N, M, K = map(int, input().split())

Frends = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a < b:
        Frends[a].append(b)
    else:
        Frends[b].append(a)

Blocked = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if c < d:
        Blocked[c].append(d)
    else:
        Blocked[d].append(c)

# process
# 友人グループを作成
fg = []
for i in range (N):
    fs = Frends[i]
    for f in fs:
        t = -1

        j = 0
        fglen = len(fg)
        while j < fglen:
            g = fg[j]
            if i in g and f in g:
                if t < 0:
                    t = j              
                else:
                    fg[t] = fg[t] | g
                    fg.pop(j)
                    fglen -= 1
            elif not (i in g or f in g):
                j += 1
                continue
            else:
                if t < 0:
                    if i in g:
                        g.add(f)
                    else:
                        g.add(i)

                    t = j
                else:
                    fg[t] = fg[t] | g
                    fg.pop(j)
                    fglen -= 1
            j += 1
            
        if t < 0:
            fg.append(set([i, f]))

# 友人候補を抽出
cand = []
for i in range(N):
    for g in fg:
        if i in g:
            for f in g:
                if i < f and not f in Frends[i] and not f in Blocked[i]:
                    cand.append((i, f,))

# 友人候補をカウント
ans = [0 for _ in range(N)]
for c in cand:
    a, b = c
    ans[a] += 1
    ans[b] += 1

# output
#print(fg)
#print(cand)
print(" ".join(map(str, ans)))


Fixed submission:
# input
N, M = map(int, input().split())

SC = []
for _ in range(M):
    SC.append(tuple(map(int, input().split())))

# process
ans = 0

A = [-1 for _ in range(N)]

for s, c in SC:
    s -= 1
    if s == 0 and c == 0 and N > 1:
        ans = -1
        break
    elif A[s] == -1:
        A[s] = c
    elif A[s] != c:
        ans = -1
        break

if ans != -1:
    if A[0] == -1 and N > 1:
        A[0] = 1
    for i in range(0, N):
        if A[i] == -1:
            A[i] = 0

    A = A[::-1]
    for i in range(N):
        ans += A[i]*(10**i)

# output
print(ans)
Buggy python submission (verdict: Runtime Error):
# input
N = int(input())
X = list(map(int, input().split()))

# process/output
L = min(X)
R = max(X)

ans = int(float('inf'))
for i in range(L, R+1):
    cost = 0
    for x in X:
        cost += (x-i)**2
    
    if cost < ans:
        ans = cost

print(ans)


Fixed submission:
# input
N = int(input())
X = list(map(int, input().split()))

# process
L = min(X)
R = max(X)

ans = float('inf')
for i in range(L, R+1):
    cost = 0
    for x in X:
        cost += (x-i)**2
    
    if cost < ans:
        ans = cost

# output
print(int(ans))
Buggy python submission (verdict: Runtime Error):
# input
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

# process
INF = 10**9
dp = [INF]*(H+max(a for a, _ in AB))
dp[0] = 0

for i in range(H):
    if dp[i] == INF:
        continue
    for a, b in AB:
        t = dp[i]+b
        if dp[i+a] > t:
            dp[i+a] = t

# output
print(min(dp[H:]))


Fixed submission:
# input
H, A = map(int, input().split())

# output
if H%A == 0: print(H//A)
else: print(H//A+1)
Buggy python submission (verdict: Time Limit Exceeded):
# input
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

# process
INF = 10**9
dp = [INF]*(H+max(a for a, _ in AB))
dp[0] = 0

for i in range(H):
    if dp[i] == INF:
        continue
    for a, b in AB:
        t = dp[i]+b
        if dp[i+a] > t:
            dp[i+a] = t

# output
print(min(dp[H:]))


Fixed submission:
import numpy as np

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

AB = [list(map(int, input().split())) for _ in range(N)]
A, B = np.array(AB, dtype=np.int64).reshape(N, 2).T

# process
dp = np.zeros(H+1, dtype=np.int64)
dp[0] = 0

for i in range(1, H + 1):
    dp[i] = np.amin(dp[np.maximum(i - A, 0)] + B)

# output
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
# input
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

# process
max_a = max(a for a, _ in AB)
dp = [10**9]*(H+max_a)
dp[0] = 0

for i in range(H):
    if dp[i] == 10**9:
        continue
    for a, b in AB:
        t = dp[i]+b
        if dp[i+a] > t:
            dp[i+a] = t

# output
print(min(dp[H:]))


Fixed submission:
import numpy as np

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

AB = [list(map(int, input().split())) for _ in range(N)]
A, B = np.array(AB, dtype=np.int64).reshape(N, 2).T

# process
dp = np.zeros(H+1, dtype=np.int64)
dp[0] = 0

for i in range(1, H + 1):
    dp[i] = np.amin(dp[np.maximum(i - A, 0)] + B)

# output
print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
# input
H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

# process
max_a = max(A)
dp = [10**9]*(H+max_a)
dp[0] = 0

for i in range(H):
    if dp[i] == 10**9:
        continue
    for j in range(N):
        t = dp[i]+B[j]
        if dp[i+A[j]] > t:
            dp[i+A[j]] = t

# output
print(min(dp[H:]))


Fixed submission:
import numpy as np

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

AB = [list(map(int, input().split())) for _ in range(N)]
A, B = np.array(AB, dtype=np.int64).reshape(N, 2).T

# process
dp = np.zeros(H+1, dtype=np.int64)
dp[0] = 0

for i in range(1, H + 1):
    dp[i] = np.amin(dp[np.maximum(i - A, 0)] + B)

# output
print(dp[H])