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

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



for i in range(Q):
    X,Y = map(int,input().split())

    ans = 0

    for j in range(N):
        if A[j] == X:
            ans += Y
            A[j] = Y
        else:
            ans += A[j]

    print(ans)


### FIXED CODE ###

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

cnt_dict = {}


s = sum(A)

ans = 0

for item in A:
    if item not in cnt_dict:
        cnt_dict[item] = 0
    cnt_dict[item] += 1

for _ in range(Q):
    X,Y = map(int,input().split())

    if X not in cnt_dict:
        cnt_dict[X] = 0
    if Y not in cnt_dict:
        cnt_dict[Y] = 0

    s -= cnt_dict[X] * X
    s += cnt_dict[X] * Y

    cnt_dict[Y] += cnt_dict[X]
    cnt_dict[X] = 0


    print(s)





'''
#初期案　遅すぎ

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



for i in range(Q):
    X,Y = map(int,input().split())

    ans = 0

    for j in range(N):
        if A[j] == X:
            ans += Y
            A[j] = Y
        else:
            ans += A[j]

    print(ans)

    '''
### BUGGY CODE ###

n,m=map(int,input().split())
s={k for k in range(1,100001)}
for i in range(m):
  l,r=map(int,input().split())
  b={j for j in range(l,r+1)}
  s=s&b
print(len(s))

### FIXED CODE ###

n,m = map(int,input().split())
count = 0
lmax = 0
rmin = 100000
for i in range(m):
  l,r = map(int,input().split())
  lmax = max(l,lmax)
  rmin = min(r,rmin)
print(max(rmin-lmax+1,0))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n, m = map(int, input().split())
h = np.array(input().split(), dtype='int')
good_tower = np.arange(1, n+1)
bad_tower = np.zeros((), dtype='int')

for i in range(m):
    a, b = map(int, input().split())

    if h[a-1] > h[b-1]:
        bad_tower = np.append(bad_tower, b)
    elif h[a-1] < h[b-1]:
        bad_tower = np.append(bad_tower, a)
    elif h[a-1] == h[b-1]:
        bad_tower = np.append(bad_tower, a)
        bad_tower = np.append(bad_tower, b)

bad_tower = np.array(list(set(bad_tower)))

ans = len(good_tower) - len(bad_tower) + 1

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n, m = map(int, input().split())
h = np.array(input().split(), dtype='int')
bad_tower = np.zeros((n), dtype='int')

for i in range(m):
    a, b = map(int, input().split())
    ha = h[a-1]
    hb = h[b-1]

    if ha > hb:
        bad_tower[b-1] = 1
    elif ha < hb:
        bad_tower[a-1] = 1
    elif ha == hb:
        bad_tower[a-1] = 1
        bad_tower[b-1] = 1

ans = n - np.sum(bad_tower)

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

#D
a, b, n = list(map(int, input().split()))
ans = 0
for x in range(n+1):
    new_ans = int(a*x/b) - int(x/b) * a
    ans = max(ans, new_ans)
print(ans)

### FIXED CODE ###

a, b, n = list(map(int, input().split()))
ans = min(b-1, n)
print(int(a*ans/b)-a*int(ans/b))
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
answer = 0
for i in range(N):
    key = 1
    for j in range(i):
        # key = 1
        if P[i] > P[j]:
            key *= 0
        # print(P[i],P[j], key, answer)

    if key:
        answer += 1

print(answer)

### FIXED CODE ###

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

def init_min(init_min_val):
    #set_val
    for i in range(N):
        seg_min[i+num_min-1]=init_min_val[i]    
    #built
    for i in range(num_min-2,-1,-1) :
        seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2]) 
    
def update_min(k,x):
    k += num_min-1
    seg_min[k] = x
    while k:
        k = (k-1)//2
        seg_min[k] = min(seg_min[k*2+1],seg_min[k*2+2])
    
