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

def password():
    for i in range(10):
        for j in range(10):
            for k in range(10):
                yield [str(i), str(j), str(k)]


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

ans = 0
for perm in password():
    j = 0
    for i in range(len(s)):
        if perm[j] == s[i]:
            j += 1
            if j >= len(perm):
                break
    if j >= len(perm):
        ans += 1

print(ans)


### FIXED CODE ###

def password():
    for i in range(10):
        for j in range(10):
            for k in range(10):
                yield [str(i), str(j), str(k)]


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

ans = 0
for perm in password():
    if perm[0] in s:
        a = s.find(perm[0])
        if perm[1] in s[a + 1 :]:
            b = s[a + 1 :].find(perm[1])
            if perm[2] in s[a + 1 :][b + 1 :]:
                ans += 1

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

from functools import reduce

result = 0

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

n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    result = max(result, reduce(gcd, A[:i]+A[i+1:]))

print(result)

### FIXED CODE ###

from functools import reduce

result = 0

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

n = int(input())
A = list(map(int, input().split()))
X = [0 for i in range(n)]
Y = [0 for i in range(n)]
for i in range(1, n):
    X[i] = gcd(X[i-1], A[i-1])
for i in range(n-1)[::-1]:
    Y[i] = gcd(Y[i+1], A[i+1])
print(max(gcd(X[i], Y[i]) for i in range(n)))
### BUGGY CODE ###

R = [0]*2019
s = input()

res = 0
for d in map(int, s):
    new = [0]*2019
    for i in range(2019):
        new[(i*10 + d)%2019] += R[i]
    new[d] += 1
    res += new[0]
    R = new
print(res)



### FIXED CODE ###

R = [0]*2019
s = input()

res = 0
for d in map(int, s):
    new = [0]*2019
    for i in range(2019):
        new[(i*10 + d)%2019] += R[i]
    new[d] += 1
    res += new[0]
    R = new
print(res)
### BUGGY CODE ###

from collections import deque

class Node:
    def __init__(self, idx):
        self.idx = idx
        self.a = []


n, x, y = map(int, input().split())
nodes = []

for i in range(n):
    node = Node(i+1)
    nodes.append(node)

for i in range(n-1):
    cur = nodes[i]
    next = nodes[i+1]

    cur.a.append(next)
    next.a.append(cur)

X = nodes[x-1]
Y = nodes[y-1]
X.a.append(Y)
Y.a.append(X)
dp = [[None] * (n+1) for _ in range(n+1)]

for i in range(n):
    node = nodes[i]
    q = deque()
    q.append((node, 0))
    done = set()

    while q:
        t = q.popleft()
        node, d = t[0], t[1]

        if node.idx not in done:
            dp[i + 1][node.idx] = d
            done.add(node.idx)
            for adj in node.a:
                q.append((adj, d + 1))

# for i in range(1, n+1):
#     print(dp[i])

