Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
#m-solutions2020 c
import sys,
input = sys.stdin.readline

N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
for i in range(K,N):
    if A[i]>A[i-K]:
        print('Yes')
    else:
        print('No')



Fixed submission:
#m-solutions2020 c
import sys
input = sys.stdin.readline


N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
for i in range(K,N):
    if A[i]>A[i-K]:
        print('Yes')
    else:
        print('No')

Buggy python submission (verdict: Time Limit Exceeded):
#m-solutions2020 c
import sys,math,collections,itertools
input = sys.stdin.readline

N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
ans = 1
for i in range(K):
    ans *= A[i]
pre = ans
for i in range(K,N):
    now = pre * A[i]//A[i-K]
    if now > pre:
        print('Yes')
    else:
        print('No')
    pre = now




Fixed submission:
#m-solutions2020 c
import sys
input = sys.stdin.readline


N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
for i in range(K,N):
    if A[i]>A[i-K]:
        print('Yes')
    else:
        print('No')
Buggy python submission (verdict: Runtime Error):
#AIsing2020 d
 
import sys,math,collections,itertools,copy
input = sys.stdin.readline
 
 
def popcount(n):
    bin_str = bin(n)
    cou1 = bin_str.count('1')
    return cou1
 
def count(nc):
    co = 0
    while nc >0:
        cou1 = popcount(nc)
        nc = nc%cou1
        co +=1
    return co
 
N = int(input())
X = list(input().rstrip())
 
for i in range(N):
    Y = copy.copy(X)
    if Y[i] == '1':
        Y[i] = '0'
    else:
        Y[i] = '1'
    s = '0b'+"".join(Y)
    a =int(s,2)
    co = count(a)
    print(co)

Fixed submission:
#AIsing2020 a

import sys,math,collections,itertools
input = sys.stdin.readline

L,R,d = list(map(int,input().split()))

if L%d ==0:
    print(R//d-L//d+1)
else:
    print(R//d-L//d)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N,M,K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))

sumA = sum(A)
countA = len(A)
ans = 0
for i in range(N,-1,-1):
    if i != N:
        sumA -= A[i]
        countA -= 1
    time = sumA
    
    if time > K:
        count = 0
    else:
        count = countA
    j=0
    while time+B[j] <=K:
        count += 1
        time += B[j]
        j += 1
        if j >= M:
            break
        #print(count,time,B[i])
    ans = max(ans,count)
print(ans)
        



Fixed submission:
import sys
input = sys.stdin.readline

N,M,K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))

time = sum(A)
count = len(A)
ans = 0
j=0
for i in range(N,-1,-1):
    if i != N:
        time -= A[i]
        count -= 1
    if time>K:
        continue
    if time <= K and j<M:
        while time+B[j] <=K:
            time +=B[j]
            j +=1
            count +=1
            if j >=M:
                break
    ans = max(ans,count)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
