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

n = int(input())
s = input()
count = 0
for i in range(n):
  for j in range(i):
    if s[i] != s[j]:
      for k in range(j):
        if 2*j != i+k and s[j]!=s[k] and s[k]!=s[i]:
          count += 1

print(count)

### FIXED CODE ###

n = int(input())
s = input()
r = []
g = []
b = []

ans = s.count("R")*s.count("G")*s.count("B")

for i in range(n):
    for j in range(i+1,n):
        k = 2*j-i
        if k>=n:
          break
        ans -= s[k] != s[i] != s[j] != s[k]

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

n = int(input())
p = list(map(int, input().split()))

l = int(n/2)

for i in range(l-1):
    t1 = max(p)
    t2 = min(p)
    #print(t1, t2)
    p.remove(t1)
    p.remove(t2)

print(max(p) - min(p))

### FIXED CODE ###

from heapq import nsmallest

n = int(input())
p = list(map(int, input().split()))

m = int(-(n/2))
s = int(n/2)

m2 = sorted(p)[m]
s2 = nsmallest(s, p)[-1]

print(m2-s2)
### BUGGY CODE ###

import sys

input = lambda: sys.stdin.readline().rstrip()

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
F = sorted(list(map(int, input().split())))


def binary_search(min_n, max_n):

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if judge(tn):
            max_n = tn
        else:
            min_n = tn

    return max_n