def query_min(p,q):
    if q<=p:
        return ide_ele_min
    p += num_min-1
    q += num_min-2
    res=ide_ele_min
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg_min[p])
        if q&1 == 1:
            res = min(res,seg_min[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg_min[p])
    else:
        res = min(min(res,seg_min[p]),seg_min[q])
    return res

#####単位元######
ide_ele_min = 10**10

#num_min:n以上の最小の2のべき乗
num_min =2**(N-1).bit_length()
seg_min=[ide_ele_min]*2*num_min
init_min(P)

answer = 1

for i in range(1, N):
    MIN = query_min(0, i)
    if MIN > P[i]:
        answer += 1

print(answer)
### BUGGY CODE ###

from collections import Counter

def verify_anagrams(first_word, second_word):
    def get_counter(s):
        return Counter(s.upper().replace(' ', ''))
    return get_counter(first_word) == get_counter(second_word)
ans=[]
N=int(input())
kotae=[0]*N
for n in range(N):
    a=input()
    if n==0:
        ans.append(a)
        kotae[0]=1
    else:
        u=0
        for i in range(len(ans)):
            if verify_anagrams(a,ans[i])==True:
                kotae[i]+=1
                u=1
                break
        if u==0:
            kotae[len(ans)]=1
            ans.append(a)
c=0
for n in range(len(kotae)):
    c=c+kotae[n]*(kotae[n]-1)/2
print(round(c))


### FIXED CODE ###

import collections


N=int(input())
c=0
ans=[]
for n in range(N):
    a=input()
    a=sorted(a)
    a=''.join(a)
    ans.append(a)
c = collections.Counter(ans)
values, counts = zip(*c.most_common())
uu=0
for n in range(len(counts)):
    uu+=(counts[n]*(counts[n]-1))/2
print(round(uu))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush
import collections
import bisect

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    n = int(input())

    ans = 0
    for i in range(1,n):
        if len(make_divisors(n-i)) != 0:
            num = len(make_divisors(n-i))
            ans += num
    print(ans)



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush
import collections
import bisect

def main():
    n = int(input())
    ans = 0
    for i in range(1, n):
        ans += (n-1)//i
    print(ans)


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

# ABC174 D
import sys
sys.setrecursionlimit(3*10**5)

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

def search(s):
    if s=='':
        return 0
    if s[0]=='R':
        return search(s[1:])
    if s[-1]=='W':
        return search(s[:-1])
    return search(s[1:-1])+1
print(search(S))

### FIXED CODE ###

# ABC174 D
import sys
sys.setrecursionlimit(3*10**5)

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

def search(l,r):
    # 半開区間
    if l==r:
        return 0
    if S[l]=='R':
        return search(l+1,r)
    if S[r-1]=='W':
        return search(l,r-1)
    return search(l+1,r-1)+1
print(search(0,N))
### BUGGY CODE ###

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


def calc(x):
    return (A*x)//B - A*(x//B)

index = 1
prev = -1
max_num = 0
flag = True
if B == 1:
    flag = False
    max_num = 0



while flag and index <= min(N,B):
    tmp = calc(index)
    if tmp < prev:
        flag = False
    else:
        prev = tmp
    if max_num < tmp:
        max_num = tmp
    index += 1

print(max_num)


### FIXED CODE ###

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


def calc(x):
    return (A*x)//B - A*(x//B)

print(calc(min(B-1, N)))
### BUGGY CODE ###

#coding:utf-8

s = input()
s_arr = list(s)

n = 0
l = len(s_arr)
while True:
    counter = 0
    for i in range(l):
        if i == l-1:
            break
        if (s_arr[i] == 'B')&(s_arr[i+1] == 'W'):
            s_arr[i] = 'W'
            s_arr[i+1] = 'B'
            counter += 1
            n += 1
    if counter == 0:
        break

print(n)

### FIXED CODE ###

#coding:utf-8

s = input()
s_arr = list(s)

n = 0
l = len(s_arr)

ans = 0
b_count = 0
for i in range(l, 0, -1):
    if i == l:
        if s_arr[i-1] == 'B':
            b_count += 1
    else:
        if s_arr[i-1]=='B':
            ans += l - i - b_count
            b_count += 1


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

N = int(input())
my_list = list(map(int, input().split()))
ans = 0

for i in range(N - 1):
    for j in range(i + 1, N):
        if j - i == my_list[i] + my_list[j]:
            ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
my_list = list(map(int, input().split()))
my_dict1 = {}
my_dict2 = {}

# j - i == Aj + Ai
# j - Aj == Ai + i

#Ai + i
for i in range(N):
    key = my_list[i] + i
    if key in my_dict1.keys():
        my_dict1[key] += 1
    else:
        my_dict1[key] = 1

#j - Aj
for j in range(N):
    key = j - my_list[j]
    if key in my_dict2.keys():
        my_dict2[key] += 1
    else:
        my_dict2[key] = 1


ans = 0
for key in my_dict1.keys():
    if key in my_dict2.keys():
        ans += my_dict1[key] * my_dict2[key]

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

from bisect import bisect_left
n = int(input())
D = sorted(list(map(int, input().split())))
m = int(input())
T = list(map(int, input().split()))
for t in T:
	while t:
		i = bisect_left(D, t)
		if i == n or D[i] != t:
			print("NO")
			exit()
		else:
			t -= D[i]
			n -= 1
			D.pop(i)
else:
	print("YES")

### FIXED CODE ###

n = int(input())
D = list(map(int, input().split()))
m = int(input())
T = list(map(int, input().split()))

from collections import Counter
DC = Counter(D)
TC = Counter(T)
for k, v in TC.items():
	if v > DC[k]:
		print("NO")
		exit()
else:
	print("YES")
### BUGGY CODE ###

N = int(input())
count = 0
for i in range(N):
    count += i
print(count)

### FIXED CODE ###

N = int(input())
count = N * (N - 1) // 2
print(count)
### BUGGY CODE ###

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



#%%
# n = 6
# a = [3, 14, 159, 2, 6, 53]
# b = [58, 9, 79, 323, 84, 6]
# c = [2643, 383, 2, 79, 50, 288]

#%%
a=sorted(a)
b=sorted(b)
c=sorted(c)

#%%
ans = 0

for ci in c:
    for bi in b:
        if ci > bi:
            for ai in a:
                if bi > ai:
                    # print(ci, bi, ai)
                    ans += 1
                else:
                    break
        else:
            break

#%%
print(ans)

#%%


### FIXED CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
# import bisect

N = INT()
A = LIST()
B = LIST()
C = LIST()

A.sort()
B.sort()
C.sort()

def binsearch(lst, th, ud="up"):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if ud == "up":
            if lst[mid] > th:
                right = mid
            else:
                left = mid
        else:
            if lst[mid] >= th:
                right = mid
            else:
                left = mid
        
    return right if ud == "up" else left


ans = 0
# for ai in A:
#     i = bisect.bisect_right(B, ai)
#     for bi in B[i:]:
#         j = bisect.bisect_right(C, bi)
#         ans += len(C[j:])

for bi in B:
    i = binsearch(A, bi, "down")
    j = binsearch(C, bi, "up")
    ans += (i+1) * (N-j)


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

l = int(input())
order = list(input().split())
for i in range(l):
    order[i] = int(order[i])

a = 0
c = 0
for i in range(l):
    for j in range(i+1):
        if order[j] >= order[i]:
            c = c + 1
        if c - 1  == i:
            a = a + 1
        if j  == i:
            c  = 0
print(a)

### FIXED CODE ###

l  = int(input())
order = list(input().split())
for i in range(l):
    order[i] = int(order[i])


min  = order[0]
a = 0

for i in range(l):
    if order[i] <= min:
        a = a + 1
        min  = order[i]
print(a)
### BUGGY CODE ###

import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x


fact = [1] * 100100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return fact[n] * modinv(fact[n - r]) * modinv(fact[r]) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - n*(n+1)//2

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n+1, k) - comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)


