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

n = int(input())
A = [int(input()) for i in range(n)]

def insertionSort(A, n, g):
 global cnt
 for i in range(g, n):
  v = A[i]
  j = i - g
  while j >= 0 and A[j] > v:
   A[j + g] = A[j]
   j -= g
   cnt +=1
  A[j + g] = v

def shellSort(A, n, m, G):
 A1 = A[:]
 global cnt
 cnt = 0
 for i in range(m):
  insertionSort(A1, n, G[i])
 return A1

def Gmake(n):
 G=[]
 k = 1
 while k <= n and len(G) < 100:
  G.append(k)
  k += 3
 G.reverse()
 return G

G = Gmake(n)
A2 = shellSort(A, n, len(G), G)
print(str(len(G)))
print(" ".join(map(str, G)))
print(str(cnt))
for i in A2:
 print(str(i))

### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]

def insertionSort(A, n, g):
 global cnt
 for i in range(g, n):
  v = A[i]
  j = i - g
  while j >= 0 and A[j] > v:
   A[j + g] = A[j]
   j -= g
   cnt +=1
  A[j + g] = v

def shellSort(A, n, m, G):
 A1 = A[:]
 global cnt
 cnt = 0
 for i in range(m):
  insertionSort(A1, n, G[i])
 return A1

def Gmake(n):
 G=[]
 k = 1
 while k <= n and len(G) < 100:
  G.append(k)
  k = 3 * k + 1
 G.reverse()
 return G

G = Gmake(n)
A2 = shellSort(A, n, len(G), G)
print(str(len(G)))
print(" ".join(map(str, G)))
print(str(cnt))
for i in A2:
 print(str(i))
### BUGGY CODE ###

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    counts = [0] * n
    for _ in range(m):
        l, r = map(int, input().split())
        for i in range(l - 1, r):
            counts[i] += 1
    print(counts.count(m))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    l_max = 0
    r_min = float('inf')
    for _ in range(m):
        l, r = map(int, input().split())
        l_max = max(l_max, l)
        r_min = min(r_min, r)
    print(max(r_min + 1 - l_max, 0))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()
### BUGGY CODE ###

n = int(input())
s = input()

count = 0
 
for i,first in enumerate(s[:-2]):
    r_count = s[i+1:].count('R')
    g_count = s[i+1:].count('G')
    b_count = s[i+1:].count('B')
    for j,second in enumerate(s[i+1:n-1]):
        if second == 'R':
            r_count -=1
        elif second == 'G':
            g_count -=1
        else:
            b_count -=1
        if first != second:
            if 'R' != first and 'R' != second:
                count += r_count
                third = 'R'
            elif 'G' != first and 'G' != second:
                count += g_count
                third = 'G'
            else:
                count += b_count
                third = 'B'
            if i+j+2+j <= n-1 and s[i+j+2:][j] == third:
                count -= 1

 
print(count)

### FIXED CODE ###

n = int(input())
s = input()

r_count = s.count('R')
g_count = s.count('G')
b_count = s.count('B')

count = r_count*g_count*b_count


for i,elem in enumerate(s):
    length = min(i,n-1-i)
    for j in range(1,length+1):
        elem_2 = s[i-j]
        elem_3 = s[i+j]
        if elem != elem_2 and elem != elem_3 and elem_2 != elem_3:
            count -= 1

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

s=input()
q=int(input())
direction=0 #0:順 1:逆

for i in range(q):
    query=input()
    #print(query)
    if query[0]=='1':
        direction=direction^1
    elif query[0]=='2':
        c=query[4]
        if query[2]=='1' and direction==0:
            s=c+s
        elif query[2]=='1' and direction==1:
            s=s+c
        elif query[2]=='2' and direction==0:
            s=s+c 
        elif query[2]=='2' and direction==1:
            s=c+s

if direction==0:
    print(s)
else:
    ns=''
    for i in range(len(s)):
        ns+=s[-1-i]
    print(ns)


### FIXED CODE ###

from collections import deque
s=deque(list(input()))
q=int(input())
direction=0 #0:順 1:逆

for i in range(q):
    query=input()
    if query[0]=='1':
        direction=direction^1
    elif query[0]=='2':
        i,f,c=query.split()
        if f=='1' and direction==0:
            s.appendleft(c)
        elif f=='1' and direction==1:
            s.append(c)
        elif f=='2' and direction==0:
            s.append(c)
        elif f=='2' and direction==1:
            s.appendleft(c)


