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

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


total = 0
N = int(input())
for i in range(1, N+1):
    for j in range(1, N+1):
        x = gcd(i, j)
        for k in range(1, N+1):
            total += gcd(x, k)

print(total)


### FIXED CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


total = 0
N = int(input())
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            total += gcd(i, j, k)

print(total)
### BUGGY CODE ###

def mod_inv(a, m):
    return pow(a,m-2,m)


X, Y = map(int, input().split())
MOD = 10 ** 9 + 7

if (X + Y) % 3:
    print(0)
    exit()

n = (X + Y) // 3
nx, ny = X - n, Y - n

if nx < 0 or ny < 0:
    print(0)
    exit()

ans = 1
for i in range(1, nx + ny + 1):
    ans = ans * i % MOD
for i in range(1, nx + 1):
    ans = ans * mod_inv(i, MOD) % MOD
for i in range(1, ny + 1):
    ans = ans * mod_inv(i, MOD) % MOD

print(ans)

### FIXED CODE ###

def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


X, Y = map(int, input().split())
MOD = 10 ** 9 + 7

if (X + Y) % 3:
    print(0)
    exit()

n = (X + Y) // 3
nx, ny = X - n, Y - n

if nx < 0 or ny < 0:
    print(0)
    exit()

ans = 1
for i in range(1, nx + ny + 1):
    ans = ans * i % MOD
for i in range(1, nx + 1):
    ans = ans * mod_inv(i, MOD) % MOD
for i in range(1, ny + 1):
    ans = ans * mod_inv(i, MOD) % MOD

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

import sys
sys.setrecursionlimit(10000)
N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]
PX = [list(map(int, input().split())) for _ in range(Q)]

chil = [[] for _ in range(N+1)]
count = [0]*(N+1)

for ab in AB:
    chil[ab[0]].append(ab[1])
    chil[ab[1]].append(ab[0])

def cleanse(fromN, toN):
    chil[toN].remove(fromN)
    if len(chil[toN])==0:
        return
    for node in chil[toN]:
        cleanse(toN, node)

for node in chil[1]:
    cleanse(1, node)

def addition(fromN, toN):
    count[toN] += count[fromN]
    if len(chil[toN])==0:
        return
    for node in chil[toN]:
        addition(toN, node)
        
for px in PX:
    count[px[0]] += px[1]

for node in chil[1]:
    addition(1, node)