def judge(tn):

    k = 0
    for i in range(N):
        if A[i] * F[i] > tn:
            k += A[i] - (tn // F[i])
        if k > K:
            return False

    return True


def solve():

    ans = binary_search(-1, 10**12)
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys

input = lambda: sys.stdin.readline().rstrip()

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
F = sorted(list(map(int, input().split())))


def binary_search(min_n, max_n):

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if judge(tn):
            max_n = tn
        else:
            min_n = tn

    return max_n


def judge(tn):

    k = 0
    for i in range(N):
        if A[i] * F[i] > tn:
            k += A[i] - (tn // F[i])
        if k > K:
            return False

    return True


def solve():

    ans = binary_search(-1, 10**12)
    print(ans)


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

h,w,d = map(int,input().split())
n2c = {i:None for i in range(1, h*w+1)}
for i in range(h):
    i += 1
    for j,v in enumerate(input().split()):
        j = j + 1
        v = int(v)
        n2c[v] = (i,j)


def c(x1,y1,x2,y2):
    return abs(x1-x2) + abs(y1-y2)

q = int(input())
for i in range(q):
    cost = 0
    l,r = map(int, input().split())
    lt = range(l,r+1,d)
    l = list(map(lambda x:n2c[x], lt))
    for i in range(len(l)-1):
        x1,y1 = l[i]
        x2,y2 = l[i+1]
        cost += c(x1,y1,x2,y2)
    print(cost) 


### FIXED CODE ###

h,w,d = map(int,input().split())
n2c = {i:None for i in range(1, h*w+1)}
D = [0] * (h * w + 1)
for i in range(h):
    i += 1
    for j,v in enumerate(input().split()):
        j = j + 1
        v = int(v)
        n2c[v] = (i,j)

for i in range(d+1, h*w+1):
    D[i] = D[i - d] + abs(n2c[i][0] - n2c[i-d][0]) + abs(n2c[i][1] - n2c[i-d][1])

def c(x1,y1,x2,y2):
    return abs(x1-x2) + abs(y1-y2)

q = int(input())
for i in range(q):
    l,r = map(int, input().split())
    print(D[r] - D[l])
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
d = defaultdict(int)
for i in A:
    d[i] += 1

ans = 0
for i1,j1 in d.items():
    for i2,j2 in d.items():
        if j1 >= 2 and j2 >= 2 and i1 != i2:
            ans = max(ans,i1*i2)
        elif i1==i2 and j1>=4 and j2>=4:
            ans = max(ans,i1*i2)
print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = []
i = 0
while i+1<N:
    if len(b)==2:
        break
    if a[i] == a[i+1]:
        b += [a[i]]
        i += 2
    else:
        i += 1

if len(b)<2:
    print(0)
else:
    print(b[0]*b[1])
### BUGGY CODE ###


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


val=1
for i in range(len(a)):
    val*=a[i]


print(val if val<=10**18 else '-1')

### FIXED CODE ###


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

    if 0 in A:
        print(0)
        return

    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return

    print(prod)
    return

main ()
### BUGGY CODE ###

# - coding : utf-8 -*-
    
if __name__ == '__main__':
    n, m = map(int, raw_input().split())
    cities = []
    city_lst = {}
    for i in range(0, m):
        p, y = map(int, raw_input().split())
        cities.append((p, y))
        if not p in city_lst:
            city_lst[p] = [y]
        else:
            city_lst[p].append(y)
    for key in city_lst.keys():
        city_lst[key].sort()
    for city in cities:
        print str('%06d' % city[0]) + str('%06d' % (int(city_lst[city[0]].index(city[1]) + 1)))

### FIXED CODE ###

# - coding : utf-8 -*-

if __name__ == '__main__':
    n, m = map(int, raw_input().split())
    cities = []
    for i in range(0, m):
        p, y = map(int, raw_input().split())
        cities.append((y, p, i))
    cities.sort()

    city_codes = [0] * (n + 1)
    postal_codes = [""] * m
    for j in range(0, m):
        y, p, i = cities[j]
        city_codes[p] += 1
        postal_codes[i] = "%06d%06d"%(p, city_codes[p])
    for postal_code in postal_codes:
        print postal_code
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
z = [list(map(int,input().split())) for i in range(q)]
l,r = [list(i) for i in zip(*z)]
p = 0
for i in range(q):
    print(s[l[i]-1:r[i]].count('AC'))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
s = s.replace('AC','ac')
t = [0] * n
r = 0
for i in range(n):
    if s[i] == 'c':
        r += 1
    t[i] = r
for i in range(q):
    l,r = map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

n, m = map(int, input().split())
ll = [[] for _ in range(n) ]

for i in range(n):
    a, b = map(int, input().split())
    ll[i].append(a)
    ll[i].append(b)
i = 0
while i < n-1:
    k = i+1
    while k <= n-1:
        if ll[i][0] > ll[k][0]:
            ll[i], ll[k] = ll[k], ll[i]
        k += 1
    i+=1
s = 0
cst = 0
while m > 0:
    cst += ll[s][0] * ll[s][1]
    m -= ll[s][1]
    s += 1
print(cst + m*ll[s-1][0])

### FIXED CODE ###

n, m = map(int, input().split())
ll = []
for i in range(n):
    l = list(map(int, input().split()))
    ll.append(l)

ll.sort()

t = 0
cst = 0
i = 0
while t < m:
    t += ll[i][1]
    cst += ll[i][0]*ll[i][1]
    if t > m:
        cst -= ll[i][0]*(t-m)
    i += 1
print(cst)
### BUGGY CODE ###

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

from collections import defaultdict, deque

dp = defaultdict(lambda: -1)

q = deque([])
q.append((A, 0))

inf = float("inf")

ans = inf
while q:
    t, cost = q.popleft()
    if len(t) == 0:
        ans = min(ans, cost)
        continue

    if len(t) == 1:
        ans = min(ans, cost + t[0])
        continue

    tpl = t
    for i in range(len(tpl) - 1):
        if not (tpl[0:i] + (tpl[i] + tpl[i + 1],) + tpl[i + 2:], tpl[i] + tpl[i + 1]) in q:
            q.append((tpl[0:i] + (tpl[i] + tpl[i + 1],) + tpl[i + 2:], cost + tpl[i] + tpl[i + 1]))

print(ans - sum(A))
exit(0)



### FIXED CODE ###

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

from itertools import accumulate
Accum = list(accumulate([0] + A))

dp = [ [inf]*(N+1) for _ in range(N+1)]

def dfs(l,r):
    if dp[l][r] != inf:
        return dp[l][r]
    if l == r: 
        return 0
    if l+1 == r: 
        dp[l][r] = A[l]
        return A[l]

    local_ans = inf
    for i in range(l+1, r): # 0 to 4, 0-1, 1-4
        local_ans = min(local_ans, dfs(l,i) + dfs(i,r))
    dp[l][r] = local_ans + Accum[r] - Accum[l]
    return dp[l][r]
print (dfs(0,N)- sum(A))
### BUGGY CODE ###

# coding: utf-8

n = int(input().rstrip())
a_list = list(map(int,input().split()))
money = 2020202020

for i in range(len(a_list)-1):
    x = a_list[:i+1]
    y = a_list[i+1:]
    z = abs(sum(x)-sum(y))
    
    if money > z:
        money = z

print(money)

### FIXED CODE ###

# coding: utf-8

n = map(int,input().split())
a = list(map(int,input().split()))
a_sum = sum(a)
kyoukaisen = a_sum /2
left = 0

for i in range(len(a)):
    left += a[i]
    
    if left >= kyoukaisen:
        print(min(abs(a_sum - 2*left),abs( (a_sum - (left-a[i])) - (a_sum-(a_sum - (left-a[i])))) ))
        break
### BUGGY CODE ###

# C
import numpy as np
from bisect import bisect

x1, y1, x2, y2 = map(int, input().split())
N = int(input())

xL = min(x1, x2)
xR = max(x1, x2)
yL = min(y1, y2)
yR = max(y1, y2)

xv = np.zeros(N, dtype='int')
yv = np.zeros(N, dtype='int')

ind = 0
for _ in range(N):
    x, y = map(int, input().split())
    if xL <= x and x <= xR and yL <= y and y <= yR:
        xv[ind] = x
        yv[ind] = y
        ind += 1

xv = xv[:ind]
yv = yv[:ind]

N = ind



if x1 < x2 and y1 > y2:
    direction = 'rightdown'
elif x1 > x2 and y1 < y2:
    direction = 'rightdown'
else:
    direction = 'rightup'

    
# sort
if direction == 'rightup':
    xv_s = np.argsort(xv)
else:
    xv_s = np.argsort(-xv)

# calculate
dp = [yR+1]*(ind)
for i in range(ind):
    y = yv[xv_s[i]]
    dp[bisect(dp,y)] = y
count_ = bisect(dp,yR)

diff = 5*np.pi - 20
diff2 = 10*np.pi - 20
if count_ == min((xR-xL), (yR-yL)) + 1:
    print(100*((xR-xL) + (yR-yL)) + (count_-1)*diff + diff2)
else:
    print(100*((xR-xL) + (yR-yL)) + count_*diff)

### FIXED CODE ###

# C
from bisect import bisect
import math
x1, y1, x2, y2 = map(int, input().split())
N = int(input())

xL = min(x1, x2)
xR = max(x1, x2)
yL = min(y1, y2)
yR = max(y1, y2)

xyl = []

if x1 < x2 and y1 > y2:
    direction = 'rightdown'
elif x1 > x2 and y1 < y2:
    direction = 'rightdown'
else:
    direction = 'rightup'
    
    
# sort
if direction == 'rightup':
    for _ in range(N):
        x, y = map(int, input().split())
        if xL <= x and x <= xR and yL <= y and y <= yR:
            xyl.append((x, y-yL))
else:
    for _ in range(N):
        x, y = map(int, input().split())
        if xL <= x and x <= xR and yL <= y and y <= yR:
            xyl.append((x, yR-y))

ind = len(xyl)
xyl.sort()

# calculate
dp = [yR-yL+1]*(ind)
for i in range(ind):
    _, y = xyl[i]
    dp[bisect(dp,y)] = y
count_ = bisect(dp,yR-yL)

diff = 5*math.pi - 20
diff2 = 10*math.pi - 20
if count_ == min((xR-xL), (yR-yL)) + 1:
    print(100*((xR-xL) + (yR-yL)) + (count_-1)*diff + diff2)
else:
    print(100*((xR-xL) + (yR-yL)) + count_*diff)
### BUGGY CODE ###

from bisect import bisect_left
def index(a, x):
    i = bisect_left(a,x)
    if i != len(a) and a[i] == x:
        return True
    return False
R, G, B, N = map(int,input().split())
listB = [ i for i in range(N//B+1) ]
cnt = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        v = R*r+G*g
        if (N - v)%B == 0 and index(listB,(N - v)//B):
            cnt += 1
print(cnt)


### FIXED CODE ###

*j, N = map(int,input().split())
j.sort()
a,b,c = j
cnt = 0
for r in range(N//b+1):
    for g in range((N-b*r)//c+1):
        v = b*r+c*g
        if (N-v)%a == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

def gcd(a,b):
	if b == 0:
		return a
	return gcd(b,a%b)

def lcm(a,b):
	p = a*b
	g = gcd(a,b);
	return p//g
MOD = int(10**9+7)
n = int(input())
a = list(map(int,input().split()))
lc = a[0];
for i in range(1,n):
	lc = lcm(a[i],lc)
ans = 0
for i in range(n):
	ans += (lc//a[i])
	ans %= MOD
print(ans)

### FIXED CODE ###

def gcd(a,b):
	if b == 0:
		return a
	return gcd(b,a%b)

def lcm(a,b):
	p = a*b
	g = gcd(a,b);
	return p//g
MOD = int(10**9+7)
n = int(input())
a = list(map(int,input().split()))
lc = a[0];
for i in range(1,n):
	lc = lcm(a[i],lc)
ans = 0
for i in range(n):
	ans += (lc//a[i])
print(ans%MOD)
### BUGGY CODE ###

s = int( input() )
ss = str( s )
l = len( ss )
#print( s, l )

ans = int( 0 )
for i in range( l-4 ):
    for j in range( i+4, l+1 ):
        ssij = ss[ i:j ]
        sij = int( ssij )
#        print( i, j, sij )
        if sij % 2019 == 0:
#            print( "Yes" )
            ans = ans + 1

print( ans )


### FIXED CODE ###

import numpy as np

s = input()

d = [ int( 0 ) ] * 2019
d[ 0 ] = int( 1 )
r = int( 0 )
t = int( 1 )

for si in reversed( s ):
#    print( si )

    r = int( si ) * t + r
    r = r % 2019

    t = t * 10
    t = t % 2019

    d[ r ] = d[ r ] + 1

ans = int( 0 )
for di in d:
    ans = ans + di * ( di - 1 ) // 2

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

n, w = map(int, input().split())
W, V = [], []
for i in range(n):
    wi, vi = map(int, input().split())
    W.append(wi)
    V.append(vi)
    
# Dp[i][sum_w] := i-1 番目までの品物から重さがsum_wを超えないように選んだときの、価値の総和の最大値
Dp = [[0] * (w + 1) for _ in range(n+1)]

for i in range(n):
    for sum_w in range(w+1):
        # i番目の商品を選ぶ場合
        if sum_w - W[i] >= 0:
            Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w - W[i]] + V[i])
        # i番目の商品を選ばない場合
        Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w])
print(Dp[-1][-1])

### FIXED CODE ###

n, w = map(int, input().split())
W, V = [], []
for i in range(n):
    wi, vi = map(int, input().split())
    W.append(wi)
    V.append(vi)
    
# Dp[i][sum_w] := i-1 番目までの品物から重さがsum_wを超えないように選んだときの、価値の総和の最大値
Dp = [[0] * (w + 1) for _ in range(n+1)]

for i in range(n):
    for sum_w in range(w+1):
        # i番目の商品を選ぶ場合
        if sum_w - W[i] >= 0:
            Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w - W[i]] + V[i])
        # i番目の商品を選ばない場合
        Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w])
print(Dp[-1][-1])
### BUGGY CODE ###

n=int(input())
x=[0.0,0.0]
for i in range(n):
  a0,b0=x
  a ,b =[int(i) for i in input().split()]
  if a>=b:
    while a0/a!=a0//a or a0==0 or (a0/a)*b<b0 :
      a0+=1
    x=[a0,(a0/a)*b]
  else:
    while b0/b!=b0//b or b0==0 or (b0/b)*a<a0 :
      b0+=1
    x=[(b0/b)*a,b0]
print(int(sum(x)))

### FIXED CODE ###

import math
from fractions import Fraction
n=int(input())
x=[1,1]
for i in range(n):
  a0,b0=x
  a ,b =[int(i) for i in input().split()]
  m=math.ceil(max(Fraction(a0,a),Fraction(b0,b)))
  x=[m*a,m*b]
  
print(int(sum(x)))
### BUGGY CODE ###

n = int(input())
k = int(input())


def f(n, k):
    assert n >= 0 #例外処理
    if n < 10:
        if k == 0:
            return 1 #0しかない数 = 0
        elif k == 1:
            return n #k = 1ならn個分存在している
        return 0 #k >= 2のときは、0を返す
    
    q, r = divmod(n, 10)
    res = 0
    
    if k >= 1:
        #1の位が0でないとき
        res += f(q, k-1) * r
        res += f(q-1, k-1) * (9 - r)
    #１の位が0
    res += f(q, k)
    return res

print(f(n, k))

### FIXED CODE ###

#maspyさんのやつ

from functools import lru_cache

n = int(input())
k = int(input())

@lru_cache(None)
def f(n, k):
    assert n >= 0 #例外処理
    if n < 10:
        if k == 0:
            return 1 #0しかない数 = 0
        elif k == 1:
            return n #k = 1ならn個分存在している
        return 0 #k >= 2のときは、0を返す
    
    q, r = divmod(n, 10)
    res = 0
    
    if k >= 1:
        #1の位が0でないとき
        res += f(q, k-1) * r
        res += f(q-1, k-1) * (9 - r)
    #１の位が0
    res += f(q, k)
    return res

print(f(n, k))
### BUGGY CODE ###

from scipy.sparse import lil_matrix
import sys
input = sys.stdin.readline

N = int(input())
edge = lil_matrix((N+1,N+1))
 
for _ in range(N-1):
  a,b,c = map(int,input().split())
  edge[a,b] = c
 
Q,K = map(int,input().split())
 
from scipy.sparse.csgraph import dijkstra
dist = dijkstra(edge,directed = False, indices = K).astype(int)
 
for _ in range(Q):
  x,y = map(int,input().split())
  print(dist[x] + dist[y])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

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

dist = [None]*(N+1)

def set_dist(x,d):
  dist[x] = d
  for y,dd in edge[x]:
    if dist[y] is not None:
      continue
    set_dist(y,d+dd)

set_dist(K,0)

for _ in range(Q):
  x,y = map(int,input().split())
  print(dist[x] + dist[y])
### BUGGY CODE ###

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

mod = 10**9 + 7

def chs(a,b, md):
    res = 1
    for i in range(a-b+1,a+1):
        res *=  i
        res %= md
    rev = 1
    for i in range(1,b+1):
        rev *= i
        rev %= md
    rev2 = pow(rev,md-2,md)
    
    res *= rev2
    res %= md
    
    return res

ans = 0

for i in range(1,n):
    ans += chs(n*m-2,k-2,mod)*i*(n-i)*m**2
    ans %= mod

        

for i in range(1,m):
    ans += chs(n*m-2,k-2,mod)*i*(m-i)*n**2
    ans %=mod
    
print(ans)


### FIXED CODE ###

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

mod = 10**9 + 7

def chs(a,b, md):
    res = 1
    for i in range(a-b+1,a+1):
        res *=  i
        res %= md
    rev = 1
    for i in range(1,b+1):
        rev *= i
        rev %= md
    rev2 = pow(rev,md-2,md)
    
    res *= rev2
    res %= md
    
    return res

ans = 0
c = chs(n*m-2,k-2,mod)

for i in range(1,n):
    ans += i*(n-i)*m**2
    ans %= mod

        

for i in range(1,m):
    ans +=i*(m-i)*n**2
    ans %=mod
ans *= c
ans %= mod
print(ans)
### BUGGY CODE ###

import sys
from bisect import insort_left
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    # a = [int(i) for i in input().split()]
    # a.sort()
    a = []
    for i in map(int, input().split()):
        insort_left(a, i)
    for _ in range(m):
        b = a.pop()//2
        insort_left(a, b)
    print(sum(a))


main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

import numpy as np

def main():
    n, m = map(int, input().split())
    a = np.array([int(i) for i in input().split()])
    a.sort()

    while True:
        temp = a[-1]//2
        a[-1] //= 2
        a.sort()
        ind = np.where(a==temp)[0][0]
        m -= 1
        if m == 0:
            print(np.sum(a))
            break
        elif n - ind < m:
            a[ind:] = a[ind:]//2
            a.sort()
            m = m - (n-ind)
        else:
            a[-m:] = a[-m:]//2
            print(np.sum(a))
            break

main()
### BUGGY CODE ###

import math

Num,HP = (map(int,input().split()))
Katanas = [list(map(int,input().split())) for x in range(Num)]

amax = max([x[0] for x in Katanas])
bpower = sorted([x[1] for x in Katanas if x[1] > amax],reverse=True)
bsum = sum(bpower)
if bsum > HP:
    attake = 0
    while HP > 0:
        attake += 1
        HP -= bpower[0]
        bpower = bpower[1:]
else:
    attake = math.ceil((HP-bsum)/amax)+len(bpower)
print(attake)

### FIXED CODE ###

import math

Num,HP = (map(int,input().split()))
#Katanas = [list(map(int,input().split())) for _ in range(Num)]

CKatanaMax = 0
katanas = []

for _ in range(Num):
    a,b = map(int,input().split())
    CKatanaMax = max(CKatanaMax,a)
    katanas.append(b)

Tkatanas = sorted([x for x in katanas if x > CKatanaMax],reverse=True)

attake = 0
for Tkatana in Tkatanas:
    HP -= Tkatana
    attake += 1
    if HP <= 0:
        break
else:
    attake += math.ceil(HP/CKatanaMax)
print(attake)
### BUGGY CODE ###

S = input()
count = 0
S_len = len(S)
for i in range(S_len):
    for j in range(i+4,S_len+1):
        if int(S[i:j]) % 2019 == 0:
            count += 1

print(count)

### FIXED CODE ###

S = input()
MOD =2019
count = [0]*MOD
r = 0
t = 1
for i in reversed(S):
    r += int(i) * t
    r %= MOD
    t *= 10
    t %= MOD
    count[r] += 1

count[0] += 1
print(int(sum(i*(i-1)/2 for i in count)))
### BUGGY CODE ###

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

dic = {}
one = []
for i in range(N):
	if not A[i] in one:
		one.append(A[i])

ans = len(one)
print(ans - ((ans+1) % 2))





### FIXED CODE ###

N = int(input())
A = list(map(int,input().split(" ")))
print(len(set(A)) - ((len(set(A))+1) % 2))
### BUGGY CODE ###

from collections import defaultdict

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [[float('inf') for _ in range(H + max(AB)[0] + 1)] for _ in range(N + 1)]
dp[0][0] = 0
for n in range(N):
    for h in range(H + max(AB)[0] + 1):
        if h - AB[n][0] >= 0:
            dp[n + 1][h] = min(dp[n + 1][h - AB[n][0]] + AB[n][1], dp[n][h])
        else:
            dp[n + 1][h] = dp[n][h]

print(min(dp[N][H:]))


### FIXED CODE ###

import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [0 for _ in range(H + max(AB, key=lambda x: x[0])[0])]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print(dp[H])
### BUGGY CODE ###

N = int(input())

def ryuka(N):
  if N == 1:
    return 1
  if N == 0:
    return 2
  return ryuka(N-1) + ryuka(N-2)


print(ryuka(N))

### FIXED CODE ###

N = int(input())

ryuka = [0] * 100
ryuka[0] = 2
ryuka[1] = 1

for i in range(2, 87):
  ryuka[i] = ryuka[i-1] + ryuka[i - 2]


print(ryuka[N])
### BUGGY CODE ###

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

for _ in range(min(K, 100)):
    b = [0]*N
    for i, a in enumerate(A):
        for j in range(max(i-a, 0), min(a+i+1, N)):
            b[j] += 1
    A = b

print(" ".join(str(a) for a in A))


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
c = [0]*N

for _ in range(min(K, 100)):
    b = [0]*(N+1)
    for i, a in enumerate(A):
        b[max(i-a, 0)] += 1
        b[min(i+a+1, N)] -= 1
    
    x = 0
    for i in range(N):
        x += b[i]
        A[i] = x

print(" ".join(str(a) for a in A))
### BUGGY CODE ###

a, b = map(int, input().split()) 
for i in range(10**9+1):
  if abs(a-i) == abs(b-i):
    print(i)
    exit()

print("IMPOSSIBLE")

### FIXED CODE ###

a, b = map(int, input().split()) 

if (a+b)%2 == 0:
  print((a+b)//2)
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

n = int(input())

mod = 10**9+7
ans = 1

for i in range(n):
    ans *= (i+1)



print(ans%mod)

### FIXED CODE ###

n = int(input())

mod = 10**9+7
ans = 1

for i in range(n):
    ans *= (i+1)
    ans %= mod



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

import sys
import bisect

N, Q = map(int, input().split(' '))
G = [list(map(int, sys.stdin.readline().split(' '))) for _ in range(N)]
T = [int(sys.stdin.readline()) for _ in range(Q)]

G.sort(key = lambda x : -x[2])
T.sort()


A = [-2] * (4 * Q + 5)

def update(i, l, r, ll, rr, val) :
    if r <= ll or rr <= l :
        return
    if ll <= l and r <= rr :
        A[i] = val
        return

    if A[i] != -2 :
        A[i * 2] = A[i * 2 + 1] = A[i]
        A[i] = -2

    m = (l + r) // 2
    update(i * 2, l, m, ll, rr, val)
    update(i * 2 + 1, m, r, ll, rr, val)

def get(i, l, r, p) :
    if A[i] != -2 or l + 1 == r :
        return A[i]
    m = (l+r) // 2
    if p < m :
        return get(i * 2, l, m, p)
    else :
        return get(i * 2 + 1, m, r, p)

for g in G :
    s = max(0, g[0] - g[2])
    e = g[1] - g[2]
    if e <= 0 :
        continue

    ll = bisect.bisect_left(T, s)
    rr = bisect.bisect_left(T, e)

    if ll == rr :
        continue

    update(1, 0, Q, ll, rr, g[2])

for i in range(Q) :
    ans = get(1, 0, Q, i)
    if ans == -2 :
        print(-1)
    else :
        print(ans)


### FIXED CODE ###

import sys
import bisect
 
N, Q = map(int, input().split(' '))
G = [list(map(int, sys.stdin.readline().split(' '))) for _ in range(N)]
T = [int(sys.stdin.readline()) for _ in range(Q)]

class SegTree :
    def __init__(self, n) :
        self.n = n
        self.A = [10**15] * (2 << (n + 1).bit_length())
 
    def update(self, l, r, val) :
      l += len(self.A) // 2
      r += len(self.A) // 2
      while l < r:
          if l & 1 :
              self.A[l] = min(self.A[l], val)
              l += 1
          if r & 1:
              self.A[r-1] = min(self.A[r-1], val)
              r -= 1
          l //= 2
          r //= 2

    def get(self, i) :
      i += len(self.A) // 2
      ret = self.A[i]
      while i > 0 :
          i //= 2
          ret = min(ret, self.A[i])
      return ret if ret < 10**15 else -1

ST = SegTree(Q)
for g in G :
    s = g[0] - g[2]
    e = g[1] - g[2]
 
    ll = bisect.bisect_left(T, s)
    rr = bisect.bisect_left(T, e)
 
    if ll == rr :
        continue
 
    ST.update(ll, rr, g[2])
 
for i in range(Q) :
    ans = ST.get(i)
    print(ans)