Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n = int(input())
*A, = map(int, input().split())
*B, = map(int, input().split())
cnt = 0
while B != A:
    for i in range(n):
        a, c = B[i-1], B[(i+1)%n]
        while (B[i] > A[i]) &\
           (B[i] > a) &\
           (B[i] > c):
            B[i] -= a+c
            cnt += 1
        if B[i] < A[i]:
            print(-1)
            exit()
print(cnt)

### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
*B, = map(int, input().split())
cnt = 0
while B != A:
    for i in range(n):
        a, c = B[i-1], B[(i+1)%n]
        if (B[i] > A[i]) &\
           (B[i] > a) &\
           (B[i] > c):
            d = (B[i]-max(A[i], a, c)+a+c-1)//(a+c)
            B[i] -= (a+c)*d
            cnt += d
        elif B[i] < A[i]:
            print(-1)
            exit()
print(cnt)
### BUGGY CODE ###

import heapq

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
heapq.heapify(a)

for i in range(m):
  b,c=map(int,input().split())
  for j in range(b):
    tmp=heapq.heappop(a)
    if tmp<c:
      heapq.heappush(a,c)
    else:
      heapq.heappush(a,tmp)
      break
print(sum(a))

### FIXED CODE ###

import heapq

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
heapq.heapify(a)

li=[list(map(int,input().split())) for i in range(m)]
li=sorted(li,key=lambda x:x[1],reverse=True)
for i in range(m):
  tmp=heapq.heappop(a)
  if tmp>li[i][1]:
    heapq.heappush(a,tmp)
    break
  else:
    heapq.heappush(a,tmp)
    for j in range(li[i][0]):
      tmp=heapq.heappop(a)
      if tmp<li[i][1]:
        heapq.heappush(a,li[i][1])
      else:
        heapq.heappush(a,tmp)
        break
print(sum(a))
### BUGGY CODE ###

n=int(input())
k=0
for i in range(10**9):
    while (i+1)**2 < n:
        k+=1
print((k+1)**2)

### FIXED CODE ###

n=int(input())
print((int(n**0.5))**2)
### BUGGY CODE ###

A, B, K = map(int, input().split())
l = []
for i in range(A, B + 1):
    l.append(i)
if B - A + 1 < K:
    for j in l:
        print(j)

else:
    m = l[:K] + l[B - A + 1 - K:]
    
    M = list(set(m))
    M.sort()
    for k in M:
        print(k)

### FIXED CODE ###

a, b, k = map(int, input().split())
l = []
for i in range(a, min(a + k, b)):
    l.append(i)

for i in range(max(a, b - k + 1), b + 1):
    l.append(i)

for i in sorted(set(l)):
    print(i)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *
		
s = input()
t = input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

common = [[] for _ in range(len(t))]

for i in range(len(s)):
	for j in range(len(t)):
		if s[i] == t[j]:
			dp[i+1][j+1] = dp[i][j] + 1
			common[dp[i][j]].append(t[j])
		else:
			dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

y = len(s)
x = len(t)
ans = ""
while 1:
	#print(y, x, ans)
	if x*y == 0:
		break
	elif s[y-1] == t[x-1]:
		ans += s[y-1]
		x -= 1
		y -= 1
	else:
		if dp[y][x] == dp[y-1][x]:
			y -= 1
		elif dp[y][x] == dp[y][x-1]:
			x -= 1

print(ans[::-1])

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *
		
s = input()
t = input()
 
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

for i in range(len(s)):
	for j in range(len(t)):
		if s[i] == t[j]:
			dp[i+1][j+1] = dp[i][j] + 1
		else:
			dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
            
y = len(s)
x = len(t)
ans = ""
while 1:
	#print(y, x, ans)
	if x*y == 0:
		break
	elif s[y-1] == t[x-1]:
		ans += s[y-1]
		x -= 1
		y -= 1
	else:
		if dp[y][x] == dp[y-1][x]:
			y -= 1
		elif dp[y][x] == dp[y][x-1]:
			x -= 1
            
print(ans[::-1])
### BUGGY CODE ###