for k in range(1, n):
    temp = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            if dp[i][j] == k:
                temp += 1
    print(temp//2)

### FIXED CODE ###

from collections import deque

class Node:
    def __init__(self, idx):
        self.idx = idx
        self.a = []


n, x, y = map(int, input().split())
nodes = []

for i in range(n):
    node = Node(i+1)
    nodes.append(node)

for i in range(n-1):
    cur = nodes[i]
    next = nodes[i+1]

    cur.a.append(next)
    next.a.append(cur)

X = nodes[x-1]
Y = nodes[y-1]
X.a.append(Y)
Y.a.append(X)
dp = [[None] * (n+1) for _ in range(n+1)]

for i in range(n):
    node = nodes[i]
    q = deque()
    q.append((node, 0))
    done = set()

    while q:
        t = q.popleft()
        node, d = t[0], t[1]

        if node.idx not in done:
            dp[i + 1][node.idx] = d
            done.add(node.idx)
            for adj in node.a:
                q.append((adj, d + 1))

# for i in range(1, n+1):
#     print(dp[i])

m = {}

for i in range(1, n + 1):
    for j in range(1, n + 1):
        dis = dp[i][j]
        if dis in m:
            m[dis] += 1
        else:
            m[dis] = 1

for k in range(1, n):
    if k in m:
        print(m[k] // 2)
    else:
        print(0)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
inp = iter(map(int, read().split()))

H, W, D = next(inp), next(inp), next(inp)
addr = [None] * (H*W+1)
for i in range(H):
    for j in range(W):
        v = next(inp)
        addr[v] = (i, j)

Q = next(inp)
for _ in range(Q):
    s, t = next(inp), next(inp)
    r, c = addr[s]
    cost = 0
    while s < t:
        s += D
        nr, nc = addr[s]
        cost += abs(nr - r) + abs(nc - c)
        r, c = nr, nc
    print(cost)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
inp = iter(map(int, read().split()))

H, W, D = next(inp), next(inp), next(inp)
addr = [None] * (H*W+1)
for i in range(H):
    for j in range(W):
        v = next(inp)
        addr[v] = (i, j)

cost = []
for m in range(D):
    arr = [0]
    for x in range((H*W-m)//D):
        if m + x * D == 0:
            arr.append(0)
            continue
        r, c = addr[m + x * D]
        nr, nc = addr[m + (x+1) *D]
        arr.append(arr[-1] + abs(nr - r) + abs(nc - c))
    cost.append(arr)

Q = next(inp)
for _ in range(Q):
    s, t = next(inp), next(inp)
    m = s % D
    ans = cost[m][t//D] - cost[m][s//D]
    print(ans)
### BUGGY CODE ###

N = int(input())
data = []
for i in range(N):
    num = int(input())
    if num in data:
        data.remove(num)
    else:
        data.append(num)
print(len(data))


### FIXED CODE ###

import sys

data = set()
N = int(sys.stdin.readline())

for i in range(N):
    num = int(sys.stdin.readline())
    if num in data:
        data.remove(num)
    else:
        data.add(num)
print(len(data))
### BUGGY CODE ###

def main():
    from fractions import gcd

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

    l = 1
    for num in num_list:
        l *= num // gcd(l, num)

    answer = 0

    for num in num_list:
        answer += l // num
        answer %= 10 ** 9 + 7

    print(int(answer))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import *
n,*a=map(int,open(0).read().split())
b=1
for i in a:b*=i//gcd(b,i)
print(sum(b//i for i in a)%(10**9+7))
### BUGGY CODE ###

iH,iW,iA,iB = [int(x) for x in input().split()]
iD = 1000000007

def fFr(iX,iR=1):
    if iR == 0 or iX == 0:
        return 1
    else :
        iRet = 1
        for i in range(iR,iX+1):
            iRet *= i
        return iRet

def fnCr(iN,iR):
    if iR == 0:
        return 1
    else:
        return fFr(iN,iR+1) // fFr(iN-iR)

iRet = 0
for iL in range(0,iH-iA):
    iRet += (fnCr(iL+iB-1,iL) * fnCr(iW-iB+iH-iL-2,iW-iB-1))%iD
    iRet %= iD
iRet %= iD
print(iRet)


### FIXED CODE ###

iH,iW,iA,iB = [int(x) for x in input().split()]
iD = 10**9+7 #法

#初等整数論勉強して解説通りキッチリ実装したった

#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

#nCr = n!/r!(n-r)!
#ループ回すだけ版や
def fFr(iX,iR=1):
    if iR == 0 or iX == 0:
        return 1
    else :
        iRet = 1
        for i in range(iR,iX+1):
            iRet *= i
        return iRet

def fnCr(iN,iR):
    if iR == 0:
        return 1
    else:
        return fFr(iN,iR+1) // fFr(iN-iR)

#階乗(iDを法とした)の配列
aM = [1]*(iH+iW-1)
for i in range(1,iH+iW-1):
    aM[i]=aM[i-1]*i %iD
#各階乗のiDを法とした逆元の配列
aInvM = [1]*(iH+iW-1)
aInvM[iH+iW-2] = fBiPow(aM[iH+iW-2],iD-2,iD)
for i in range(iH+iW-2,0,-1):
    aInvM[i-1]=aInvM[i]*i % iD

iRet = 0
for iL in range(0,iH-iA):
    #iRet += (fnCr(iL+iB-1,iL) * fnCr(iW-iB+iH-iL-2,iW-iB-1))%iD
    iRet += (aM[iL+iB-1]*aInvM[iL]*aInvM[iB-1]) % iD * (aM[iW-iB+iH-iL-2]*aInvM[iW-iB-1]*aInvM[iH-iL-1])%iD
    iRet %= iD
iRet %= iD
print(iRet)
### BUGGY CODE ###

N, M = map(int, input().split())
A = sorted([int(a) for a in input().split()])
for num in range(M):
    b, c = map(int, input().split())
    b = min(b, N)
    if A[-1] < c:
        if b == N:
            A = [c] * b
        else:
            A = A[b:] + [c] * b
    elif A[0] < c:
        A += [c] * b
        A = sorted(A)[b:]
total = 0
for a in A:
    total += a
print(total)

### FIXED CODE ###

N, M = map(int, input().split())
A = sorted([int(a) for a in input().split()])[::-1]
BC = []
for num in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))
lis = sorted(BC, key = lambda x: -x[1])
total = 0
counter = 0
while counter < N:
    if not lis == []:
        if lis[0][1] > A[0]:
            (b, c) = lis.pop(0)
            b = min(b, N - counter)
            total += c * b
            counter += b
        else:
            total += A.pop(0)
            counter += 1
    else:
        total += A.pop(0)
        counter += 1
print(total)
### BUGGY CODE ###

#input
H, W = map(int, input().split())
S = [list(str(input())) for i in range(H)]

#output
import numpy as np
INF = -1
dp = np.full((H, W), INF)

dx = [1, 0, -1, 0]
dy = [0, 1, 0 ,-1]

def clear_maze(sx, sy, gx, gy, maze):
    def bfs():
        q = []
        q.insert(0, (sx, sy))
        dp[sx, sy] = 0

        while len(q):
            x, y = q.pop()

            if x == gx and y == gy:
                break

            for i in range(0, 4):
                nx, ny = x + dx[i], y + dy[i]

                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and dp[nx, ny] == INF:
                    q.insert(0, (nx, ny))
                    dp[nx, ny] = dp[x, y] + 1
        return dp[gx, gy]
    return bfs()

L = []
for h1 in range(H):
    for h2 in range(H):
        for w1 in range(W):
            for w2 in range(W):
                if S[h1][w1] != "#" and S[h2][w2] != "#":
                    dp = np.full((H, W), INF)
                    p = clear_maze(h1, w1, h2, w2, S)
                    if p != INF:
                        L.append(p)
print(int(max(L)))

### FIXED CODE ###

#input
H, W = map(int, input().split())
import numpy as np
S = [input() for _ in range(H)]

#output
import numpy as np

INF = -1
dx = [1, 0, -1, 0]
dy = [0, 1, 0 ,-1]

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            dp = np.full((H, W), INF)
            q = []
            q.insert(0, (i, j))
            dp[i, j] = 0
            while len(q):
                x, y = q.pop()

                for t in range(4):
                    nx, ny = x + dx[t], y + dy[t]

                    if (0 <= nx < H) and (0 <= ny < W) and (S[nx][ny] != "#") and (dp[nx, ny] == INF):
                        q.insert(0, (nx, ny))
                        dp[nx, ny] = dp[x, y] + 1
            for row in dp:
                answer = max(answer, max(row))
print(int(answer))
### BUGGY CODE ###

n,m = [int(i) for i in input().split()]

num_set = {i for i in range(n+1)}
for i in range(m):
    s,e = [int(i) for i in input().split()]
    card_set = {i for i in range(s,e+1)}
    num_set = num_set & card_set
    
print(len(num_set))

### FIXED CODE ###

n,m = [int(i) for i in input().split()]

l = 0
r = n
for i in range(m):
    s,e = [int(i) for i in input().split()]
    l = max(l,s)
    r = min(r,e)
    
print(max(0,r-l + 1))
### BUGGY CODE ###

n = int(input())
List = list(map(int,input().split()))
max = 0
adj = 0
rest = n
for i in range(n-1):
    counter = 0
    i = i + adj
    if i < n:
        for j in range(n-i-1):
            if List[i+j] >= List[i+j+1]:
                counter +=1
                if counter > max:
                    max = counter
                adj = j
                if rest < max:
                    break
            else:
                break
    else:
        break
        
print(max)

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
counter = 0
Ans = 0
temp = 0
for i in range(N-1):
  if H[counter]>=H[counter+1]:
    temp += 1
    if temp > Ans:
      Ans = temp
    counter += 1
  else:
    temp = 0
    counter += 1
    
print(Ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
a = list(map(int, input().split()))

d = list()
for i, v in enumerate(a):
    if i % 2 == 0:
        d.insert(0, v)
    else:
        d.append(v)
if i % 2 == 1:
    d = d[::-1]
print(*d, sep=' ')


### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))

b = np.zeros(n, dtype='int')

cnt = 0
if n % 2 == 0:
    for i in range(n // 2):
        left_idx = n // 2 - 1 - i
        right_idx = n // 2 + i
        b[left_idx] = 2 * i + 1
        b[right_idx] = 2 * i + 2
    b = b[::-1]
else:
    for i in range(n // 2):
        left_idx = n // 2 - i
        right_idx = n // 2 + 1 + i
        b[left_idx] = 2 * i + 1
        b[right_idx] = 2 * i + 2
    b[0] = n
# print('b', b)

for i in a[[b - 1]]:
    print(i)
### BUGGY CODE ###

N, X = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]

def solve(N, X, A):
    A2 = A + A
    T = [
        [min(A2[N+j+1-i-1:N+j+1]) for j in range(N)]
        for i in range(N)
    ]
    mins = [
        sum(T[i]) + i * X
        for i in range(N)
    ]
    result = min(mins)
    return result

print(solve(N, X, A))


### FIXED CODE ###

N, X = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]

def solve0(N, X, A):
    A2 = A + A
    T = [
        [min(A2[N+j+1-i-1:N+j+1]) for j in range(N)]
        for i in range(N)
    ]
    mins = [
        sum(T[i]) + i * X
        for i in range(N)
    ]
    result = min(mins)
    return result

def solve(N, X, A):
    M = A[:]
    result = sum(M)
    for i in range(1, N):
        M = [min(M[j], A[(j-i)%N]) for j in range(N)]
        r = sum(M) + X * i
        result = min(result, r)
    return result

print(solve(N, X, A))
### BUGGY CODE ###

n=int(input())
a = list(map(int,input().split()))
cnt=0
for i in range(n):
    for j in range(n-i):
        j+=i
        if sum(a[i:j+1])==0:
            cnt+=1
print(cnt)





### FIXED CODE ###

n=int(input())
a = list(map(int,input().split()))
s=[0 for _ in range(n+1)]
for i in range(n):
    s[i+1]+=s[i]+a[i]
s.sort()
c=1
cnt=0
for i in range(n):
    if s[i]==s[i+1]:
        cnt+=c
        c+=1
    else:
        c=1
print(cnt)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    q = input()
    if q == '1':
        S = S[::-1]
    else:
        F, C = q.split()[1:]
        if F == '1':
            S = C + S
        else:
            S = S + C
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
rev = False
head = []
tail = []
for i in range(Q):
    q = input()
    if q == '1':
        rev = not rev
    else:
        F, C = q.split()[1:]
        if (F == '1' and not rev) or (F == '2' and rev):
            head.append(C)
        else:
            tail.append(C)

head = ''.join(head)
tail = ''.join(tail)
S = head[::-1] + S + tail
if rev:
    S = S[::-1]
print(S)
### BUGGY CODE ###

N = int(input())
lst = [list(map(int,input().split())) for i in range(N)]
lst.reverse()
ans = 0
for A,B in lst:
    while (A+ans)%B != 0:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
lst = [list(map(int,input().split())) for i in range(N)]
lst.reverse()
ans = 0
for A,B in lst:
    if (A+ans)%B != 0:
        ans += B-(A+ans)%B
print(ans)
### BUGGY CODE ###

def rabin_karp(T, P, d):
    n = len(T)
    m = len(P)
    if n < m:
        return
    h = 1
    p = 0
    t0 = 0
    for _ in range(m - 1):
        h *= d
    for i in range(m):
        p = d * p + P[i]
        t0 = d * t0 + T[i]
    for s in range(n - m + 1):
        if p == t0:
            print(s)
        if s < n - m:
            t0 = d * (t0 - T[s] * h) + T[s + m]


d = 167
t = list(map(ord, input()))
p = list(map(ord, input()))

rabin_karp(t, p, d)


### FIXED CODE ###

def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)
### BUGGY CODE ###

from heapq import heappush, heappop
from math import ceil
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

h = []
for a in A :
  heappush(h, (-a, a, 1))
  
for _ in range(K) :
  _, x, i = heappop(h)
  heappush(h, (-(x / (i + 1)), x, i + 1))
  
print(ceil(-h[0][0]))

### FIXED CODE ###

from heapq import heappush, heappop
from math import ceil, floor
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

ng, ok = 0, 10 ** 9
for _ in range(50) :
  mid = (ng + ok) / 2
  ret = 0
  for a in A :
    ret += floor(a / mid)
  if ret <= K :
    ok = mid
  else :
    ng = mid
    
print(ceil(ng))
### BUGGY CODE ###

n = int(input())
s = list(input())
minChange = n

w = [0 for i in range(n)]
ac = 0
for i in range(n):
    if s[i] == 'W':
        ac += 1
    w[i] = ac

e = [i + 1 - w[i] for i in range(n)]

for i in range(n):
    if s[i] == 'W':
        acW = w[i] - 1
        racE = s.count('E') - e[i]
        minChange = min(minChange, acW + racE)
    else:
        acW = w[i]
        racE = s.count('E') - e[i]
        minChange = min(minChange, acW + racE)

print(minChange)

### FIXED CODE ###

N = int(input())
S = list(input())

reS = S[::-1]

wSum = [0 for i in range(N)]
eSum = [0 for i in range(N)]

for i in range(N):
    if i == 0:
        if S[i] == 'W':
            wSum[i] = 1
        if reS[i] == 'E':
            eSum[i] = 1
    else:
        if S[i] == 'W':
            wSum[i] = wSum[i-1] + 1
        else:
            wSum[i] = wSum[i-1]
        if reS[i] == 'E':
            eSum[i] = eSum[i-1] + 1
        else:
            eSum[i] = eSum[i-1]

eSum = eSum[::-1]

cost = eSum[1]

for i in range(1,N):
    if i == N - 1:
        if cost > wSum[N-2]:
            cost = wSum[N-2]
    else:
        if cost > wSum[i-1] + eSum[i+1]:
            cost = wSum[i-1] + eSum[i+1]
print(cost)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
import sys
import copy
import itertools

sys.setrecursionlimit(10**7)

def dfs(num,hiyo):
    ans[num]=min(hiyo,ans[num])
    for to,cos in way[num]:
        if ans[to]>ans[num]+cos:
            dfs(to,hiyo+cos)
    
    return 

N,M,R=map(int,input().split())

r=list(map(int,input().split()))

way=[[] for i in range(N)]

for _ in range(M):
    A,B,C=map(int,input().split())
    way[A-1].append([B-1,C])
    way[B-1].append([A-1,C])

root=[[] for i in range(N)]
for item in r:
    ans=[10**10]*N
    dfs(item-1,0)
    root[item-1].append(copy.deepcopy(ans))

#print(root)

ans=10**9
for order in itertools.permutations(r):
    temp=0
    for i in range(len(order)-1):
        #print("YES")
        #print(order[i]-1,order[i+1]-1)
        #print(root[order[i]-1][0])
        temp+=root[order[i]-1][0][order[i+1]-1]
    ans=min(ans,temp)
print(ans)


### FIXED CODE ###

# coding: utf-8
# Your code here!

#保存
import heapq
import sys
import itertools
 
sys.setrecursionlimit(10**7)

def bfs(cost,node):
    root[node]=min(root[node],cost)
    for next_c,next_n in way[node]:
        if root[next_n]==10**9:
            heapq.heappush(q,[cost+next_c,next_n])
    return
    
N,M,R=map(int,input().split())
r=list(map(int,input().split()))

way=[[] for i in range(N)]

for _ in range(M):
    A,B,C=map(int,input().split())
    way[A-1].append([C,B-1])
    way[B-1].append([C,A-1])

made=[]

#print(q)
for start in r:
    root=[10**9]*N
    q=[[0,start-1]]
    heapq.heapify(q)#costとnode
    while q:
        temp=heapq.heappop(q)
        #print(temp)
        if root[temp[1]]==10**9:
            bfs(temp[0],temp[1])
    made.append(root)
#print(made)

ans=10**9
for order in itertools.permutations([i for i in range(len(r))]):
    #print(order)
    temp=0
    for i in range(len(order)-1):
        fro=r[order[i]]
        aft=r[order[i+1]]
        #print("YES")
        #print(order[i]-1,order[i+1]-1)
        #print(root[order[i]-1][0])
        temp+=abs(made[order[i]][aft-1]-made[order[i]][fro-1])
    ans=min(ans,temp)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

T = 0
F = 1
C = 2


s = input()
q = int(input())

query = [input().split() for l in range(q)]

# print(s,q,query)


for i in range(q):
    if query[i][T] == "2":
        # print(query[i])
        if query[i][F] == "1":
            s = query[i][C]+s
            # print(s)
        else :
            s = s+query[i][C]
    else:
        s = s[::-1]


print(s)




### FIXED CODE ###

# -*- coding: utf-8 -*-

T = 0
F = 2
C = 4

s = input()
q = int(input())

cnt = 0

front = ""
back = ""

for i in range(q):
    query = input()

    if query[T] == "1":
        cnt += 1
        continue

    # モード通常
    if cnt % 2 == 0:
        if query[F] == "1":
            front +=  query[C]
        else:
            back += query[C]

    # モード反転
    else:
        if query[F] == "1":
            back += query[C]
        else:
            front +=  query[C]


# print(cnt)
# print(front)
# print(s)
# print(back)

# moji = front+s+back

if cnt % 2 == 0:
    print(front[::-1]+s+back)
    pass
else:
    print(back[::-1]+s[::-1]+front)
    # print(s[::-1])
### BUGGY CODE ###

import numpy as np
n,k = map(int,input().split())
A = list(map(int,input().split()))
imos = [0]*(n+1)
for j in range(k):
    if j==0:
        arr = A
    else:
        arr = imos
    imos = [0]*(n+1)
    for i,a in enumerate(arr):
        imos[max(i-a, 0)] += 1
        imos[min(i+a+1, n)] -= 1
    imos = list(np.cumsum(imos))[:-1]
    if set(imos)=={n}:
        break
print(*imos)

### FIXED CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
imos = [0]*(n+1)
for j in range(k):
    if j==0:
        arr = A
    else:
        arr = imos
    imos = [0]*(n+1)
    for i,a in enumerate(arr):
        imos[max(i-a, 0)] += 1
        imos[min(i+a+1, n)] -= 1
    for k in range(1, len(imos)):
        imos[k] = imos[k]+imos[k-1]
    imos = imos[:-1]
    if set(imos)=={n}:
        break
print(*imos)
### BUGGY CODE ###

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

for i in range(K):
  if A>0:
    A-=1
  elif B>0:
    B-=1

print(A,B)

### FIXED CODE ###

A,B,K=map(int, input().split())
 
if K<=A:
  A-=K
elif K<=A+B:
  B-=K-A
  A=0
else:
  A=0
  B=0

print(A,B)
### BUGGY CODE ###

import math
N = int(input())
A = [int(s) for s in input().split()]
B = [0 for i in range(N)]
idx = []
for i in range(N):
  B[A[i]-1] += 1
  if B[A[i]-1] >= 2 and not A[i]-1 in idx:
    idx.append(A[i]-1)

from operator import mul
from functools import reduce

def nC2(n):
  return n*(n-1)//2

Cs = []
C = []
Ctot = 0
for j in idx:
  if B[j]-1 >= 2:
    Cs.append(nC2(B[j]-1))
  else:
    Cs.append(0)
  tmp = nC2(B[j])
  C.append(tmp)
  Ctot += tmp
for i in range(N):
  current_idx = A[i]-1
  if current_idx in idx:
    count = Ctot + Cs[idx.index(current_idx)]-C[idx.index(current_idx)]
  else:
    count = Ctot
  print(count)

### FIXED CODE ###

N = int(input())
A = [int(s) for s in input().split()]
B = [0 for i in range(N)]
def nC2(n):
  return n*(n-1)//2
for i in range(N):
  B[A[i]-1] += 1
Ctot = 0
for i in range(N):
  Ctot += nC2(B[i])
for i in range(N):
  current_idx = A[i]-1
  if B[current_idx] == 1:
    count = Ctot
  else:
    count = Ctot + nC2(B[current_idx]-1) - nC2(B[current_idx])
  print(count)
### BUGGY CODE ###

H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

mA = max(A)

INF = 1001001001
DP = [INF for _ in range(H+1)]
DP[0] = 0
ans = INF
for h in range(H):
    for j in range(N):
        DP[min(h+A[j], H)] = min(DP[min(h+A[j], H)], DP[h] + B[j])
    if DP[H] < ans:
        ans = DP[H]

print(ans)

### FIXED CODE ###

H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

mA = max(A)

INF = 1001001001
DP = [INF for _ in range(H+1)]
DP[0] = 0
for h in range(H):
    for j in range(N):
        nh = min(h+A[j], H)
        DP[nh] = min(DP[nh], DP[h] + B[j])

print(DP[H])