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

n, m = map(int, input().split())
des = []
first = []
second = []
a = 1
for i in range(0, m):
	b = (list(map(int, input().split())))
	if b[0] == 1:
		first.append(b[1])
	if b[1] == n:
		second.append(b[0])
###以上1から行ける場所をfirstに格納 終点につながるとこをsecondに格納

for i in first:
	if i in second:
		print('POSSIBLE')
		a = 0
		break

if a:
	print('IMPOSSIBLE')





### FIXED CODE ###

n, m = map(int, input().split())
des= [0]*(n+1)
a = 1
for i in range(0, m):
	b = (list(map(int, input().split())))
	if b[0] == 1:
		des[b[1]] += 1
		if des[b[1]] == 2:
			print('POSSIBLE')
			a = 0
			break
	if b[1] == n:
		des[b[0]] += 1
		if des[b[0]] == 2:
			print('POSSIBLE')
			a = 0
			break
		
if a:
	print('IMPOSSIBLE')
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, D, A = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(N)]

S.sort()
cnt = 0

for i in range(N):
    if S[i][1] <= 0:
        continue
    if S[i][1] % A == 0:
        dmg = S[i][1]
        cnt += S[i][1] // A
    else:
        dmg = A * (S[i][1]//A + 1)
        cnt += S[i][1]//A + 1
    max_X = S[i][0] + D*2
    for j in range(i+1, N):
        if S[j][0] > max_X:
            break
        S[j][1] -= dmg

print(cnt)


### FIXED CODE ###

from collections import deque
import math

import sys
input = sys.stdin.readline

N, D, A = map(int, input().split())
S = [0]*N
atack = deque()
for i in range(N):
    x, h = map(int, input().split())
    S[i] = [x, h]

S.sort()
cnt = 0
dmg = 0
for i in range(N):
    while atack:
        if atack[0][0] < S[i][0]:
            x, d = atack.popleft()
            dmg -= d
        else:
            break

    if S[i][1] <= dmg:
        continue
    bomb = math.ceil((S[i][1]-dmg)/A)
    atack.append([S[i][0]+2*D, A*bomb])
    cnt += bomb
    dmg += A*bomb

print(cnt)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**18

dp = [INF]*n
dp[0] = 0
dp[1] = abs(h[0]-h[1])

for i in range(2, n):
    for k in range(1, k+1):
        dp[i] = min(dp[i], dp[i-k]+abs(h[i]-h[i-k]))

print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**18

dp = [INF]*n
dp[0] = 0
dp[1] = abs(h[0]-h[1])

for i in range(2, n):
    for k in range(1, k+1):
        dp[i] = min(dp[i], dp[i-k]+abs(h[i]-h[i-k]))

print(dp[n-1])
### BUGGY CODE ###

import copy

H, W = map(int, input().split())
A = [list('#' * (W + 2))]
for _ in range(H):
    a = input()
    A.append(list('#' + a + '#'))
A.append(list('#' * (W + 2)))
B = copy.deepcopy(A)
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

ans = 0
count = 0
while count < H * W:
    count = 0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if A[i][j] == '#':
                count += 1
                for k in range(4):
                    B[i + dy[k]][j + dx[k]] = '#'
    ans += 1
    A = copy.deepcopy(B)

print(ans - 1)


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
A = [list('#' * (W + 2))]
q = deque()
A_append = A.append
q_append = q.append
for _ in range(H):
    a = input()
    A_append(list('#' + a + '#'))
A.append(list('#' * (W + 2)))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if A[i][j] == '#':
            q_append([i, j, 0])

ans = 0

while len(q) != 0:
    p = q.popleft()
    for k in range(4):
        y = p[0] + dy[k]
        x = p[1] + dx[k]
        c = p[2]
        ans = max(ans, c)
        if A[y][x] == '.':
            A[y][x] = '#'
            q_append([y, x, c + 1])

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

n,k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n
dp[0] = 0
dp[1] = abs(h[0]-h[1])

for i in range(2,n):
    best_jump = 10**10
    
    for j in range(1, k+1):
        if i-j < 0:
            break
        else:
            jump = dp[i-j] + abs(h[i]-h[i-j])      
            if jump < best_jump:
                best_jump = jump            
    dp[i] = best_jump
    
print(dp[-1])

### FIXED CODE ###

n,k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n
dp[0] = 0
dp[1] = abs(h[0]-h[1])

for i in range(2,n):
    best_jump = 10**10
    
    for j in range(1, k+1):
        if i-j < 0:
            break
        else:
            jump = dp[i-j] + abs(h[i]-h[i-j])      
            if jump < best_jump:
                best_jump = jump            
    dp[i] = best_jump
    
print(dp[-1])
### BUGGY CODE ###

import itertools
import heapq
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2*k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)
  