I = lambda: map(int, input().split())
n, k = I()
a = []
for _ in range(n):
    t, d = I()
    a += [d, t, 0],
a.sort(reverse = True)
b = 0
c = [0]*(n+1)
for i in a[:k]:
    b += i[0]
    c[i[1]] += 1
    i[2] = 1
e = sum(int(bool(i)) for i in c)
f = [b+e**2]
for i in range(k, n):
    g = a[i]
    if c[g[1]] > 0: continue
    for j in a[:i][::-1]:
        if j[2] > 0 and c[j[1]] > 1:
            b += g[0]-j[0]
            g[2] = 1
            j[2] = 0
            c[g[1]] += 1
            c[j[1]] -= 1
            e += 1
            f += b+e**2,
            break
print(max(f))

### FIXED CODE ###

mi = lambda: map(int, input().split())
n, k = mi()
sushis = [list(mi()) for _ in range(n)]
types = set()
sushis.sort(key = lambda x: x[1], reverse = True)
bp = tp = sp = 0
exts = []
for t, d in sushis[:k]:
    bp += d
    if t in types:
        exts += d,
    else:
        types.add(t)
        tp += 1
sp = bp+tp**2
for t, d in sushis[k:]:
    if not exts: break
    if t not in types:
        types.add(t)
        bp += d-exts.pop()
        tp += 1
        sp = max(sp, bp+tp**2)
print(sp)
### BUGGY CODE ###

from copy import deepcopy
N=int(input())
A=[int(i) for i in input().split()]

def chmax(a,b):
    if a[0]<b[1]:
        return b
    elif a[0]<b[0]:
        return(b[0],a[0])
    elif a[1]<b[0]:
        return (a[0],b[0])
    else:
        return a
dp=[(A[i],0) for i in range(1<<N)]
#print(dp)
for i in range(N):
    for j in range(1<<N):
        if (j & (1<<i))==0:
            #print(j,i,j|(1<<i))
            dp[j|(1<<i)]=chmax(dp[j],dp[j|(1<<i)])
#print(dp)
ans =sum(dp[0])
for i in range(1,1<<N):
    t = sum(dp[i])
    ans = max(ans,t)
    print(ans)

### FIXED CODE ###

from copy import deepcopy
N=int(input())
A=[int(i) for i in input().split()]

def chmax(a,b):
    if a[0]<b[1]:
        return b
    elif a[0]<b[0]:
        return(b[0],a[0])
    elif a[1]<b[0]:
        return (a[0],b[0])
    else:
        return a
dp=[(A[i],0) for i in range(1<<N)]
#print(dp)
for i in range(N):
    for j in range(1<<N):
        if j & (1<<i):
            #print(j,i,j|(1<<i))
            dp[j]=chmax(dp[j],dp[j^(1<<i)])
#print(dp)
ans =sum(dp[0])
for i in range(1,1<<N):
    t = sum(dp[i])
    ans = max(ans,t)
    print(ans)
### BUGGY CODE ###

s=list(map(int,input().split()))
i=0
a=0
list=[]
for i in range(s[0],s[1]+1):
  if i%s[2]!=0 and i%s[3]!=0:
    a=a+1
print(a)

### FIXED CODE ###

A,B,C,D=map(int,input().split())
a=B//C-(A-1)//C
b=B//D-(A-1)//D
def lcm(x,y):
    return x*y//gcd(x,y)

def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

z=lcm(C,D)
c=B//z-(A-1)//z
print(B-A+1-a-b+c)
### BUGGY CODE ###

n,k=map(int,input().split())

def count(k,i):
    cnt=0
    while k>i:
        i**=2
        cnt+=1
    return cnt

p=0
for i in range(1,n+1):
    p+=((1/2)**(count(k,i)))
print(p/n)

### FIXED CODE ###

import sys
import math

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
   
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,k=map(int,input().split())

A=[]
cnt=0
def count(i,k):
    cnt=0
    while k>i:
        i=i*2
        cnt+=1
        
    return cnt

pro=0

for i in range(1,n+1):
	pro+=(1/2)**count(i,k)