if direction==0:
    print(''.join(s))
else:
    x=[]
    for i in range(len(s)):
        x.append(s[-1-i])
    print(''.join(x))
### BUGGY CODE ###

n = int(input())
data = list(map(int, input().split()))
ans = 1
for i in data:
    ans*=i
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
data = list(map(int, input().split()))
if 0 in data:
    print(0)
    exit()
ans = 1
for a in data:
    ans*=a
    if ans > 10**18:
        print(-1)
        exit()

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

import sys
input=sys.stdin.readline
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
cnt=Counter(a)
#print(cnt)

ans={}
for i in set(a):
    temp=cnt[i]-1
    ans[i]=0
    for x,y in cnt.items():
        if x!=i and y>=2:
            ans[i]+=(y-1)*y//2
        elif x==i and temp>=2:
            ans[i]+=(temp-1)*temp//2

for i in a:
    print(ans[i])

### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
cnt=Counter(a)
#print(cnt)

ans=0
for i in cnt.values():
    ans=ans+i*(i-1)//2

for i in a:
    print(ans-cnt[i]+1)
### BUGGY CODE ###

N,M=map(int,input().split())
hune=[]
for a in range(M):
    a,b=input().split()
    hune.append(int(a))
    hune.append(int(b))
number=0
for a in range(0,2*M-1,2):
    if hune[a]==1:
        c=hune[a+1]
        for z in range(0,2*M-1,2):
            if hune[z]==c and hune[z+1]==N:
                print('POSSIBLE')
                number+=1
                break
        for y in range(1,2*M,2):
            if hune[z]==c and hune[z-1]==N:
                print('POSSIBLE')
                number+=1
                break
if number==0:
    print('IMPOSSIBLE')
    

### FIXED CODE ###

N,M=map(int,input().split())
islands=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    islands[a].append(b)
answer=1
for n in islands[1]:
    if N in islands[n]:
        answer=0
        print('POSSIBLE')
        break
if answer==1:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import sys
input=sys.stdin.readline

s=int(input())

#0<= x,y <=10**9
#s/2

if s<=10**9:
    print(0,0,1,0,0,s)
    exit()

hoge=int(s**0.5)

for i in range(hoge):
    ss=hoge-i
    #print(ss)
    if s%ss==0:
        print(0,0,ss,0,0,s//ss)
        exit()



### FIXED CODE ###

import sys
input=sys.stdin.readline

s=int(input())

#0<= x,y <=10**9
#s/2

if s<=10**9:
    print(0,0,1,0,0,s)
    exit()

y=(-1*s//(10**9))*(-1)
x=10**9*y-s

print(0,0,10**9,1,x,y)
### BUGGY CODE ###

# C - Digits in Multiplication
N = int(input())

A = int(N**0.5)
ans = 1
for i in range(A,N):
    if N % i == 0:
        ans = len(str(i))
        break
    else:
        ans = len(str(i))

print(ans)

### FIXED CODE ###

# C - Digits in Multiplication
N = int(input())

A = int(N**0.5)
# print(A)
ans = 1
for i in range(A,0,-1):
    if N % i == 0:
        tmp = N / i
        ans = len(str(int(tmp)))
        break
    else:
        pass

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

mondai, kaitou = map(int, input().split())

# 問題ごとの
clearNo = []
# 問題ごとのWrong
wrong = {}
cleard = 0
pena = 0
# 解答数分繰り返す
kaitous = [input().split() for _ in range(kaitou)]
for i in kaitous:
    if i[0] in clearNo:
        continue
    else:
        if i[1] == 'WA':
            if i[0] in wrong:
                wrong[i[0]] += 1
            else:
                wrong[i[0]] = 1
        else:
            cleard += 1
            if i[0] in wrong:
                pena += wrong[i[0]]
            clearNo.append(i[0])

print(str(cleard) + ' ' + str(pena))


### FIXED CODE ###

mondai, kaitou = map(int, input().split())

# 問題ごとのクリア管理
clearNo = [0] * (mondai+1)
# 問題ごとのWrong
wrong = [0] * (mondai+1)
cleard = 0
pena = 0
# 解答数分繰り返す
kaitous = [input().split() for _ in range(kaitou)]
for i in kaitous:
    qNo = int(i[0])
    result = i[1]
    if clearNo[qNo] == 1:
        continue
    else:
        if result == 'WA':
            wrong[qNo] += 1
        else:
            clearNo[qNo] = 1
            cleard += 1
            pena += wrong[qNo]

print(str(cleard) + ' ' + str(pena))
### BUGGY CODE ###

import itertools
n,x=map(int,input().split())
a=list(map(int, input().split()))
if sum(a)<x:
    print(len(a)-1)
else:
    ans=0
    for i in range(1,n+1):
        for v in itertools.combinations(a,i):
            if sum(v)<=x:
                ans=len(v)
    print(ans)

### FIXED CODE ###

n,x=map(int,input().split())
a=list(map(int, input().split()))

ans=0
rest=x
target=sorted(a)
if sum(target)<x:
    print(n-1)
elif sum(target)==x:
    print(n)
else:
    for i in range(n):
        rest-=target[i]
        if rest<0:
            ans=i
            break
        if rest==0:
            ans=i+1
            break
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float('inf')
MOD=10**9+7
input=sys.stdin.readline

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

#初期値が0の辞書
from collections import defaultdict
lrd = defaultdict(lambda: []) 

lr=defaultdict(lambda: 0) 

for _ in range(m):
    l,r,d=map(int,input().split())
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x)
    for llrrdd in lrd[x]:
        #print(lrd,item,x)
        item=llrrdd[0]
        if answer[item]==INF:
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n

for i in range(n):
    if checked[i]==0:
        answer = defaultdict(lambda: INF) 
        answer[i]=1
        BFD(i)

print("Yes")


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

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

lrd=[[] for _ in range(n)]

for _ in range(m):
    l,r,d=map(int,input().split())
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x,lrd[x])
    for llrrdd in lrd[x]:
        #print(llrrdd,x)
        item=llrrdd[0]
        if answer[item]=="first":
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n
answer = ["first"]*n