### FIXED CODE ###

import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x


fact = [1] * 100100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return fact[n] * modinv(fact[n - r]) * modinv(fact[r]) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - n*(n+1)//2

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n+1, k) - comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)
### BUGGY CODE ###

from sys import stdin

n = int(input())
A = list(map(int, stdin.readline().split()))

d = dict()

for a in A:
    d[a] = d.get(a, 0) + 1

for _ in range(int(input())):
    b, c = map(int, input().split())
    if d.get(b, 0) != 0:
        temp = d[b]
        d[b] -= temp
        d[c] = d.get(c, 0) + temp

    print(sum(k*v for k, v in d.items()))

### FIXED CODE ###

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

    sum_a = sum(A)

    d = dict()

    for a in A:
        d[a] = d.get(a, 0) + 1

    for _ in range(int(input())):
        b, c = map(int, input().split())
        if d.get(b, 0) != 0:

            temp = d[b]         
            d[b] -= temp
            d[c] = d.get(c, 0) + temp

            sum_a += (c - b) * temp
        print(sum_a)
        
main()
### BUGGY CODE ###

X, Y ,Z ,K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

C.sort(reverse=True)

ab_scores = sorted([a + b for a in A for b in B], reverse=True)[:K]
scores = sorted([ab + c for ab in ab_scores for c in C], reverse=True)