print(pro/n)
### BUGGY CODE ###

n=int(input())
tmp=[list(map(int,input().split())) for i in range(n)]
tmp.reverse()
tmp.append([0,0])
v=[0]
for i in range(0,n):
    cnt=0
    if tmp[i][0]%tmp[i][1]!=0:
        cnt+=(tmp[i][1]-tmp[i][0]%tmp[i][1])
        tmp[i][0]+=(tmp[i][1]-tmp[i][0]%tmp[i][1])
    v.append(cnt)
    tmp[i + 1][0] += sum(v)
print(sum(v))



### FIXED CODE ###

n=int(input())
A=[]
B=[]
for i in range(n):
    a,b=input().split()
    A.append(a)
    B.append(b)
A.reverse()
B.reverse()
A.append(0)
B.append(0)
A=list(map(int,A))
B=list(map(int,B))

x=0
for i in range(0,n):
    cnt=0
    if A[i]%B[i]!=0:
        cnt+=(B[i]-A[i]%B[i])
        A[i]+=(B[i]-A[i]%B[i])
    x+=cnt
    A[i+1]+= x
print(x)
### BUGGY CODE ###

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
b = 0

for i in range(n):
    for j in range(i,n):
        b = max(b, (abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1])))
print(b)


### FIXED CODE ###

def get_ints():
    return list(map(int, input().split()))

n = int(input())
a,b = [],[]
for i in range(n):
    x, y = get_ints()
    a.append(x+y)
    b.append(x-y)

a.sort()
b.sort()
ans = max(a[-1]-a[0], b[-1]-b[0])
print(ans)
### BUGGY CODE ###

k = int(input())
s = input()
mod = 10 ** 9 + 7

MAX = 2 * 10 ** 6

fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = (fact[i-1] * i) % mod

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod


ln = len(s)

ans = 0
for i in range(ln, k + ln + 1):
    ans += pow(25, i - ln, mod) * pow(26, ln + k - i, mod) * comb(i - 1, ln - 1)
    ans %= mod

print(ans)


### FIXED CODE ###

k = int(input())
s = input()
mod = 10 ** 9 + 7

MAX = 2 * 10 ** 6

fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = (fact[i-1] * i) % mod

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod


ln = len(s)

ans = 0
pow25 = 1
pow26 = pow(26, k, mod)
inv26 = pow(26, mod - 2, mod)
for i in range(ln, k + ln + 1):
    ans += pow25 * pow26 % mod * comb(i - 1, ln - 1) % mod
    ans %= mod
    pow25 *= 25
    pow25 %= mod
    pow26 *= inv26
    pow26 %= mod

print(ans)
### BUGGY CODE ###

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]
n,m=map(int,input().split())
ans_list=[]
for _ in range(n):
    ans_list.append(0)
h_list=list(map(int,input().split()))
#print(h_list)
road_list=[]
for i in range(m):
  road_list.append(list(map(int,input().split())))
#print(road_list)
roadset=get_unique_list(road_list)
#print(roadset)
roadnum=len(roadset)
#print(roadnum)

for i in range(roadnum):
  templist=roadset[i]
  a=templist[0]
  b=templist[1]
  #print([a,b])
  if h_list[a-1]>h_list[b-1]:
    ans_list[b-1]+=1
  elif h_list[a-1]==h_list[b-1]:
    ans_list[a-1]+=1
    ans_list[b-1]+=1
  else:
    ans_list[a-1]+=1
print(ans_list.count(0))

### FIXED CODE ###

n,m=map(int,input().split())
ans_list=[]
for _ in range(n):
    ans_list.append(0)
h_list=list(map(int,input().split()))
#print(h_list)
road_list=[]
for i in range(m):
  road_list.append(list(map(int,input().split())))
#print(road_list)
#roadset=get_unique_list(road_list)
#print(roadset)
roadnum=len(road_list)
#print(roadnum)

for i in range(roadnum):
  templist=road_list[i]
  a=templist[0]
  b=templist[1]
  #print([a,b])
  if h_list[a-1]>h_list[b-1]:
    ans_list[b-1]+=1
  elif h_list[a-1]==h_list[b-1]:
    ans_list[a-1]+=1
    ans_list[b-1]+=1
  else:
    ans_list[a-1]+=1