for i in range(n):
    if checked[i]==0:
        answer[i]=1
        BFD(i)

print("Yes")
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
    a[-1] //= 2
    a.sort()
print(sum(a))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(lambda x: int(x) * (-1), input().split()))
heapq.heapify(a)

for i in range(m):
    x = heapq.heappop(a)
    heapq.heappush(a, -1 * ((-x) // 2))
print(-sum(a))
### BUGGY CODE ###

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

ans = sum(A)

for b in range(min(A)-N,max(A)+N):
        tmp = sum([abs(A[i]-(b+i+1)) for i in range(N)])
        if ans > tmp:
                ans = tmp

print(ans)

### FIXED CODE ###

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

ans = sum(A)

imin = min(A)-N
imax = max(A)+N

def calcAns(b):
        global A
        return sum([abs(A[i]-(b+i+1)) for i in range(N)])

while True:
        if imin == imax:
                break
        else:
                imid = imin + (imax - imin)//2
                tmp = calcAns(imid)
                if calcAns(imid+1)<tmp:
                        imin = imid+1
                elif calcAns(imid-1)<tmp:
                        imax = imid-1
                else:
                        imin = imid
                        imax = imid

print(calcAns(imin))
### BUGGY CODE ###

import re

s = input()
flg = True
while flg:
    flg = False
    for rp in ['dream', 'dreamer', 'erase', 'eraser']:
        aft = re.sub(rp+'$', '', s)
        ##print(s,rp,aft, flg)
        if s != aft:
            s = aft
            flg = True
if s == '':
    print('YES')
else:
    print('NO')


### FIXED CODE ###

s = input()
l = ['dream', 'dreamer', 'erase', 'eraser']
pos = 0
flg = True
can = False
while flg:
    flg = False
    for i in range(len(l)):
        st = len(l[i])+pos
        if st<=len(s):
            if s[st*(-1):len(s)-pos] == l[i]:
                pos += len(l[i])
                if pos == len(s):
                    can = True
                    break
                flg = True
if can == True:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    count = 0
    for j in range(N):
        now_j = S[j]
        for i in range(j):
            now_i = S[i]
            if now_i == now_j:
                continue
            for k in range(j+1, N):
                now_k = S[k]
                if now_k == now_i or now_k == now_j or k - j == j - i:
                    continue
                count += 1
    print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    a = [0, 0, 0]
    for i in range(N):
        if S[i] == 'R':
            a[0] += 1
        elif S[i] == 'G':
            a[1] += 1
        else:
            a[2] += 1
    count = a[0] * a[1] * a[2]
    for i in range(N - 1):
        for j in range(1, N):
            if i - j < 0 or N <= i + j:
                break
            if S[i - j] != S[i] and S[i] != S[i + j] and S[i - j] != S[i + j]:
                count -= 1
    print(count)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
lst = list(map(int, input().split()))
lst2 = []
flag = 0
for _ in range(max(lst)):
  lst2.append(0)
for i in range(n):
  if lst2[lst[i]-1] == 0:
    lst2[lst[i]-1] += 1
  else:
    print('NO')
    flag = 1
    break
if flag == 0:
  print('YES')

### FIXED CODE ###

n = int(input())
lst = list(map(int, input().split()))
flag = 0
lst.sort()
for i in range(n-1):
  if lst[i] == lst[i+1]:
    print('NO')
    flag = 1
    break
if flag == 0:
  print('YES')
### BUGGY CODE ###

import sys
n = int(sys.stdin.readline())
s = sys.stdin.readline()
r = []
g = []
b = []
cnt = 0
i = 0
while i < n:
  if s[i] == "R":
    r.append(i)
  elif s[i] == "G":
    g.append(i)
  else:
    b.append(i)
for j in r:
  for k in g:
    for l in b:
      if l - k != k - j:
        cnt += 1
print(cnt)

### FIXED CODE ###

import sys

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))