for i in scores[:K]:
    print(i)


### FIXED CODE ###

X, Y ,Z ,K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)


scores = []
for a in range(len(A)):
    for b in range(len(B)):
        if (a + 1) * (b + 1) > K:
            break
        for c in range(len(C)):
            if (a + 1) * (b + 1) * (c + 1) > K:
                break
            score = A[a] + B[b] + C[c]
            scores.append(score)

scores.sort(reverse=True)

for i in range(K):
    print(scores[i])
### BUGGY CODE ###

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

### FIXED CODE ###

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

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

maximized = []

for k in range(K):
    B = [0] * N

    # 全玉maxになったとき
    if len(maximized) == N:
        break

    for i in range(N):
        # 強さはN超にはならない
        if A[i] == N:
            B[i] = A[i]
            maximized.append(i)
        else:
            # 照らせる範囲
            l = max(0, i - A[i])
            r = min(N - 1, i + A[i])

            for j in range(l, r + 1):
                B[j] += 1
    A = B

A = [str(a) for a in A]
print(' '.join(A))


### FIXED CODE ###

import numpy as np
from numba import njit

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A, dtype=int)


fin = [N] * N

@njit(cache=True)
def calc_b(a):
    b = np.zeros(N, dtype=np.int64)
    for i, _a in enumerate(a):
        l = max(0, i - _a)
        r = min(N - 1, i + _a)

        # imos hou
        b[l] += 1
        if r + 1 < N:
            b[r + 1] -= 1

    b = np.cumsum(b)
    # print('b_sum', b)
    return b


for k in range(min(K,100)):
    # print('a', a)
    a = calc_b(a)
    # if all(a == fin):
    #     break

a = [str(_) for _ in a]
print(' '.join(a))
# print('step=', k)
### BUGGY CODE ###

from collections import defaultdict

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

dp = defaultdict(int)
dp[0] = 0
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    for k in list(dp.keys()):
        if k + w <= W:
            dp[k + w] = max(dp[k + w], dp[k] + v)
            ans = max(ans, dp[k + w])


print(ans)


### FIXED CODE ###

from collections import defaultdict

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

dp = defaultdict(lambda: 1e9)
dp[0] = 0
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    keys = sorted(dp.keys(), reverse=True)
    for k in keys:
        dp[k + v] = min(dp[k + v], dp[k] + w)
        if dp[k + v] <= W:
            ans = max(ans, k + v)


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

N = int(input())
A = [int(T) for T in input().split()]
Remove = 0
for T in set(A):
    TCount = A.count(T)
    if TCount<T:
        Remove += TCount
    elif TCount>T:
        Remove += TCount-T
print(Remove)

### FIXED CODE ###

import collections
N = int(input())
A = collections.Counter(int(T) for T in input().split()).most_common()
Remove = 0
for T in range(0,len(A)):
    if A[T][0]>A[T][1]:
        Remove += A[T][1]
    elif A[T][0]<A[T][1]:
        Remove += A[T][1]-A[T][0]
print(Remove)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import itertools