N =int(input())
N_kfk = []
kfk = []
for j in range(1,N+1):
    #Nの約数の個数を求める
    N_k = []
    for i in range(1,j+1):
        if i>j**0.5:
            break
        if j % i == 0:
            N_k.append(i)
            N_k.append(j//i)
    set_n = len(set(N_k))
    #print(N_k)
    #Nの約数の個数求めるの終わり
    N_kfk.append(set_n*j)
    #kfk.append(set_n)
print(sum(N_kfk))


Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
ans = 0
for i in range(1,N+1):
    n = N//i
    ans += i * n*(n+1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
x,n = map(int,input().split())
mp = set(range(1,101))
p = set(list(map(int,input().split())))
lp = list(mp-p)
sub_lp = [abs(i-x) for i in lp]
print(lp[sub_lp.index(min(sub_lp))])

Fixed submission:
x,n = map(int,input().split())
if n == 0:
    print(x)
else:
    mp = set(range(-1,102))
    p = set(list(map(int,input().split())))
    lp = list(mp-p)
    sub_lp = [abs(i-x) for i in lp]
    print(lp[sub_lp.index(min(sub_lp))])
Buggy python submission (verdict: Runtime Error):
import collections
N = int(input())
A = sorted(list(map(int,input().split())))

li = [1]*(max(A)+1)
for j in range(N):
    for i in range(A[j]*2,A[-1]+1,A[j]):
        li[i] = 0
    if j == 0:
        if A[j] == A[j+1]:
            li[A[j]]= 0
    elif j == N-1:
        if A[j] == A[j-1]:
             li[A[j]]= 0
    else:
        if A[j] == A[j+1] or A[j] == A[j-1]:
             li[A[j]]= 0
sA = sum([li[i] for i in A])
print(sA)

Fixed submission:
import collections
N = int(input())
A = sorted(list(map(int,input().split())))
cA = collections.Counter(A)

li = [1]*(max(A)+1)
for j in range(N):
    for i in range(A[j]*2,A[-1]+1,A[j]):
        li[i] = 0

for key,val in cA.items():
    if val >1:
        li[key]=0
        
sA = sum([li[i] for i in A])
print(sA)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = sorted(list(map(int,input().split())))
cnt = 0
ln = set()
for i in range(N):
    tmp = A[i]
    if i == 0 and A[i] == A[i+1]:
        cnt = 0
        ln = ln | set(range(A[i],A[-1]+1,A[i]))
    elif i == 0 and A[i] != A[i+1]:
        cnt +=1
        ln = ln | set(range(A[i],A[-1]+1,A[i]))
    else:
        if A[i] not in ln:
            cnt +=1
    ln = ln | set(range(A[i],A[-1]+1,A[i]))
print(cnt)


Fixed submission:
import collections
N = int(input())
A = sorted(list(map(int,input().split())))
cA = collections.Counter(A)

li = [1]*(max(A)+1)
for j in range(N):
    for i in range(A[j]*2,A[-1]+1,A[j]):
        li[i] = 0

for key,val in cA.items():
    if val >1:
        li[key]=0
        
sA = sum([li[i] for i in A])
print(sA)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = sorted(list(map(int,input().split())))
cnt = 0
for i in range(N):
    tmp = A[i]
    if i == 0:
        if A[0]==A[1]:
            continue
    elif i == N-1:
        if A[-1]==A[-2]:
            continue
    else:
        if A[i-1]== A[i] or A[i] == A[i+1]:
            continue
    flag = 0
    for j in range(i):
        if A[j]*2 > A[i]:
            break
        else:
            #print(A[j],A[i])
            if A[i]%A[j]== 0:
                flag = 1
                break
            else:
                continue
    #print(A[i],flag)
    if flag == 0:
        #print(A[i])
        cnt +=1
print(cnt)
    


Fixed submission:
import collections
N = int(input())
A = sorted(list(map(int,input().split())))
cA = collections.Counter(A)

li = [1]*(max(A)+1)
for j in range(N):
    for i in range(A[j]*2,A[-1]+1,A[j]):
        li[i] = 0

for key,val in cA.items():
    if val >1:
        li[key]=0
        
sA = sum([li[i] for i in A])
print(sA)
Buggy python submission (verdict: Runtime Error):
A,V = map(int,input().split())
B,W= map(int,input().split())
T = int(input()
dist = abs(A-B)
vec = V-W
print('Yes' if vec*T >= dist else 'NO')

Fixed submission:
A,V = map(int,input().split())
B,W= map(int,input().split())
T = int(input())
dist = abs(A-B)
vec = V-W
print('YES' if vec*T >= dist else 'NO')
Buggy python submission (verdict: Time Limit Exceeded):
import sys,math,collections,itertools
input = sys.stdin.readline
from numba import jit

N,K=list(map(int,input().split()))
A = list(map(int,input().split()))

@jit
def solve(N,K,A):
    for i in range(K):
        imo = [0]*(N+1)
        flag = 1
        for j in range(N):
            imo[max(0,j-A[j])] += 1
            imo[min(N,j+A[j]+1)] -= 1
            if j-A[j]>0 or j+A[j]+1<N:
                flag = 0
        A = list(itertools.accumulate(imo))[:-1]
        if flag == 1:
            break
    return A

A = solve(N,K,A)
print(*A)


Fixed submission:
import sys,math,collections,itertools
input = sys.stdin.readline

N,K=list(map(int,input().split()))
A = list(map(int,input().split()))

for i in range(K):
    imo = [0]*(N+1)
    flag = 1
    for j in range(N):
        imo[max(0,j-A[j])] += 1
        imo[min(N,j+A[j]+1)] -= 1
        if j-A[j]>0 or j+A[j]+1<N:
            flag = 0
    A = list(itertools.accumulate(imo))[:-1]
    if flag == 1:
        break
print(*A)

Buggy python submission (verdict: Time Limit Exceeded):
import sys,math,collections,itertools
input = sys.stdin.readline

N,K=list(map(int,input().split()))
A = list(map(int,input().split()))

for i in range(K):
    imo = [0]*(N+1)
    flag = 1
    for j in range(N):
        imo[max(0,j-A[j])] += 1
        imo[min(N,j+A[j]+1)] -= 1
        if j-A[j]>0 or j+A[j]+1<N:
            flag = 0
    A = list(itertools.accumulate(imo))[:-1]
    if flag == 1:
        break
print(*A)


Fixed submission:
import sys,math,collections,itertools
input = sys.stdin.readline

N,K=list(map(int,input().split()))
A = list(map(int,input().split()))

for i in range(K):
    imo = [0]*(N+1)
    flag = 1
    for j in range(N):
        imo[max(0,j-A[j])] += 1
        imo[min(N,j+A[j]+1)] -= 1
        if j-A[j]>0 or j+A[j]+1<N:
            flag = 0
    A = list(itertools.accumulate(imo))[:-1]
    if flag == 1:
        break
print(*A)
Buggy python submission (verdict: Runtime Error):
import math
a,b=input().split()
b=int(float(b)*100)
s=(int(a)*b)
print(str(s[:-2]) if s>99 else 0)

Fixed submission:
import math
a,b=input().split()
c=int(a)
d1=100*c*int(b[0])
d2=10*c*int(b[2])
d3=1*c*int(b[3])
ds=d1+d2+d3
if ds<100:
  print(0)
else:
  print(str(ds)[:-2])

Buggy python submission (verdict: Runtime Error):
import math
a,b=input().split()
b=int(float(b)*100)
s=(int(a)*b)
print(srr(s[:-2]) if s>99 else 0)

Fixed submission:
import math
a,b=input().split()
c=int(a)
d1=100*c*int(b[0])
d2=10*c*int(b[2])
d3=1*c*int(b[3])
ds=d1+d2+d3
if ds<100:
  print(0)
else:
  print(str(ds)[:-2])
Buggy python submission (verdict: Time Limit Exceeded):
import sys,math,collections,itertools
input = sys.stdin.readline

N,K=list(map(int,input().split()))
A =[0]+list(map(int,input().split()))
town = 1
town_list = [1]
count = 0
while True:
    town = A[town]
    count +=1
    if count == K:
        print(town)
        exit()
    if town not in town_list:
        town_list.append(town)
    else:
        roop_town_num = town
        break
    
l_ini_index = town_list.index(roop_town_num)
len_roop = len(town_list)-l_ini_index 

if K <= l_ini_index:
    print(town_list[K])
else:
    print(town_list[((K-l_ini_index)%len_roop+l_ini_index)])
    


Fixed submission:
import sys,math,collections,itertools
input = sys.stdin.readline

N,K=list(map(int,input().split()))
A =[0]+list(map(int,input().split()))
town = 1
town_list = [1]
towntown = [0]*(N+1)
towntown[1]=1
count = 0
while True:
    town = A[town]
    count +=1
    if count == K:
        print(town)
        exit()
    if towntown[town] == 0:
        town_list.append(town)
        towntown[town] =1
    else:
        roop_town_num = town
        break
    
l_ini_index = town_list.index(roop_town_num)
len_roop = len(town_list)-l_ini_index 

if K <= l_ini_index:
    print(town_list[K])
else:
    print(town_list[((K-l_ini_index)%len_roop+l_ini_index)])

Buggy python submission (verdict: Runtime Error):
import sys,math,collections,itertools
input = sys.stdin.readline

N,K=list(map(int,input().split()))
A =[0]+list(map(int,input().split()))
town = 1
town_list = [1]
while True:
    town = A[town]
    if town not in town_list:
        town_list.append(town)
    else:
        roop_town_num = town
        break
    
l_ini_index = town_list.index(roop_town_num)
len_roop = len(town_list)-l_ini_index 

if K <= l_ini_index:
    print(town_lis[K])
else:
    print(town_list[((K-l_ini_index)%len_roop+l_ini_index)])
    


Fixed submission:
import sys,math,collections,itertools
input = sys.stdin.readline

N,K=list(map(int,input().split()))
A =[0]+list(map(int,input().split()))
town = 1
town_list = [1]
towntown = [0]*(N+1)
towntown[1]=1
count = 0
while True:
    town = A[town]
    count +=1
    if count == K:
        print(town)
        exit()
    if towntown[town] == 0:
        town_list.append(town)
        towntown[town] =1
    else:
        roop_town_num = town
        break
    
l_ini_index = town_list.index(roop_town_num)
len_roop = len(town_list)-l_ini_index 

if K <= l_ini_index:
    print(town_list[K])
else:
    print(town_list[((K-l_ini_index)%len_roop+l_ini_index)])
Buggy python submission (verdict: Time Limit Exceeded):
N,M,K = map(int,input().split())
m = 998244353
ans = (M*pow(M-1,N-1,m))%m
alpha = 1
for k in range(1,K+1):
    alpha = alpha*(N-k)//(k)
    ans = (ans + M*alpha*pow(M-1,N-k-1,m))%m
print(ans)


Fixed submission:
N,M,K = map(int,input().split())
m = 998244353
ans = (M*pow(M-1,N-1,m))%m
alpha = 1
for k in range(1,K+1):
    alpha = (alpha*(N-k)*pow(k,m-2,m))%m
    ans = (ans + M*alpha*pow(M-1,N-k-1,m))%m
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,M,K = map(int,input().split())
m = 998244353
ans = (M*pow(M-1,N-1,m))%m
alpha = 1
for k in range(1,K+1):
    alpha = alpha*(N-k)//(k)
    ans = (ans + M*alpha*pow(M-1,N-k-1,m))%m
print(ans)


Fixed submission:
N,M,K = map(int,input().split())
m = 998244353
ans = (M*pow(M-1,N-1,m))%m
alpha = 1
for k in range(1,K+1):
    alpha = (alpha*(N-k)*pow(k,m-2,m))%m
    ans = (ans + M*alpha*pow(M-1,N-k-1,m))%m
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
X= int(input())
 
Bp = -1*math.floor(X**0.2)
Bn = 0
while True:
    Bp += 1
    A = (X+Bp**5)**0.2
    if A == int(A):
        print(int(A),Bp)
        exit()

Fixed submission:
import math

X= int(input())

for A in range(-120,121):
    for B in range(-120,A+1):
        if A**5-B**5  == X:
            print(A,B)
            exit()

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

Bp = -1*math.floor(X**0.2)
Bn = 0
while True:
    Bp += 1
    A = (X+Bp**5)**0.2
    if A == int(A):
        print(int(A),Bp)
        exit()


Fixed submission:
import math

X= int(input())

for A in range(-120,121):
    for B in range(-120,A+1):
        if A**5-B**5  == X:
            print(A,B)
            exit()

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

Bp = 0
Bn = 0
while True:
    Bp += 1
    A = (X+Bp**5)**0.2
    if A == int(A):
        print(A,Bp)
        exit()

    Bn -= 1
    A = (X+Bn**5)**0.2
    if A == int(A):
        print(int(A),Bn)
        exit()


Fixed submission:
import math

X= int(input())

for A in range(-120,121):
    for B in range(-120,A+1):
        if A**5-B**5  == X:
            print(A,B)
            exit()
Buggy python submission (verdict: Time Limit Exceeded):
import sys,math,collections,itertools
input = sys.stdin.readline

S=input().rstrip()
cnt = 0
for i in range(len(S)-3):
    mul3 =0
    num = 0
    for j in range(i,len(S)):
        mul3 = (mul3 + int(S[j]))%3
        num = num*10+int(S[j])
        if mul3 == 0:
            if num%2019 ==0:
                cnt += 1
print(cnt)


Fixed submission:
import sys,math,collections,itertools
input = sys.stdin.readline

S=input().rstrip()
Smod2019=[0]
num = 0
deg = 0
for i in range(len(S)-1,-1,-1):
    num = (num+int(S[i])*pow(10,deg,2019))%2019
    Smod2019.append(num)
    deg += 1
Sc = collections.Counter(Smod2019)

cnt = 0
for val in Sc.values():
    cnt += val*(val-1)//2
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
import sys,math,collections,itertools
input = sys.stdin.readline

S=input().rstrip()
cnt = 0
for i in range(len(S)-3):
    mul3 =0
    num = 0
    for j in range(i,len(S)):
        mul3 = (mul3 + int(S[j]))%3
        num = num*10+int(S[j])
        if mul3 == 0:
            if num%2019 ==0:
                cnt += 1
print(cnt)


Fixed submission:
import sys,math,collections,itertools
input = sys.stdin.readline

S=input().rstrip()
Smod2019=[0]
num = 0
deg = 0
for i in range(len(S)-1,-1,-1):
    num = (num+int(S[i])*pow(10,deg,2019))%2019
    Smod2019.append(num)
    deg += 1
Sc = collections.Counter(Smod2019)

cnt = 0
for val in Sc.values():
    cnt += val*(val-1)//2
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A =list(map(int,input().split()))
for i in range(1,n+1):
    print(A.count(i))


Fixed submission:
import collections
n = int(input())
A = list(map(int,input().split()))
Ac = collections.Counter(A)
for i in range(1,n+1):
    if i in Ac.keys():
        print(Ac[i])
    else:
        print(0)
Buggy python submission (verdict: Time Limit Exceeded):
import collections
n,x,y = map(int,input().split())
h = [[] for _ in range(n+1) ]
for i in range(1,n+1):
    if i+1<n+1:
        h[i].append(i+1)
    if i-1>0:
        h[i].append(i-1)
h[x].append(y)
h[y].append(x)

k = [0]*n
for i in range(1,n+1):
    q = collections.deque([i])
    step = [-1]*(n+1)
    step[i] = 0
    while q:
        now = q.popleft()
        for hh in h[now]:
            if step[hh] == -1:
                q.append(hh)
                step[hh] = step[now]+1
                k[step[now]+1] += 1
for i in range(1,n):
    print(k[i]//2)

Fixed submission:
import collections
n,x,y = map(int,input().split())
h = [[] for _ in range(n+1) ]
for i in range(1,n+1):
    if i+1<n+1:
        h[i].append(i+1)
    if i-1>0:
        h[i].append(i-1)
h[x].append(y)
h[y].append(x)

k = [0]*n
for i in range(1,n+1):
    q = collections.deque([i])
    step = [-1]*(n+1)
    step[i] = 0
    while q:
        now = q.popleft()
        for hh in h[now]:
            if step[hh] == -1:
                q.append(hh)
                step[hh] = step[now]+1
                k[step[now]+1] += 1
for i in range(1,n):
    print(k[i]//2)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
Q = int(input())

rev_count = 0
for i in range(Q):
    que = input()
    if que[0] == '1':
        rev_count +=1
    elif que[0] == '2':
        if (rev_count + int(que[2]))%2 == 0:
            s = s + que[4]
        else:
            s = que[4] + s

print(s if rev_count %2 == 0 else s[-1::-1])


Fixed submission:
s = input()
Q = int(input())

rev_count = 0
sbf=''
saf=''
for i in range(Q):
    que = input()
    if que[0] == '1':
        rev_count +=1
    elif que[0] == '2':
        if (rev_count + int(que[2]))%2 == 0:
            saf = saf + que[4]
        else:
            sbf = que[4] + sbf

print(sbf+s+saf if rev_count %2 == 0 else (sbf+s+saf)[-1::-1])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
Q = int(input())

rev_count = 0
for i in range(Q):
    que = input()
    if que[0] == '1':
        rev_count +=1
    elif que[0] == '2':
        if (rev_count + int(que[2]))%2 == 0:
            s = s + que[4]
        else:
            s = que[4] + s

print(s if rev_count %2 == 0 else s[-1::-1])


Fixed submission:
s = input()
Q = int(input())

rev_count = 0
sbf=''
saf=''
for i in range(Q):
    que = input()
    if que[0] == '1':
        rev_count +=1
    elif que[0] == '2':
        if (rev_count + int(que[2]))%2 == 0:
            saf = saf + que[4]
        else:
            sbf = que[4] + sbf

print(sbf+s+saf if rev_count %2 == 0 else (sbf+s+saf)[-1::-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys,collections,math
input = sys.stdin.readline

n,a,b = list(map(int,input().split()))
m = 10**9+7
ans = pow(2,n,m)


la  = 1
laa = 1
for i in range(n,n-a,-1):
    la = la*i
for i in range(1,a+1):
    laa = laa*i

lb  = 1
lbb = 1
for i in range(n,n-b,-1):
    lb = lb*i
for i in range(1,b+1):
    lbb = lbb*i

la = (la*pow(laa,10**9+5,m))%m
lb = (lb*pow(lbb,10**9+5,m))%m

print((ans-la-lb-1)%m)


Fixed submission:
import sys,collections,math
input = sys.stdin.readline

n,a,b = list(map(int,input().split()))
m = 10**9+7
ans = pow(2,n,m)


la  = 1
laa = 1
for i in range(n,n-a,-1):
    la = (la*i)%m
for i in range(1,a+1):
    laa = (laa*i)%m

lb  = 1
lbb = 1
for i in range(n,n-b,-1):
    lb = (lb*i)%m
for i in range(1,b+1):
    lbb = (lbb*i)%m

la = (la*pow(laa,10**9+5,m))%m
lb = (lb*pow(lbb,10**9+5,m))%m

print((ans-la-lb-1)%m)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np
input = sys.stdin.readline

N,K = list(map(int,input().split()))
p = np.array(list(map(int,input().split())))

pn1 = p - 1

ans = 0
for i in range(N-K+1):
    sp = sum(pn1[i:i+K])
    ans = max(sp,ans)
print(ans/2+K)

Fixed submission:
import sys
import numpy as np
input = sys.stdin.readline

N,K = list(map(int,input().split()))
p = np.array(list(map(int,input().split())))

pn1 = p - 1

ans = sum(pn1[:K])
spb = ans
for i in range(N-K):
    sp = spb -pn1[i] + pn1[i+K]
    #print(sp,spb,pn1[i],pn1[i+K])
    ans = max(sp,ans)
    spb = sp
print(ans/2+K)
Buggy python submission (verdict: Time Limit Exceeded):
import sys,math,collections,itertools
input = sys.stdin.readline

H,N=list(map(int,input().split()))
AB = []
amax = 0
for _ in range(N):
    a,b=map(int,input().split())
    amax = max(amax,a)
    AB.append([a,b])
HN = [float('inf')]*(H+amax+1)
HN[0] = 0
for i in range(H+amax+1):
    for j in range(N):
        if AB[j][0]<=i:
            tmp = HN[i-AB[j][0]]+AB[j][1]
            HN[i] = min(HN[i],tmp)
        else:
            tmp = AB[j][1]
            HN[i] = min(HN[i],tmp)
print(min(HN[H:]))


Fixed submission:
import sys,math,collections,itertools
input = sys.stdin.readline

H,N=list(map(int,input().split()))
AB = []
amax = 0
for _ in range(N):
    a,b=map(int,input().split())
    amax = max(amax,a)
    AB.append([a,b])
HN = [float('inf')]*(H+amax+1)
HN[0] = 0
for i in range(H+amax+1):
    for j in range(N):
        if AB[j][0]<=i:
            tmp = HN[i-AB[j][0]]+AB[j][1]
            HN[i] = min(HN[i],tmp)
        else:
            tmp = AB[j][1]
            HN[i] = min(HN[i],tmp)
print(min(HN[H:]))
Buggy python submission (verdict: Time Limit Exceeded):

def main():
    N = int(input())
    NN = [[0]*10 for _ in range(11)]
    for i in range(11,100):
        As = str(i)[0]
        Ae = str(i)[-1]
        cnt = 0
        for j in range(1,N+1):
            if str(j)[-1]== As and str(j)[0] == Ae:
                cnt +=1
        NN[int(As)][int(Ae)] = cnt


    ans = 0
    for i in range(1,N+1):
        ans += NN[int(str(i)[0])][int(str(i)[-1])]

    print(ans)

if __name__ == '__main__':
        main()



Fixed submission:
N = int(input())
NN = [[0]*10 for _ in range(11)]
for i in range(11,100):
    As = str(i)[0]
    Ae = str(i)[-1]
    cnt = 0
    for j in range(1,N+1):
        if str(j)[-1]== As and str(j)[0] == Ae:
            cnt +=1
    NN[int(As)][int(Ae)] = cnt


ans = 0
for i in range(1,N+1):
    ans += NN[int(str(i)[0])][int(str(i)[-1])]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
NN = [[0]*10 for _ in range(11)]
for i in range(11,100):
    As = str(i)[0]
    Ae = str(i)[-1]
    cnt = 0
    for j in range(1,N+1):
        if str(j)[-1]== As and str(j)[0] == Ae:
            cnt +=1
    NN[int(As)][int(Ae)] = cnt


ans = 0
for i in range(1,N+1):
    ans += NN[int(str(i)[0])][int(str(i)[-1])]

print(ans)


Fixed submission:
N = int(input())
NN = [[0]*10 for _ in range(11)]
for i in range(11,100):
    As = str(i)[0]
    Ae = str(i)[-1]
    cnt = 0
    for j in range(1,N+1):
        if str(j)[-1]== As and str(j)[0] == Ae:
            cnt +=1
    NN[int(As)][int(Ae)] = cnt


ans = 0
for i in range(1,N+1):
    ans += NN[int(str(i)[0])][int(str(i)[-1])]

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys,math,collections,itertools
input = sys.stdin.readline

N = int(input())
imo = []
xlmin = 0
xlmax = 0
for _ in range(N):
    x,l = map(int,input().split())
    imo.append([x-l,x+l])
    xlmin = min(xlmin,x-l)
    xlmax = max(xlmax,x+l)

point = [0]*(xlmax-xlmin+2)

for i in range(N):
    point[imo[i][0]-xlmin+1] += 1
    point[imo[i][1]-xlmin+1] -= 1

now = 0
cnt = 0
befor = 0
for i in range(len(point)):
    before = now
    now += point[i]
    if point[i]>=1 and now >1:
        cnt += now-before

print(N-cnt)


Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
imo = []
xlmin = 0
xlmax = 0
for _ in range(N):
    x,l = map(int,input().split())
    imo.append([x-l,x+l-1])
imo = sorted(imo,key = lambda x: x[1])
cnt = 1
ls = imo[0][1]
for i in range(1,N):
    if imo[i][0]<=ls:
        continue
    else:
        cnt += 1
        ls = imo[i][1]
print(cnt)