n = ri()
s = rr()
ans = s.count('R') * s.count('G') * s.count('B')
for i in range(n-2):
    for j in range(i+1, n-1):
        k = j + j - i
        if k < n:
            if s[k] != s[j] and s[j] != s[i] and s[k] != s[i]:
                ans -= 1
print(ans)
### BUGGY CODE ###

def gcd(x,y):
    r = x%y
    if r==0:
        return y
    else:
        return gcd(y,r)
input = int(input())
cnt = 1
for i in range(2,input):
    if gcd(input,i) == 1:
        cnt += 1

print(cnt)

### FIXED CODE ###

def phi(n):
    r = n
    i = 2
    while i*i <= n:
        if n%i==0:
            r -= r/i
            while n%i==0:
                n /= i
        i += 1
    if n>1: r-= r/n
    return r

n = int(input())
print(int(phi(n)))
### BUGGY CODE ###

import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
dp = np.zeros((n, 13), int)
a = S[-1]
x_ = dp[0]
l = [1, 10, 9, 12, 3, 4]
l = [[i * l_ % 13 for i in range(1, 10)] for l_ in l]
li = 1
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x in zip(S[-2::-1], dp[1:]):
    if s == "?":
        x += x_
        for v in l[li]:
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    else:
        if s == "0":
            x += x_
        else:
            v = l[li][int(s) - 1]
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    x %= mod
    li += 1
    li %= 6
    x_ = x
print(dp[-1][5])

### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

A=list(map(int,list(input())))
L = len(A)
num = L
while True:
    pre = A[0]
    end = True
    for i in range(1,L):
        if A[i] != pre:
            if i*2 < L and L - i < num:
                num = L - i
            elif i < num:
                num = i
            for j in range(i):
                A[j] = 1 - A[j]
            end = False
            break
    if end:
        break
print(num)

### FIXED CODE ###

A=list(map(int,list(input())))
L = len(A)
num = L
pre = A[0]
end = True
for i in range(1,L):
    if A[i] != pre:
        if i*2 < L and L - i < num:
            num = L - i
        elif i < num:
            num = i
    pre = A[i]
print(num)
### BUGGY CODE ###

n, p = map(int, input().split())
s = input()
ans = 0
x0 = [0]*p
for i in range(n):
  x1 = [0]*p
  z = int(s[i])
  x1[z%p] = 1
  for j in range(p):
    x1[(10*j+z)%p] += x0[j]
  x0 = x1
  ans += x0[0]
print(ans)

### FIXED CODE ###

n, p = map(int, input().split())
s = input()
x = [1] + [0]*(p-1)
ans = 0
u = 0
if p in [2,5]:
  for i in range(n):
    if int(s[i])%p==0:
      ans += i+1
else:
  for i in range(n-1,-1,-1):
    u = (int(s[i])*pow(10,n-1-i,p)+u)%p
    ans += x[u]
    x[u] += 1
print(ans)
### BUGGY CODE ###

x,y = map(int, input().split())

while True:

    if x == 0 and y == 0:
        break

    elif x <= y:
        print(x,y)

    else:
        print(y, x)