print(*count[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, Q = map(int, input().split())

edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

points = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    points[p-1] += x

def dfs(v, par):
    for nv in edges[v]:
        if nv == par:
            continue
        points[nv] += points[v]
        dfs(nv, v)

dfs(0, -1)

print(*points)
### BUGGY CODE ###

def get_survivors(n, pairs):
    survivors = {v: {v} for v in range(n)}
    for x, y in reversed(pairs):
        for v, srv in survivors.copy().items():
            if x in srv:
                if y in srv:
                    del survivors[v]
                else:
                    srv.add(y)
            elif y in srv:
                srv.add(x)
    return survivors


def solve(n, pairs):
    survivors = get_survivors(n, pairs)
    ans = 0
    for u, su in survivors.items():
        for v, sv in survivors.items():
            if u >= v:
                continue
            if su.isdisjoint(sv):
                ans += 1
    return ans


n, m = map(int, input().split())
pairs = []
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    pairs.append((x, y))
print(solve(n, pairs))


### FIXED CODE ###

def get_survivors(n, pairs):
    survivors = {v: {v} for v in range(n)}
    for x, y in reversed(pairs):
        for v, srv in survivors.copy().items():
            if x in srv:
                if y in srv:
                    del survivors[v]
                else:
                    srv.add(y)
            elif y in srv:
                srv.add(x)
    return survivors


def solve(n, pairs):
    survivors = get_survivors(n, pairs)
    ans = 0
    for u, su in survivors.items():
        for v, sv in survivors.items():
            if u >= v:
                continue
            if su.isdisjoint(sv):
                ans += 1
    return ans


n, m = map(int, input().split())
pairs = []
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    pairs.append((x, y))
print(solve(n, pairs))
### BUGGY CODE ###

N=int(input())

ans=0
for i in range(1,N+1):
    for j in range(1,N):
        if i <j:
            continue
        for k in range(1,N):
            if i <k:
                continue
            for l in range(1,N):
                if i <l:
                    continue
                if l**2+j**2+k**2+l*j+j*k+k*l==i:
                    ans+=1
    print(ans)
    ans=0

### FIXED CODE ###

N=int(input())

ans=[0]*N

for i in range(1,int(N**0.5)):
    if i**2 >=N:
        break
    for j in range(1,int(N**0.5)):
            if i**2+j**2+i*j>=N:
                break
            for k in range(1,int(N**0.5)):
                    if i**2+j**2+k**2+i*j+j*k+k*i <=N:
                        ans[i**2+j**2+k**2+i*j+j*k+k*i-1] +=1

for i in range(N):
    print(ans[i])
### BUGGY CODE ###

N=int(input())
S=input()
R=[]
G=[]
B=[]
count=1
for i in S:
    if i=="R":
        R.append(count)
    if i=="G":
        G.append(count)
    if i=="B":
        B.append(count)
    count+=1
x=0
for j in R:
    for k in G:
        if 2*j-k in B:
            x+=1
        if 2*k-j in B:
            x+=1
        if (k+j)/2==(k+j)//2 and (k+j)//2 in B:
            x+=1
print(len(R)*len(G)*len(B)-x)


    









        

    









    

        




    















    



    





    






        






    
















        


























            
    


    


    
    














    


    














### FIXED CODE ###

N=int(input())
S=list(input())
S.insert(0,0)
R=S.count("R")
G=S.count("G")
B=S.count("B")
ans=R*G*B
for i in range(1,N-1):
    for j in range(i+1,N):
        k=2*j-i
        if k<N+1 and S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            ans-=1
print(ans)
### BUGGY CODE ###

s=input()[::-1]
mod=10**9+7
n=13
dp=[0]*n
mul=1
dp[0]=1
for c in s:
  ndp=[0]*n
  if c=='?':
    for k in range(10):
      for j in range(n):
        ndp[(k*mul+j)%n]=(ndp[(k*mul+j)%n]+dp[j])%mod
        #ndp[(k*mul+j)%n]%=mod
  else:
    k=int(c)
    for j in range(n):
      ndp[(k*mul+j)%n]=(ndp[(k*mul+j)%n]+dp[j])%mod
      #ndp[(k*mul+j)%n]%=mod
  mul*=10
  mul%=n
  dp=ndp
print(dp[5])


### FIXED CODE ###

M=10**9+7
r=[[(j-k)*9%13for j in range(10)]for k in range(13)]
d=[1]+[0]*12
for c in input():
  d = [sum(d[j]for j in k)%M for k in r] if c>'9' else [d[(int(c)-k)*9%13]for k in range(13)]
print(d[5])
### BUGGY CODE ###

n, k = map(int, input().split())
arr = [int(_)*(int(_)+1)/(int(_)*2.0) for _ in input().split()]
max = 0

for i in range(0, n-k+1):
  t = sum(arr[i:i+k])
  if max < t:
    max = t

print(max)

### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
arr = np.array([int(_)*(int(_)+1)/(int(_)*2.0) for _ in input().split()])

max = t = sum(arr[0:k])

for i in range(1, n-k+1):
  t += arr[i+k-1]
  t -= arr[i-1]
  if max < t:
    max = t

print(max)
### BUGGY CODE ###

import numpy as np
import copy
N=int(input())
l=list(map(int, input().split())) 

cp = copy.copy(l)
 
if l[0]!=0:

  for k in range(1,N):
    if sum(l[:k])*sum(l[:k+1])>0:
      l[k]=-np.sign(sum(l[:k]))-sum(l[:k])

  if sum(l)==0:
    print(1+sum([abs(l[n]-cp[n]) for n in range(N)]))
  else:
    print(sum([abs(l[n]-cp[n]) for n in range(N)]))

  
else:#頭0のとき；和0なので変える =>1,-1にした時両方やって良いほうに
  #1にする場合
  sei_l=copy.copy(l)
  sei_l[0]=1
  for k in range(1,N):

    if sum(sei_l[:k])*sum(sei_l[:k+1])>0:

      sei_l[k]=-np.sign(sum(sei_l[:k]))-sum(sei_l[:k])

  if sum(sei_l)==0:
    c1=1+sum([abs(sei_l[n]-cp[n]) for n in range(N)])
  else:
    c1=sum([abs(sei_l[n]-cp[n]) for n in range(N)])  

  #-1にする場合
  fu_l=copy.copy(l)
  sei_l[0]=-1
  for k in range(1,N):

    if sum(fu_l[:k])*sum(fu_l[:k+1])>0:

      fu_l[k]=-np.sign(sum(fu_l[:k]))-sum(fu_l[:k])

  if sum(fu_l)==0:
    c2=1+sum([abs(fu_l[n]-cp[n]) for n in range(N)])
  else:
    c2=sum([abs(fu_l[n]-cp[n]) for n in range(N)])  
  
  print(max(c1,c2))


### FIXED CODE ###

from copy import copy
n = int(input())
a = [int(x) for x in input().split()]
ans1=[(-1)**i for i in range(n)]

b=copy(a)
res_b=0
sb=0
c=copy(a)
res_c=0
sc=0
for i in range(n):
  sb+=a[i]
  if ans1[i]*sb>0:
    pass
  else:
    b[i]=ans1[i]-(sb-b[i])
    sb=sb-a[i]+b[i]
    res_b+=abs(b[i]-a[i])

  sc+=a[i]
  if -1*ans1[i]*sc>0:
    pass
  else:
    c[i]=-1*ans1[i]-(sc-c[i])
    sc=sc-a[i]+c[i]
    res_c+=abs(c[i]-a[i])
  
print(min(res_b,res_c))
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
s_default = N
s_plus = M // 2

# now_make = min(s_default, M//2)
# print(now_make)

ans = 0
for n in range(M//2 + 1):
    A, B = N + n, M - 2 * n
    mi = min(A, B//2)
    ans = max(mi, ans)
print(ans)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

Scc = min(N, M // 2)
N = N - Scc
M = M - Scc * 2
if N == 0:
    ans = Scc + M // 4
else:
    ans = Scc
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append([s for s in input()])
    
left = [[0 for _ in range(W)] for _ in range(H)]
right = [[0 for _ in range(W)] for _ in range(H)]
up = [[0 for _ in range(W)] for _ in range(H)]
down = [[0 for _ in range(W)] for _ in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == ".":
            if w == 0:
                left[h][w] = 1
            else:
                left[h][w] += left[h][w - 1] + 1
        else:
            left[h][w] = 0

for h in range(H):
    for w in range(W)[::-1]:
        if grid[h][w] == ".":
            if w == W - 1:
                right[h][w] = 1
            else:
                right[h][w] += right[h][w + 1] + 1
        else:
            right[h][w] = 0
            
for w in range(W):
    for h in range(H):
        if grid[h][w] == ".":
            if h == 0:
                up[h][w] = 1
            else:
                up[h][w] += up[h - 1][w] + 1
        else:
            up[h][w] = 0

for w in range(W):
    for h in range(H)[::-1]:
        if grid[h][w] == ".":
            if h == H - 1:
                down[h][w] = 1
            else:
                down[h][w] += down[h + 1][w] + 1
        else:
            down[h][w] = 0

ans = -10000
for h in range(H):
    for w in range(W):
        ans = max(ans, up[h][w] + down[h][w] + right[h][w] + left[h][w] - 3)
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append([s for s in input()])
    
left = [[0 for _ in range(W)] for _ in range(H)]
right = [[0 for _ in range(W)] for _ in range(H)]
up = [[0 for _ in range(W)] for _ in range(H)]
down = [[0 for _ in range(W)] for _ in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == ".":
            if w == 0:
                left[h][w] = 1
            else:
                left[h][w] += left[h][w - 1] + 1

for h in range(H):
    for w in range(W)[::-1]:
        if grid[h][w] == ".":
            if w == W - 1:
                right[h][w] = 1
            else:
                right[h][w] += right[h][w + 1] + 1
            
for w in range(W):
    for h in range(H):
        if grid[h][w] == ".":
            if h == 0:
                up[h][w] = 1
            else:
                up[h][w] += up[h - 1][w] + 1
                
for w in range(W):
    for h in range(H)[::-1]:
        if grid[h][w] == ".":
            if h == H - 1:
                down[h][w] = 1
            else:
                down[h][w] += down[h + 1][w] + 1
                
ans = -10000
for h in range(H):
    for w in range(W):
        ans = max(ans, up[h][w] + down[h][w] + right[h][w] + left[h][w] - 3)
print(ans)
### BUGGY CODE ###

n = int(input())
p = 1
wari = 10**9+7
for i in range( 1,n + 1):
	p  *= i
print(str(p%wari))

### FIXED CODE ###

n = int(input())
p = 1
wari = 10**9+7
for i in range( 1,n + 1):
	p  = (p*i)%wari
print(str(p%wari))
### BUGGY CODE ###

F = {}

def fib(n):
  global F
  if n < 0:
    print("error")
    exit()
  if n < 2:
    F[n] = 1
    return F[n]
  F[n] = fib(n-1) + fib(n-2)
  return F[n]

#n = int(input())
#print(fib(n))
#n = int(input())
#print(fib(n))
fib(44)
for i in range(5+1):
  print(F[i])

### FIXED CODE ###

def fibr(n):
    if arr[n] != 0:
        return arr[n]
    if n < 2:
        arr[n] = 1
    else:
        arr[n] = fibr(n-1) + fibr(n-2)
    return arr[n]

n = int(input())
arr = [0 for i in range(n+1)]
print(fibr(n))
### BUGGY CODE ###

from math import sqrt

x = int(input())
sqrt_x = int(x)

ans = 1
for b in range(sqrt_x):
    for p in range(sqrt_x-1):
  
        exp = (b+1)**(p+2)

        if exp<=x and ans<=exp:
            ans = exp

print(ans)

### FIXED CODE ###

X = int(input())

score =0
half_x = round(X/2)

answer = 0

if X < 3:
    print(1)

elif X <= 8:
    print(2)

else:
    while 1 < half_x:
        half_x -= 1
        
        for p in range(2, 10):
            
            score = pow(half_x,p)
            if score > X:
                continue
        
            if answer < score:
                answer = score
                
    print(answer)
### BUGGY CODE ###

S=list(input())
Q=int(input())
cnt=0
for i in range(Q):  
  L=list(input().split())  
  if L[0]=="1":
    cnt+=1
  else:
    if cnt%2==1:
      S=list(reversed(S))
      cnt=0
    if L[1]=="1":
      S=list(L[2])+S
    else:
      S=S+list(L[2])
if cnt%2==1:
  S=list(reversed(S))
ans=''.join(S)
print(ans)

### FIXED CODE ###

import collections

s = collections.deque(list(input()))
q = int(input())
rev = 0
for i in range(q):
    tfc = list(input().split())
    if tfc[0]=='1':
        rev = abs(rev-1)
    else:
        t,f,c = tfc
        if rev:
            if f=='1':
                s.append(c)
            else:
                s.appendleft(c)
        else:
            if f=='1':
                s.appendleft(c)
            else:
                s.append(c)
if rev:
    t = []
    for i in range(len(s)):
        t.append(s.pop())
    print(''.join(t))
else:
    print(''.join(s))
'''
初期文字列 s が与えられ q 個のクエリを処理した後の文字列を求めます。
10^100回繰り返す根気があるなら自分でやってくれと思わなくもないです。
さて、各クエリではまず t が与えられます。t=1の時文字列を反転させます。
t=2の時はさらに f,c が与えられ、f=1の時文字列の先頭にcを加えます。
f=2の時文字列の末尾にcを加えます。
愚直に行おうとすると文字列の反転で O(len(s))、先頭への追加で 
O(len(s)) かかってしまい間に合いません。
そこでcollections.dequeを利用します。先頭、末尾への追加をO(1) で行えます。
注意する点は反転させると追加する位置が逆になることです。
なので現在の状態を管理しておく必要があります。
同様に出力する時も最終的な向きによって出力する順番が逆になります。
'''
### BUGGY CODE ###

X = int(input())
# X > 0 なのでマイナス方向にジャンプする選択肢は選ばない
cnt = 0
while X != 0:
    if X != cnt + 1:
        X -= cnt
    cnt += 1
print(cnt - 1)


### FIXED CODE ###

X = int(input())
acc = 0
# X > 0 なのでマイナス方向にジャンプする選択肢は選ばない
for i in range(X + 1):
    acc += i
    if X <= acc:
        ans = i
        break
print(i)
### BUGGY CODE ###

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

def main():
    N,M,K = [int(i) for i in input().strip().split()]
    A = [int(i) for i in input().strip().split()]
    B = [int(i) for i in input().strip().split()]

    pre_A = [0] * (N + 1)
    pre_B = [0] * (M + 1)


    for i in range(1,N+1):
        pre_A[i] = pre_A[i-1] + A[i-1]
    for i in range(1,M+1):
        pre_B[i]= pre_B[i-1] + B[i-1]

    ans = 0

    for i in range(N+1):
        for j in range(M+1):
            if pre_A[i] + pre_B[j] <= K:
                ans = max(ans,i+j)
            else:
                break

    return ans

if __name__ == "__main__":
    print(main())

### FIXED CODE ###

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

def main():
    N,M,K = [int(i) for i in input().strip().split()]
    A = [int(i) for i in input().strip().split()]
    B = [int(i) for i in input().strip().split()]

    pre_A = [0] * (N + 1)
    pre_B = [0] * (M + 1)


    for i in range(1,N+1):
        pre_A[i] = pre_A[i-1] + A[i-1]
        if pre_A[i] > K:
            idx_a = i-1
            break
    else:
        idx_a = N

    for i in range(1,M+1):
        pre_B[i]= pre_B[i-1] + B[i-1]
        if pre_B[i] > K:
            idx_b = i-1
            break
    else:
        idx_b = M

    ans = max(idx_a,idx_b)

    j = idx_b
    for i in range(idx_a + 1):
        while pre_B[j] > K - pre_A[i]:
            j -= 1
        ans = max(ans,i+j)

    return ans

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

N,K = [int(i) for i in input().split()]
list = []

for i in range(N):
    a,b = [int(i) for i in input().split()]
    for _ in range(b):
        list.append(a)

list.sort()
print(list[K-1])


### FIXED CODE ###

N,K = [int(i) for i in input().split()]
dic = {}
sum = 0

for i in range(N):
    a,b = [int(i) for i in input().split()]
    if a in dic:
        dic[a] += b
    else:
        dic[a] = b

dic = sorted(dic.items())

for i in range(len(dic)):
    sum += dic[i][1]
    if K <= sum:
        print(dic[i][0])
        break
### BUGGY CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
            
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)


### FIXED CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

def parent(i):return (i - 1) // 2
def left(i):return  2 * i + 1
def right(i):return  2 * i + 2
def max_heapify(a, i):
    l = left(i)
    r = right(i)
    largest = l if  l < len(a) and a[l] > a[i] else i
    largest = r if  r < len(a) and a[r] > a[largest] else largest
    
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest)
        
def build_max_heap(a):
    for i in range(len(a) // 2, -1, -1):
        max_heapify(a, i)
def max_heap_insert(a, key):
    a.append(key)
    heap_increase_key(a)
def heap_increase_key(a):
    i = len(a) - 1
    while i > 0 and a[parent(i)] < a[i]:
        a[i], a[parent(i)] = a[parent(i)], a[i]
        i = parent(i)
def heap_extract_max(a):
    if  len(a)  == 0:
        raise Exception
    max_heap = a[0]
    a[0] = a[-1]
    a.pop(-1)
    max_heapify(a, 0)
    return max_heap

a = []
while True:
    command = input().split()
    if command[0] == 'insert':
        max_heap_insert(a, int(command[1]))
    elif command[0] == 'extract':
        print(heap_extract_max(a))
    else:
        break

### FIXED CODE ###

from sys import stdin
from heapq import heappop, heappush
readline = stdin.readline


heap = []
while True:
    line = readline()
    if line[1] == 'x':print(-heappop(heap))
    elif line[0] == 'i':heappush(heap, -int(line.split()[1]))
    else:break
### BUGGY CODE ###

n = int(input())
s = input()
sum = s.count("R") * s.count("G") * s.count("B")
for i in range(1, n-1):
  for j in range(i+1, n):
    if(s[i-1] == s[j-1] or 2*j-i-1 >= n):
      continue
    k = {"R", "G", "B"} - {s[i-1], s[j-1]}
    k = k.pop()
    if(s[2*j-i-1] == k):
      sum -= 1
print(sum)

### FIXED CODE ###

n = int(input())
s = input()
sum = s.count("R") * s.count("G") * s.count("B")
for i in range(1, n-1):
  for j in range(i+1, n):
    k = 2*j-i-1
    if(k >= n):
      break
    if(len({s[i-1], s[j-1], s[k]}) == 3):
        sum -= 1
print(sum)
### BUGGY CODE ###

import sys
import bisect

input = sys.stdin.readline

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

STX = [list(map(int, input().split())) for _ in range(N)]
# xの昇順に工事の区間をsort
STX = sorted(STX, key=lambda x: x[2])

D = [int(input()) for _ in range(Q)]
ans = [-1] * Q
for s, t, x in STX:
    left = bisect.bisect_left(D, s - x - 0.5)
    right = bisect.bisect_left(D, t - x - 0.5)
    
    for i in range(left, right):
        if ans[i] == -1:
            ans[i] = x

for a in ans:
    print(a)

### FIXED CODE ###

import sys
import bisect

input = sys.stdin.readline

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

STX = [list(map(int, input().split())) for _ in range(N)]
# xの昇順に工事の区間をsort
STX = sorted(STX, key=lambda x: x[2])

D = [int(input()) for _ in range(Q)]
ans = [-1] * Q
index = [-1] * Q
for s, t, x in STX:
    left = bisect.bisect_left(D, s - x - 0.5)
    right = bisect.bisect_left(D, t - x - 0.5)
    now = left
    while now < right:
        if index[now] == -1:  # まだansが更新されていない場合
            ans[now] = x
            index[now] = right
            now += 1
        else:
            now = index[now]
            

for a in ans:
    print(a)
### BUGGY CODE ###

def main():
  import sys
  input=sys.stdin.readline
  
  h,n=map(int,input().split())
  AB=tuple([list(map(int,input().split()))for _ in range(n)])
  
  DP=[float("inf") for _ in range(h+2)]
  DP[0]=0
  for i in range(1,h+2):
    for a,b in AB:
      if i<=a:
        DP[i]=min(DP[i],b)
      else:
        DP[i]=min(DP[i],DP[i-a]+b)
        
  print(DP[h])
  
if __name__=="__main__":
  main()

### FIXED CODE ###

def main():
  
  h,n=map(int,input().split())
  AB=tuple([list(map(int,input().split()))for _ in range(n)])
  
  DP=[float("inf") for _ in range(h+2)]
  DP[0]=0
  for i in range(1,h+2):
    for a,b in AB:
      if i<=a:
        DP[i]=min(DP[i],b)
      else:
        DP[i]=min(DP[i],DP[i-a]+b)
        
  print(DP[h])
  
if __name__=="__main__":
  main()