print(ans_list.count(0))
### BUGGY CODE ###

n, s = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353

dp = [[[0] * 3 for _ in range(s + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for i, e in enumerate(a):
    for j in range(s + 1):
        dp[i+1][j][0] += dp[i][j][0]
        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
        if j + e <= s:
            dp[i+1][j+e][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+e][2] += dp[i][j][0] + dp[i][j][1]

        for k in range(3):
            dp[i+1][j][k] %= mod

ans = dp[n][s][2]
print(ans)


### FIXED CODE ###

import numpy as np

n, s = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353

dp = np.array([[0] * 3 for _ in range(s + 1)], dtype=np.int64)
dp[0][0] = 1

for i, e in enumerate(a):
    cp = dp.copy()
    dp[:, 1] += cp[:, 0]
    dp[:, 2] += cp[:, 0] + cp[:, 1]

    dp[e:, 1] += cp[:-e, 0] + cp[:-e, 1]
    dp[e:, 2] += cp[:-e, 0] + cp[:-e, 1]

    dp %= mod

ans = dp[s][2]
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
s = set(l)
ans = 0

for i in s:
    ans = max(l.count(i-1) + l.count(i) + l.count(i+1), ans)

print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())
l = list(map(int, input().split()))
c = Counter(l)
s = set(l)
ans = 0

for i in s:
    ans = max(c[i-1] + c[i] + c[i+1], ans)
print(ans)
### BUGGY CODE ###

n, k = [int(e) for e in input().split()]
h = [int(e) for e in input().split()]
cost = [0] * n
cost[1] = abs(h[1] - h[0])
for i in range(1, n):
  cost[i] = min(abs(h[i] - h[j]) + cost[j] for j in range(max(0, i - k), i))
print(cost[n - 1])


### FIXED CODE ###

n, k = [int(e) for e in input().split()]
h = [int(e) for e in input().split()]
cost = [0] * n
cost[1] = abs(h[1] - h[0])
for i in range(1, n):
  cost[i] = min(abs(h[i] - h[j]) + cost[j] for j in range(max(0, i - k), i))
print(cost[n - 1])
### BUGGY CODE ###

if __name__ == '__main__':
    N,K=list(map(int,input().split()))
    L=[]
    for i in range(N):
        a,b=list(map(int,input().split()))
        for j in range(b):
            L.append(a)
    L.sort()
    print(L[K-1])

### FIXED CODE ###

if __name__ == '__main__':
    N,K=list(map(int,input().split()))
    AB=[tuple(map(int,input().split())) for i in range(N)]
    AB.sort(key=lambda x:x[0])
    for a,b in AB:
        K-=b
        if K<=0:
            print(a)
            break
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
count = 0

for i in range(N - 2):
    for j in range(N - i - 2):
        for k in range(N - i - j - 2):
            if L[i] + L[i + j + 1] <= L[i + j + k + 2]:
                pass
            elif L[i + j + 1] + L[i + j + k + 2] <= L[i]:
                pass
            elif L[i + j + k + 2] + L[i] <= L[i + j + 1]:
                pass
            else:
                count = count + 1

print(count)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
C = sorted(L)
count = 0

import bisect
for i in range(N - 2):
    for  j in range(N - i - 2):
        s = C[i] + C[j + i + 1]
        t = bisect.bisect_left(C,s)
        u = t - (j + i + 1) - 1
        if u <= 0:
            pass
        else:
            count = count + u

print(count)
### BUGGY CODE ###

n = int(input())
a = tuple(map(int,input().split()))

mod = 10**9 + 7
at = tuple([a[i] % mod for i in range(n)])

ans = 0
for i in range(n):
  atemp = at[i]
  for j in range(i+1,n):
    ans += (atemp * (at[j])) % mod
    ans = ans % mod
print(ans % mod)

### FIXED CODE ###

n = int(input())
a = tuple(map(int,input().split()))
t = 0
mod = 10**9 + 7
at = []
for j in range(1,n):
  t += a[n-j] % mod 
  at.append(t)

ans = 0
for i in range(n-1):
  ans += at[n-2-i] *a[i]
print(ans % mod)
### BUGGY CODE ###

def main():
  s = input()
  divisor = 10 ** 9 + 7
  lut = [i % 13 for i in range(133)]
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      for j in range(10):
        for k in range(13):
          dpi1[lut[k * 10 + j]] += dpi[k]
    else:
      t = int(s[i])
      for k in range(13):
        dpi1[lut[k * 10 + t]] += dpi[k]
    for k in range(13):
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()


### FIXED CODE ###

s = ''.join(reversed(input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
a = a[::-1]

cur = [a[0], a[1]]
now = a[0]
for i in a[2:]:
    loc = 0
    maxer = min(cur[0], cur[-1])
    for j in range(1, len(cur)):
        temp = min(cur[j - 1], cur[j])
        if temp > maxer:
            loc = j
            maxer = temp
    now += maxer
    cur = cur[:loc] + [i] + cur[loc:]

print(now)


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
a = a[::-1]

if n % 3 == 0:
    if n % 2 == 0:
        print(a[0] + sum(a[1:n//2]) * 2)
    else:
        print(a[0] + sum(a[1:n//2]) * 2 + a[n//2])
elif n % 3 == 2:
    if n % 2 == 0:
        print(a[0] + sum(a[1:n//2]) * 2)
    else:
        print(a[0] + sum(a[1:n//2]) * 2 + a[n//2])
else:
    if n % 2 == 0:
        print(a[0] + sum(a[1:n//2]) * 2)
    else:
        print(a[0] + sum(a[1:n//2]) * 2 + a[n//2])
### BUGGY CODE ###

from operator import mod
d = 0
e = -1
i = 1
a = int(input())
while True:
    d = 7 + 10*d
    if mod(a, 2) == 0:
        print(e)
        break
    elif mod(d, a) == 0:
        print(i)
        break
    i += 1

### FIXED CODE ###

K = int(input())
 
num = 0
cnt = 0
ans = -1
 
for i in range(K):
    num = num*10 +7
    cnt += 1
    if num%K != 0:
        num = num%K
    else:
        ans = cnt
        break
    
print(ans)
### BUGGY CODE ###

n = int(input())

l = 0
r = n-1
hist = []
print(0, flush=True)
hist.append(0)
current = input()

while r - l > 2:
    mid = (l+r)//2
    print(mid,flush=True)
    hist.append(mid)
    nex = input()
    if nex == 'Vacant':
        exit()
    if current == nex:
        l = mid
    else:
        r = mid
    current = nex

cand = [i for i in range(l, r+1) if i not in hist]
for i in cand:
    print(i, flush=True)
    nex = input()
    if nex == 'Vacant':
        exit()

### FIXED CODE ###

import sys

n = int(input())
print(0)
sys.stdout.flush()
ls = input()
if ls == 'Vacant':
    exit()
print(n - 1)
sys.stdout.flush()
if input() == 'Vacant':
    exit()
l = 0
r = n - 1
while l != r - 1:
    mid = (l + r) // 2
    if mid % 2 == 1:
        mid += 1
    if mid == r:
        mid -= 1
    print(mid)
    sys.stdout.flush()
    nex = input()
    if nex == 'Vacant':
        exit()

    if ls == nex:
        l = mid
    else:
        r = mid
### BUGGY CODE ###

import sys
import numpy as np

h, n = list(map(int, input().split()))
INF = 10 ** 18
dp = np.full(h + 10001, INF, dtype=np.int64)
dp[0] = 0
for line in sys.stdin:
    a, b = map(int, line.split())
    for s in range(0, h, a):
        dp[s + a:h + a] = np.minimum(dp[s + a:h + a], dp[s:h] + b)
print(dp[h:].min())


### FIXED CODE ###

import sys

h, n = list(map(int, input().split()))
INF = 10 ** 18
dp = [INF] * (20201)
dp[0] = 0
for line in sys.stdin:
    a, b = map(int, line.split())
    for i in range(10000):
        if dp[i] == INF:
            continue
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))
### BUGGY CODE ###

A, B = map(int, input().split())
k = 0

while True:
    if 2**(k-1) <= B < 2**k:
        break
    k += 1


def sum_xor(n):
    res = []
    for i in range(k):
        if i == 0:
            res.append(1) if n % 4 == 1 or n % 4 == 2 else res.append(0)
        else:
            nmod = n % 2 ** (i + 1)
            if (2**(i+1))/2 <= nmod < 2**(i+1) and nmod % 2 == 0:
                res.append(1)
            else:
                res.append(0)
            # odd = [2**i+2*j for j in range(2**(i-1))]
            # tmp = n % 2**(i+1)
            # res.append(1) if tmp in odd else res.append(0)
    res.reverse()
    return res


ax = sum_xor(A-1)
bx = sum_xor(B)

ans = []
for i in range(k):
    ans.append(1) if (ax[i] + bx[i]) % 2 == 1 else ans.append(0)

ans = "".join(map(str, ans))
print(int(ans, 2))


### FIXED CODE ###

A, B = map(int, input().split())
k = 1

while True:
    if B == 0:
        break
    if 2**(k-1) <= B < 2**k:
        break
    k += 1


def sum_xor(n):
    res = []
    for i in range(k):
        if i == 0:
            res.append(1) if n % 4 == 1 or n % 4 == 2 else res.append(0)
        else:
            nmod = n % (2 ** (i + 1))
            if (2**(i+1))/2 <= nmod < 2**(i+1) and nmod % 2 == 0:
                res.append(1)
            else:
                res.append(0)
            # odd = [2**i+2*j for j in range(2**(i-1))]
            # tmp = n % 2**(i+1)
            # res.append(1) if tmp in odd else res.append(0)
    res.reverse()
    return res


ax = sum_xor(A-1)
bx = sum_xor(B)

ans = []
for j in range(k):
    ans.append(1) if (ax[j] + bx[j]) % 2 == 1 else ans.append(0)

ans = "".join(map(str, ans))
print(int(ans, 2))
### BUGGY CODE ###

A,B,K = map(int,input().split())
for i in range(K) :
    if A >= 1 :
        A = A - 1
    elif B >= 1 :
        B = B - 1
    else :
        pass

print(A,B)  

### FIXED CODE ###

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

if A >= K :
    A = A - K 
    print(A,B)
else :
    if (B-(K-A)) >= 0 :
        print(0,B-(K-A)) 
    else :
        print(0,0)
### BUGGY CODE ###

x, y, z, kk = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

d = []
for i in range(x):
  for j in range(y):
    for k in range(z):
      d.append(a[i]+b[j]+c[k])
d.sort(reverse=True)

for i, e in enumerate(d):
  if i>=kk:
    break
  print(e)

### FIXED CODE ###

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

d = []

for e1 in a:
  for e2 in b:
    d.append(e1+e2)

d.sort(reverse=True)
d = d[:k]
e = []

for e1 in d:
  for e2 in c:
    e.append(e1+e2)
    
e.sort(reverse=True)

for i in range(k):
  print(e[i])
### BUGGY CODE ###

while 1:
    try:
        b=[]
        count=1
        x=int(input())
        if x==1:
            print(0)
        elif x==2:
            print(1)
        else:
            for i in  range(3,x+1):
                count1=0
                for j in range(2,i):
                    if i%j==0:
                        count1=1
                        break
                if count1==0:
                    count+=1
            print(count)        
    except EOFError:
        break

### FIXED CODE ###

str1=[0 for i in range(10**6)]
str1[0]=1
str1[1]=1
for i in range(2,(10**6)):
    if str1[i]==0:
        for j in range(2,(10**6)):
            if i*j>=len(str1):
                break
            else:
                str1[i*j]=1
            
while 1 :
    try:
        x=int(input())
        count=0
        for i in range(1,x+1):
            if str1[i]==0:
                count+=1
        print(count)
        
    except EOFError:
        break