def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table


n = int(readline())
memo = prime_decomposition(n)
ans = float('inf')
if len(memo) == 1:
    print(memo[0] - 1)
else:
    len_memo = len(memo)
    bit = list(itertools.product([0, 1], repeat=len_memo))
    for i in range(2 ** len_memo):
        x, y = 1, 1
        for j in range(len_memo):
            if bit[i][j] == 0:
                x *= memo[j]
            else:
                y *= memo[j]
        if ans > x + y - 2:
            ans = x + y - 2
    print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
ans = float('inf')
for i in range(1, int(n ** 0.5) + 1):
    x, y = divmod(n, i)
    if y == 0:
        ans = min(ans, x + i)
print(ans - 2)
### BUGGY CODE ###

# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

N = int(input())
ans = 0

for i in range(N):
  ans += i

print(ans)


### FIXED CODE ###

# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

N = int(input())
ans = (N-1)*(N)//2
print(int(ans))
### BUGGY CODE ###

n = int(input())
s_list = []
for i in range(n):
    s_list.append(input())
#print(s_list)
ans = []
for s in s_list:
    if not s in ans:
        ans.append(s)
print(len(ans))
    

### FIXED CODE ###

n = int(input())
s_list = {}
count = 0
for i in range(n):
    s = input()
    if not s in s_list:
        s_list[s]=0
        count+=1
print(count)
### BUGGY CODE ###

h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]

        for j in range(w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1          
            if any(nex[m]>k for m in range(checker+1)):
                x = -1
                break

            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        if x >= 0:
            result.append(checker+x)
print(min(result))

### FIXED CODE ###

h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        
        num = i
        p = 0
        nex = [0 for _ in range(checker+1)]
        for m in range(h):
            nex[p] += s[m][0]
            p += num%2
            num = num >> 1
        if max(nex) > k:
            x = float('inf')
            continue

        if all(nex[m]+c[m] <= k for m in range(checker+1)):
            c = [c[I]+nex[I] for I in range(checker+1)]
        else:
            x += 1

        for j in range(1, w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1
            if max(nex) > k:
                x = float('inf')
                break            
            
            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))
### BUGGY CODE ###

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

pin = []
for i in range(1000):
    i = str(i)
    if len(i) == 1:
        i = '00' + i
    elif len(i) == 2:
        i = '0' + i
    pin.append(i)

ans = 0
for i in pin:
    c = 0
    for j in s:
        if j == i[c]:
            c += 1
        if c == 3:
            ans += 1
            break
print(ans)

### FIXED CODE ###

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

pin = []
for i in range(1000):
    i = str(i)
    if len(i) == 1:
        i = '00' + i
    elif len(i) == 2:
        i = '0' + i
    pin.append(i)

ans = 0
for i in pin:
    c = 0
    for j in s:
        if j == i[c]:
            c += 1
        if c == 3:
            ans += 1
            break
print(ans)
### BUGGY CODE ###

h, n = map(int, input().split())
dp = [[0] * (h+1) for i in range(n)]
a, b = map(int, input().split())
for c in range(1, h+1):
  dp[0][c] = b * ((c-1) // a + 1)
for i in range(1, n):
  a, b = map(int, input().split())
  for c in range(1, h+1):
    opt1 = dp[i-1][c]
    opt2 = dp[i-1][max(0, c-a)] + b
    opt3 = dp[i][max(0, c-a)] + b
    dp[i][c] = min(opt1, opt2, opt3)
print(dp[-1][-1])

### FIXED CODE ###

h, n = map(int, input().split())
dp = [[0] * (h+1) for i in range(n)]
a, b = map(int, input().split())
for c in range(1, h+1):
  dp[0][c] = b * ((c-1) // a + 1)
for i in range(1, n):
  a, b = map(int, input().split())
  for c in range(1, h+1):
    opt1 = dp[i-1][c]
    opt2 = dp[i-1][max(0, c-a)] + b
    opt3 = dp[i][max(0, c-a)] + b
    dp[i][c] = min(opt1, opt2, opt3)
print(dp[-1][-1])