l = []
for i in comb:
  l.append(list(i))
  
A = []
one = [1]*len(l)
for j in range(k):
  for i in range(len(l)):
    one[i]*=l[i][j]
    A.append(one[i])
    
l_max = max(one)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
ans = np.zeros((N), dtype=np.int)
tmp = np.zeros((N), dtype=np.int)
for i in range(N):
    if i == 0:
        tmp = A.copy()
    else:
        tmp = np.concatenate([A[i:].copy(), A[:i].copy()])
    ans += (-1) ** i * tmp
ans = list(ans)
print(" ".join(map(str, ans)))

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
N = int(input())
A = np.array(list(map(int, input().split())))
sgn = np.tile(np.array([1, -1]), N // 2)
sgn = np.concatenate([sgn, np.array([1])])
ans = np.empty(N, dtype=np.int)
ans[0] = (A * sgn).sum()
for i in range(1, N):
    ans[i] = 2 * A[i - 1] - ans[i - 1]
print(*ans)
### BUGGY CODE ###

H, W = map(int, input().split())
A = []
black = []
for i in range(H):
    A.append(list(input()))
    for j in range(W):
        if A[i][j] == '#':
            black.append([i,j])

dist = []
for i in range(H):
    dist.append([])
    for j in range(W):
        if A[i][j] == '#':
            dist[i].append(0)
        else:
            min_dist = 10000000
            for b in black:
                cur_dist = abs(b[0] - i) + abs(b[1] - j)
                if cur_dist < min_dist:
                    min_dist = cur_dist
                if min_dist == 1:
                    break
            dist[i].append(min_dist)

print(max([max(r) for r in dist]))

### FIXED CODE ###

H, W = map(int, input().split())
INF = H * W
A = [input() for x in range(H)]
used = [[False] * W for x in range(H)]

q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append([i, j])
            used[i][j] = True

max_dist = 0
counter = 0
depth = -1
while counter != INF:
    # print(q)
    # print(counter)
    for i in range(len(q) - counter):
        item = q[counter]

        if item[0] > 0 and not used[item[0]-1][item[1]]:
            q.append([item[0] - 1, item[1]])
            used[item[0] - 1][item[1]] = True
        if item[1] > 0 and not used[item[0]][item[1] - 1]:
            q.append([item[0], item[1] - 1])
            used[item[0]][item[1] - 1] = True
        if item[0] < H - 1 and not used[item[0] + 1][item[1]]:
            q.append([item[0] + 1, item[1]])
            used[item[0] + 1][item[1]] = True
        if item[1] < W - 1 and not used[item[0]][item[1] + 1]:
            q.append([item[0], item[1] + 1])
            used[item[0]][item[1] + 1] = True
        counter += 1
    depth += 1

print(depth)
### BUGGY CODE ###

N = int(input())
n = 1

for i in range(1, N+1):
    n = n * i
res = n%(10**9 + 7)

print(res)

### FIXED CODE ###

N = int(input())
n = 1

for i in range(1, N+1):
    n = (n * i)%(10**9+7)

print(n)
### BUGGY CODE ###

tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict ={}
for i in range(H):
    tmp = input().split()
    list[i] =tmp
    for d in range(W):
        dict[list[i][d]] = str(i)+' '+str(d)

Q = int(input())
result = {}
for j in range(Q):
    tmpx = input()
    if tmpx in result:
        print(result[tmpx])
    else:
        tmp = tmpx.split()
        sum = 0
        Lj = int(tmp[0])
        Rj = int(tmp[1])
        count = int((Rj-Lj)/D)
        for k in range(count):
            posi1 = dict[str(Lj+D*k)].split()
            posi2 = dict[str(Lj+D*(k+1))].split()
            sum += abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
        print(sum)
        result[tmpx] = sum

### FIXED CODE ###

tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dictx ={}
dicty ={}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dictx[tmp[d]] = i
        dicty[tmp[d]] = d
cost ={}
def calcost(R):
    if int(R)<=D:
        cost[R] = 0
        return 0
    else:
        costs = abs(dictx[R]-dictx[str(int(R)-D)]) + abs(dicty[R]-dicty[str(int(R)-D)])
        cost[R] = costs + cost[str(int(R)-D)]
        return cost[R]

for n in range(1,H*W+1):
    calcost(str(n))
Q = int(input())
for j in range(Q):
    tmp = input().split()
    print(str(cost[tmp[1]]-cost[tmp[0]]))
### BUGGY CODE ###

n ,k = map(int, input().split())
lis = list(map(int, input().split()))

t = 1
for i in range(k):
    t *= lis[i]

for i in range(k, n):
    a = 1
    for j in range(i-k+1, i+1):
        a *= lis[j]
    
    if a > t:
        print('Yes')
    else:
        print('No')
    
    t = a
    a = 1

### FIXED CODE ###

n ,k = map(int, input().split())
lis = list(map(int, input().split()))

 
for i in range(k, n):
    l = lis[i-k]
    r = lis[i]
    if r > l:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N, K = map(int, input().split())
listp = list(map(int, input().split()))
listans1 = []
for n in range(N-K+1):
    b = sum(listp[n:n+K])
    listans1.append(b)
#print(listans1) 
print((max(listans1)+K)/2) 

### FIXED CODE ###

N, K = map(int, input().split())
listp = tuple(map(int, input().split()))
bc =sum(listp[0:K])
b = sum(listp[0:K])
for n in range(1,N-K+1):
    b = b - listp[n-1]+listp[n+K-1]
    
    if b > bc:
        bc = b
    else:
        pass    
    #print(b)    
print((bc+K)/2)
### BUGGY CODE ###

from collections import deque

n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].popleft())