### FIXED CODE ###

while True:
    x,y = map(int, input().split())

    if x == 0 and y == 0:
        break

    elif x <= y:
        print(str(x) + " " + str(y))
    else:
        print(str(y) + " " + str(x))
### BUGGY CODE ###

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    cnt = dict()
    ans = dict()
    for i in a:
        cnt[i] = cnt.get(i, 0) + 1

    for (idx, v) in cnt.items():
        ans[idx] = v * (v - 1) // 2

    for k in range(len(a)):
        res = sum(ans.values()) - (cnt[a[k]] - 1)
        print(res)



### FIXED CODE ###

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    cnt = dict()
    ans = dict()
    for i in a:
        cnt[i] = cnt.get(i, 0) + 1

    for (idx, v) in cnt.items():
        ans[idx] = v * (v - 1) // 2

    sum_ = sum(ans.values())

    for k in range(len(a)):
        res = sum_ - (cnt[a[k]] - 1)
        print(res)
### BUGGY CODE ###

h,w,k = map(int, input().split())
item = [[0 for _ in range(w)] for _ in range(h)]
for i in range(k):
    y,x,v = list(map(int,input().split()))
    item[y-1][x-1]=v

dp = [[[0 for _ in range(w+1)] for _ in range(h+1)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        for i in range(4):
            dp[0][y+1][x]=max(dp[0][y+1][x],dp[i][y][x])
            dp[i][y][x+1]=max(dp[i][y][x+1],dp[i][y][x])
        for i in range(3):
            dp[0][y+1][x]  =max(dp[0][y+1][x],  dp[i][y][x]+item[y][x])
            dp[i+1][y][x+1]=max(dp[i+1][y][x+1],dp[i][y][x]+item[y][x])
ans=dp[0][-1][-2]
print(ans)

### FIXED CODE ###

h,w,k = map(int, input().split())
item = [[0 for _ in range(w)] for _ in range(h)]
for i in range(k):
    y,x,v = list(map(int,input().split()))
    item[y-1][x-1]=v

dp = [[[0 for _ in range(w)] for _ in range(h)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        for i in range(4):
            if y<h-1:
                dp[0][y+1][x]=max(dp[0][y+1][x],dp[i][y][x])
            if x<w-1:
                dp[i][y][x+1]=max(dp[i][y][x+1],dp[i][y][x])

        if item[y][x]>0:
            for i in range(3):
                if y<h-1:
                    dp[0][y+1][x]=max(dp[0][y+1][x],dp[i][y][x] + item[y][x])
                if x<w-1:
                    dp[i+1][y][x+1]=max(dp[i+1][y][x+1],dp[i][y][x] + item[y][x])

ans=[dp[0][-1][-1] + item[-1][-1],
     dp[1][-1][-1] + item[-1][-1],
     dp[2][-1][-1] + item[-1][-1],
     dp[3][-1][-1]]
print(max(ans))
### BUGGY CODE ###

N, W = map(int, input().split())

w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = {0: 0}
for i in range(N):
    for cw, cv in list(dp.items()):
        if cw + w[i] > W:
            continue
        dp[cw + w[i]] = max(
            dp.get(cw + w[i], 0),
            cv + v[i])
print(max(dp.values()))

### FIXED CODE ###

N, W = map(int, input().split())

w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = {0: 0}
for i in range(N):
    for cv, cw in list(dp.items()):
        if cw + w[i] > W:
            continue
        dp[cv + v[i]] = min(
            dp.get(cv + v[i], float('inf')),
            cw + w[i])
print(max(dp))
### BUGGY CODE ###

H, N= map(int,input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())
ma = max(A)
dp = [0] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        if dp[j] == 0:
            dp[j] = dp[j - a] + b
        else:
            dp[j] = min(dp[j - a] + b, dp[j])
print(min(dp[H:]))


### FIXED CODE ###

H, N= map(int,input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())
ma = max(A)
dp = [float("inf")] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        dp[j] = min(dp[j - a] + b, dp[j])
print(min(dp[H:]))
### BUGGY CODE ###

x = int(input())
temp = int(100)

while temp < x:
    temp *= 0.01

print(temp)

### FIXED CODE ###

import math
x = int(input())
temp = int(100)
ans = int(0)
while temp < x:
    temp += math.floor(temp * 0.01)
    ans += 1
print(ans)