count = 0
while True:
    index_lst = []
    for i in range(len(current)):
        candidate = current[i]
        if i+1 > candidate:
            continue
        if current[candidate-1] == i+1:
            index_lst += [i+1, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in index_lst:
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].popleft()
    count += 1

### FIXED CODE ###

from collections import deque
 
n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].popleft())

count = 0
players = set(range(1, n+1))
while True:
    index_lst = []
    for i in players:
        candidate = current[i-1]
        if candidate in index_lst:
            continue
        if current[candidate-1] == i:
            index_lst += [i, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in index_lst:
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].popleft()
    players = set(index_lst)
    count += 1
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
A.sort()

def checkMM(num):
    B = [~-((num<=a)<<1) for a in A]
    C = [0]
    [C.append(C[-1]+b) for b in B]
    tmp = 0
    for l in range(N):
        r_l = l+1
        r_r = N
        while r_l != r_r:
            if C[l]<=C[(r_l+r_r)//2]:
                r_r = (r_l+r_r)//2
            else:
                r_l = (r_l+r_r)//2 + 1
        tmp += N - r_r + 1
    return N * (N+1) / 4 < tmp

l = 0
r = N-1
while l != r:
    if checkMM(A[(l+r)//2]):
        l = (l+r)//2 + 1
    else:
        r = (l+r)//2
print(A[r])

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
AS = sorted(list(set(A)))

def f(x):
    B = [((x<=a)<<1)-1 for a in A]
    C = [N]
    [C.append(C[-1]+b) for b in B]

    r = 0
    Bit = [0] * (2*N+1)

    for i,c in enumerate(C):
        t=c-1
        while(t>0):
            r += Bit[t]
            t -= t&-t
        t=c-1
        while(t<=2*N+1):
            Bit[t] += 1
            t += t&-t
    return(r>=N*(N+1)//4)

l = 0
r = len(AS)-1
while l != r:
    if f(AS[(l+r+1)//2]):
        l = (l+r+1)//2
    else:
        r = (((l+r+1)//2)-1)
print(AS[r])
### BUGGY CODE ###

import numpy as np
from collections import deque
N,M = [int(i) for i in input().split()]
roads = []
for _ in range(M):
    A,B = [int(i) for i in input().split()]
    roads.append([A,B])
    roads.append([B,A])
roads = np.array(roads)
places = [0]*(N+1)
places[1] = 1
q = deque([1])
n = 1
while n < N:
    i = q.pop()
    L = roads[roads[:,0] == i][:,1]
    for j in L:
        if places[j] == 0:
            places[j] = i
            q.appendleft(j)
            n += 1
print("Yes")
for i in range(2,N+1):
    print(places[i])


### FIXED CODE ###

import numpy as np
from collections import deque
N,M = [int(i) for i in input().split()]
roads = [[] for _ in range(N+1)]
for _ in range(M):
    A,B = [int(i) for i in input().split()]
    roads[A].append(B)
    roads[B].append(A)
places = [0]*(N+1)
places[1] = 1
q = deque([1])
vis = [False]*(N+1)
vis[1] = True
while q:
    now = q.popleft()
    L = roads[now]
    for j in L:
        if vis[j]:
            continue
        vis[j] = True
        places[j] = now
        q.append(j)

print("Yes")
s = "\n".join(map(str, places[2:]))
print(s)
### BUGGY CODE ###

n = int(input())
l = [0]*n

for i in range(n):
    a = int(input())
    if a not in l:
        l[i] = a
    else:
        l.remove(a)

l = [j for j in l if j != 0]

print(len(l))

### FIXED CODE ###

n = int(input())
l = []
 
for _ in range(n):
    a = int(input())
    l.append(a)

l.sort()

ans = 0
cnt = 1
tmp = l[0]
for i in range(1,len(l)):
    if tmp == l[i]:
        cnt += 1
        tmp = l[i]
    else:
        if cnt%2 != 0:
            ans += 1
            cnt = 1
            tmp = l[i]
        else:
            cnt = 1
            tmp = l[i]
if cnt%2 != 0:
    ans += 1

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

N,M = map(int,input().split())
A = list(map(int,input().split()))
for _ in range(M):
  idx = A.index(max(A))
  A[idx] = A[idx]//2

print(sum(A))

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
A = list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(A)
for _ in range(M):
  heapq.heappush(A,((heapq.heappop(A)*-1)//2)*-1)

print(sum(A)*-1)
### BUGGY CODE ###

s = input()
t = input()

H = len(s)
W = len(t)
dp = [[0 for x in range(W+1)] for y in range(H+1)]

for y in range(H) :
    for x in range(W) :
        if s[y] == t[x] :
            dp[y+1][x+1] = dp[y][x]+1
        else :
            dp[y+1][x+1] = max(dp[y+1][x], dp[y][x+1])

ans = ""

while (H > 0) and (W > 0) :
    if dp[H][W] == dp[H-1][W] :
        H -= 1
    elif dp[H][W] == dp[H][W-1] :
        W -= 1
    else :
        H -= 1
        W -= 1
        ans = s[H] + ans

print(ans)


### FIXED CODE ###

s = input()
t = input()

H = len(s)
W = len(t)
dp = [[0 for x in range(W+1)] for y in range(H+1)]

for y in range(H) :
    for x in range(W) :
        if s[y] == t[x] :
            dp[y+1][x+1] = dp[y][x]+1
        else :
            dp[y+1][x+1] = max(dp[y+1][x], dp[y][x+1])

ans = ""

while (H > 0) and (W > 0) :
    if dp[H][W] == dp[H-1][W] :
        H -= 1
    elif dp[H][W] == dp[H][W-1] :
        W -= 1
    else :
        H -= 1
        W -= 1
        ans = s[H] + ans

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

N = int(input())
S = [input() for _ in range(N)]

T = [[""] * N for _ in range(N)]
ans = 0
for A in range(N):
    flag = True
    for i in range(N):
        for j in range(N):
            T[(i+A)%N][j] = S[i][j]
    for i in range(N):
        for j in range(N):
            flag &= T[i][j] == T[j][i]
    if flag:
        ans += N

print(ans)

### FIXED CODE ###

N = int(input())
S = [list(input()) for _ in range(N)]

def generate(A, B):
    T = [[""] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            ni = (i + A) % N
            nj = (j + B) % N
            T[ni][nj] = S[i][j]
    flag = True
    for i in range(N):
        for j in range(N):
            flag &= T[i][j] == T[j][i]
    return flag

ans = 0

for A in range(N):
    ans += N * generate(A, 0)

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

N,P = map(int,input().split())
data = [i for i in range(2,P+1)]
for d in data:
    data = [x for x in data if (x==d or x%d != 0 )]
lst = []
for i in data:
    if P%i == 0:
        a = P
        cnt = 0
        while a % i == 0:
            a /= i
            cnt += 1
        lst.append([i,cnt])    
#print(lst)    

ans=1
a=1
for i in lst:
    a = i[0]*(i[1]//N)
    if a:
        ans *= a
print(ans)    


### FIXED CODE ###

def hoge(p):
    ret = {}
    pp = 2
    while pp * pp <= p:
        while p % pp == 0:
            ret[pp] = ret[pp]+1 if pp in ret else 1
            p //= pp
        pp += 1
    if p != 1: ret[p] = 1
    return ret

N,P=map(int,input().split())
if N==1:
    print(P)
elif P==1:
    print(1)
else:
    ans = 1
    ret = hoge(P)
    for p,e in ret.items():
        ans *= max(1, p**(e//N))
    print(ans)
### BUGGY CODE ###



from collections import defaultdict
from collections import deque

N = int(input())
"""
before[(i,j)]
iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

nxt[(i,j)]
iとjの試合より後に行える対戦者の組

例２
4
2 3 4
1 3 4
4 1 2
3 1 2
について、
before[(1,3)] = 2
before[(1,4)] = 2
nxt[(1,2)] = set((1,3), (2,3))
みたいな
"""
before = defaultdict(int)
nxt = defaultdict(set)

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

for i in range(N):

    for j,a in enumerate(A[i]):
        l, h = min(i+1, a), max(i+1, a)
        if j == 0:
            b = (l,h)
        else:
            before[(l,h)] += 1
            nxt[b].add((l,h))
            b = (l,h)



match_today = deque()

for i in range(1, N):
    for j in range(i+1, N+1):
        if before[(i, j)] == 0:
            match_today.append((i,j))
            

match_tomorrow = deque()
ans = 0
cnt_match = 0 
while len(match_today) > 0:
    #print( match_today)
    ans += 1
    
    for _ in range(len(match_today)):
        l,h = match_today.popleft()
        cnt_match += 1
        for nl, nh in nxt[(l,h)]:
            before[(nl, nh)] -= 1
            
            if before[(nl, nh)] == 0:
                match_tomorrow.append((nl, nh))
    
    match_today = match_tomorrow
    match_tomorrow = deque()


if cnt_match == N*(N-1) // 2:
    print(ans)
else:
    print(-1)

### FIXED CODE ###


from collections import deque

N = int(input())
match_order = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    # aの残りの順で一番初めに戦う対戦相手を取り出す
    b = match_order[a].popleft()
    if next_opponent[b] == a:
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        # a,bについて、まだ対戦相手が残っているならキューに積む
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    # bの残りの順で戦う相手がaではないなら、順番が来るまで待つ
    else:
        next_opponent[a] = b

# 対戦相手が残っている人がいる場合、条件通りに終わることができない
if any(match_order):
    print(-1)
else:
    print(max(finish_by))
### BUGGY CODE ###

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

b = []
c = []
for i in range(q):
    x, y = map(int, input().split())
    b.append(x)
    c.append(y)

for j in range(q):
    a = [c[j] if i == b[j] else i for i in a]
    print(sum(a))


### FIXED CODE ###

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

counter = Counter(a)
sum_res = sum(a)

for i in range(q):
    b, c = map(int, input().split())
    sum_res += (c-b)*counter[b]

    counter[c] += counter[b]
    counter[b] = 0
    print(sum_res)
### BUGGY CODE ###

input_line = list(map(int,input().split()))
input_hp = list(map(int,input().split()))

if input_line[0] <= input_line[1]:
    print('0')
else:
    for i in range(input_line[1]):
        input_hp.sort(reverse=True)
        input_hp.pop(i)
    result = sum(input_hp)
    print(result)

### FIXED CODE ###

input_line = list(map(int,input().split()))
input_hp = list(map(int,input().split()))

if input_line[0] <= input_line[1]:
    print('0')
else:
    input_hp.sort()
    result_input_hp = len(input_hp) - input_line[1]
    sum_total = sum(input_hp[:result_input_hp])
    print(sum_total)