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

import itertools
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

_w = list(range(H+W-2))

changes = []
for path in itertools.combinations(_w,W-1):
    state = [0, 0]
    pathway = [0] * (H+W-2)
    path = list(path)
    change = 0
    for i in path:
        pathway[i] = 1
    # init Flag
    black_flag = True if S[0][0] == '#' else False
    
    for go in pathway:
        state[go] += 1
        if S[state[0]][state[1]] == '#':
            if state == [H-1, W-1]:
                change += 1
                break
            if black_flag:
                continue
            else:
                black_flag = True
        else:
            if black_flag:
                change += 1
            else:
                continue
    changes.append(change)
print(min(changes))
#print(changes)

### FIXED CODE ###

# coding: utf-8
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

grid = [[0 for _ in range(W)] for _ in range(H)]

for h in range(1,H):
  if S[h-1][0] == '#' and S[h][0] == '.':
    grid[h][0] = grid[h-1][0] + 1
  else:
    grid[h][0] = grid[h-1][0]
    
for w in range(1,W):
  if S[0][w-1] == '#' and S[0][w] == '.':
    grid[0][w] = grid[0][w-1] + 1
  else:
    grid[0][w] = grid[0][w-1]
for w in range(1,W):
  for h in range(1,H):
    if S[h-1][w] == '#' and S[h][w] == '.':
      next_h = grid[h-1][w] + 1
    else:
      next_h = grid[h-1][w]      
    if S[h][w-1] == '#' and S[h][w] == '.':
      next_w = grid[h][w-1] + 1
    else:
      next_w = grid[h][w-1]
    grid[h][w] = min([next_w, next_h])
if S[H-1][W-1] == '#':
  grid[H-1][W-1] += 1
print(grid[H-1][W-1])
### BUGGY CODE ###

h, n = map(int, input().split())
dp = [float('inf')]*(2*(10**4)+1)
dp[0] = 0
l = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
  for j in range(h):
    dp[j+l[i][0]] = min(dp[j+l[i][0]], dp[j]+l[i][1])
    
print(min(dp[h:]))

### FIXED CODE ###

h, n = map(int, input().split())
dp = [float('inf')]*(2*(10**4)+1)
dp[0] = 0
l = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
  for j in range(h):
    dp[j+l[i][0]] = min(dp[j+l[i][0]], dp[j]+l[i][1])
    
print(min(dp[h:]))
### BUGGY CODE ###

n,x=int(input()),input()
o=x.count("1")
l=[0]*(o+1)
a=int(x,2)

for i in range(1,o+1):
    ret=0
    t=i
    while t:
        t%=bin(t).count("1")
        ret+=1
    l[i]=ret

c=pow(2,n-1)
for b in x:
    if b=="1":
        k=a-c
        gg=o-1
    else:
        k=a+c
        gg=o+1
    if k:
        k%=gg
        print(1+l[k])
    else:print(0)
    c//=2

### FIXED CODE ###

n,x=int(input()),input()
o=x.count("1")
if o==1:
    for i,v in enumerate(x):
        if v=="1":print(0)
        else:
            if i!=n-1:
                if x[-1]=="0":print(1)
                else:print(2)
            else:print(2)

else:
    m=o-1
    M=o+1
    mp,mm={0:1},{0:1}
    for i in range(1,n):
        mp[i]=mp[i-1]*2%M
        mm[i]=mm[i-1]*2%m
    A=int(x,2)
    a=A%m
    b=A%M
    rest={0:0}
    for i in range(1,o+1):
        rest[i]=1+rest[i%bin(i).count("1")]
    for i,v in enumerate(x):
        if v=="1":
            print(1+rest[(a-mm[n-i-1])%m])
        else:
            print(1+rest[(b+mp[n-i-1])%M])
### BUGGY CODE ###

def examC():
    N = I()
    print(0)
    q = SI()
    if q!="Vacant":
        left = 0; right = N-1
        for _ in range(20):
            cur = (left+right)//2
            print(cur)
            next = SI()
            if next!="Vacant":
                if (cur%2==1 and next==q) or (cur%2==0 and next!=q):
                    right = cur
                else:
                    left = cur+1
            else:
                break

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()


### FIXED CODE ###

def examC():
    N = I()
    print(0)
    q = input()
    if q=="Vacant":
        exit()
    left = 0; right = N - 1
    for _ in range(20):
        cur = (left + right) // 2
        print(cur)
        next = input()
        if next=="Vacant":
            exit()

        if (cur % 2 == 1 and next == q) or (cur % 2 == 0 and next != q):
            right = cur
        else:
            left = cur + 1

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

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

s = list(input())
t = list(input())

res = 0

N = 100000
for i in range(N):
    _s = s
    while len(_s) > 0 and len(t) > 0:
        if t[0] in _s:
            _index = _s.index(t[0])
            res += _index + 1
            _s = _s[_index + 1:]
            t = t[1:]
        else:
            res += len(_s)
            break
    if len(t) == 0:
        print(res)
        exit(0)

print(-1)






### FIXED CODE ###

import bisect

s = list(input())
t = list(input())

# 辞書を作る
dictionary = {}

tt = t[:]
ss = dict(zip(list(range(len(s * 2))), s * 2))

for i in range(len(ss)):
    c = ss[i]
    if c not in dictionary:
        dictionary[c] = []
    dictionary[c].append(i)

result = 0
current_idx = 0
sLen = len(s)

for c in t:
    if c not in dictionary:
        print(-1)
        exit(0)
    indexes = dictionary[c]
    next = dictionary[c][bisect.bisect_left(indexes, current_idx)] + 1
    result += next - current_idx
    current_idx = next
    if next >= sLen:
        current_idx -= sLen

print(result)
### BUGGY CODE ###

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

inf = 10**23

d = [inf] * (H+1)
d[0] = 0
for i in range(1, H+1):
    for abi in range(N):
        if A[abi] >= i:
            d[i] = min(d[i], B[abi])
        else:
            d[i] = min(d[i], d[i-A[abi]] + B[abi])


print(d[H])




### FIXED CODE ###



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

inf = 10**23

d = [inf] * (H+1)
d[0] = 0
for i in range(1, H+1):
    for abi in range(N):
        if A[abi] >= i:
            d[i] = min(d[i], B[abi])
        else:
            d[i] = min(d[i], d[i-A[abi]] + B[abi])


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

import sys
read = sys.stdin.read
from fractions import gcd
from functools import reduce
 
n,*alst = list(map(int, read().split()))

def lcm(x, y):
    g = gcd(x, y)
    g = x * y // g
    return g

g = reduce(lcm, alst)
mod=10**9+7
res=0
for a in alst:
  res+=pow(a,mod-2,mod)*g
  res%=mod
print(res)

### FIXED CODE ###

# https://atcoder.jp/contests/abc152/submissions/9693323

import sys
read = sys.stdin.read

N, *A = map(int, read().split())
mod = 10 ** 9 + 7


def min_factor(n):
    sieve = list(range(n + 1))
    sieve[2::2] = [2] * (n // 2)
    for i in range(3, int(n ** 0.5) + 2, 2):
        if sieve[i] == i:
            sieve[i * i::2 * i] = [i] * ((n - i * i) // (2 * i) + 1)
    return sieve


def prime_factorize(n):
    a = {}
    while n != 1:
        b = table[n]
        if b in a:
            a[b] += 1
        else:
            a[b] = 1
        n //= b
    return a


table = min_factor(10**6)

dic = {}
for i in A:
    for key, value in prime_factorize(i).items():
        if key in dic:
            dic[key] = max(dic[key], value)
        else:
            dic[key] = value

lcm = 1
for i, j in dic.items():
    lcm *= pow(i, j, mod)
    lcm %= mod

answer = sum(lcm * pow(i, mod - 2, mod) for i in A) % mod
print(answer)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [0] * (K + 1)
dp[0] = 1

for i, a in enumerate(A, start=1):
    accDp = [0] * (K + 2)
    for k in range(1, K + 2):
        accDp[k] = accDp[k - 1] + dp[k - 1]

    for k in range(K + 1):
        dp[k] = (dp[k] + accDp[k] - accDp[max(0, k - a)]) % MOD

print(dp[K] % MOD)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0] * (K + 1) for _ in range(N + 1)]  # dp[child][candy] 残りcandy個の場合の数
dp[0][K] = 1

for child in range(1, N + 1):
    sumDp = [0] * (K + 2)
    for i in range(1, K + 2)[:: -1]:
        sumDp[i - 1] += sumDp[i] + dp[child - 1][i - 1]

    for candy in range(K + 1):
        dp[child][candy] = (sumDp[candy] - sumDp[min(K, candy + A[child - 1]) + 1]) % MOD

print(dp[N][0] % MOD)
### BUGGY CODE ###

import heapq, copy
h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1
vec5 = []
vec = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(-2, 3):
    for j in range(-2, 3):
        if abs(i) + abs(j) < 2:
            continue
        vec5 += [(i,j)]

lands = copy.deepcopy(s)
l = 0
def find_dot():
    for i in range(h):
        for j in range(w):
            if lands[i][j] == '.':
                return True, (i,j)
    return False, (0,0)

while True:
    b, (i,j) = find_dot()
    q = [(i,j)]
    if not b:
        break
    while len(q) > 0:
        i,j = q.pop()
        lands[i][j] = l
        for v in vec:
            ii = i + v[0]
            jj = j + v[1]
            if 0 <= ii < h and 0 <= jj < w and lands[ii][jj] == '.':
                q += [(ii, jj)]
    l += 1
q = [(0, (ch, cw))]
heapq.heapify(q)
while len(q) > 0:
    c, (i,j) = heapq.heappop(q)
    if s[i][j] != '.' and s[i][j] <= c:
        continue
    s[i][j] = c
    for v in vec:
        ii = i + v[0]
        jj = j + v[1]
        if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
            heapq.heappush(q, (c, (ii, jj)))
    for v in vec5:
        ii = i+v[0]
        jj = j+v[1]
        if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.' and lands[ii][jj] != lands[i][j]:
            heapq.heappush(q, (c+1, (ii, jj)))
if s[dh][dw] == '.':
    print(-1)
else:
    print(s[dh][dw])

### FIXED CODE ###

h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1
vec5 = []
vec = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(-2, 3):
    for j in range(-2, 3):
        if abs(i) + abs(j) < 2:
            continue
        vec5 += [(i,j)]

c = 0
q = [(ch, cw)]
while len(q) > 0:
    nq = []
    while len(q) > 0:
        i, j = q.pop()
        s[i][j] = c
        nq += [(i,j)]
        for v in vec:
            ii = i + v[0]
            jj = j + v[1]
            if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
                q += [(ii, jj)]


    while len(nq) > 0:
        i, j = nq.pop()
        for v in vec5:
            ii = i+v[0]
            jj = j+v[1]
            if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
                q += [(ii, jj)]
    c += 1
if s[dh][dw] == '.':
    print(-1)
else:
    print(s[dh][dw])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
count = 0
visited = []
ans = -1

btn = 0
for _ in range(n):
  if btn in visited:
    break
  visited.append(btn)
  btn = a[btn]-1
  count += 1
  if btn==1:
    ans = count
    break
    
print(ans)
  

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

ans = -1
count = 0
btn = 0
for i in range(n):
  btn = a[btn]-1
  count += 1
  if btn == 1:
    ans = count
    break

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

if __name__ == "__main__":
  h,w = list(map(int,input().split()))
  a = [["*"*w] for i in range(h)]
  reached = [[-1 for i in range(w)] for j in range(h)]
  for i in range(h): a[i] = input()
  
  queue = []
  for i in range(h):
    for j in range(w):
      if a[i][j] == "#":
        queue.append([i,j])
        reached[i][j] = 0
  
  res = 0
  while len(queue) > 0:
    for i in range(len(queue)):
      k = queue[0][0]
      l = queue[0][1]
      if 0 <= k+1 < h and 0 <= l < w and reached[k+1][l] == -1:
          queue.append([k+1, l])
      if 0 <= k < h and 0 <= l+1 < w and reached[k][l+1] == -1:
          queue.append([k, l+1])
      if 0 <= k-1 < h and 0 <= l < w and reached[k-1][l] == -1:
          queue.append([k-1, l])
      if 0 <= k < h and 0 <= l-1 < w and reached[k][l-1] == -1:
          queue.append([k, l-1])
      reached[k][l] = res
      queue.pop(0)
    
    res += 1
  
  print(res-1)

### FIXED CODE ###

def main():
  h,w = map(int,input().split())

  q = []
  reached = [[True]*(w+2)]
  for i in range(1, h+1):
    reached.append([True] + [s == '#' for s in list(input())] + [True])
    for j in range(1,w+1):
      if reached[i][j]: q.append((i,j))
  reached.append([True]*(w+2))

  res = 0
  for i in range(100000000):
    qq = []
    for k,l in q:
      if not reached[k+1][l]:
        qq.append((k+1, l))
        reached[k+1][l] = True
      if not reached[k][l+1]:
        qq.append((k, l+1))
        reached[k][l+1] = True
      if not reached[k-1][l]:
        qq.append((k-1, l))
        reached[k-1][l] = True
      if not reached[k][l-1]:
        qq.append((k, l-1))
        reached[k][l-1] = True
    if len(qq) == 0:
      break
    else:
      pass

    q = qq
    res += 1

  print(res)
  return 0

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

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
ans = sum(a[min(n, m):])
a = a[:min(n, m)]

if len(a) == 1 and n == 1:
    print(a[0]//2**m)
elif len(a) == 1:
    print(a[0]//2**m+ans)
else:
    for i in range(m):
        a[0] //= 2
        a = sorted(a, reverse=True)
    print(ans+sum(a))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [x*(-1) for x in a]
heapq.heapify(a)

for i in range(m):
    c = (heapq.heappop(a)*(-1)//2)*(-1)
    heapq.heappush(a, c)
print(-sum(a))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
scale = 62
#scale = 5
z0 = [0 for _ in range(scale)]
for x in a:
  for d in range(scale):
    if x % 2 == 1:
      z0[d] += 1
    x //= 2
ans = 0
for d in range(scale):
  ans += z0[d] * (n-z0[d]) * 2**d
mod = 10**9+7
ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
  tmp = bin(a[i])[2:]
  tmp = '0' * (64-len(tmp)) + tmp
  b.append(tmp)
ans = 0
bit = 1
mod = 10 ** 9 + 7
for k in range(64):
  z1 = 0
  for i in range(n):
    if b[i][-k-1] == '1':
      z1 += 1
  add = z1 * (n-z1) * bit
  add %= mod
  ans += add
  ans %= mod
  bit *= 2
  bit %= mod
  #print(z1,add,ans)
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
l, r = map(int, input().split())
s1 = {int(x) for x in range(l, r+1)}
for i in range(m-1):
    l, r = map(int, input().split())
    s2 = {int(x) for x in range(l, r+1)}
    s1 = s1 & s2
    
print(len(s1))

### FIXED CODE ###

n, m = [int(x) for x in input().split()]
l = [0] * m
r = [0] * m
for i in range(m):
    l[i], r[i] = map(int, input().split())

L = max(l)
R = min(r)

if L <= R:
    print(R - L + 1)
else:
    print(0)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
 a.append(int(input()))
count = 0
for i in range(n):
 while (a[i] >= 2):
  a[i] -= 2
  count += 1
 if (i != n-1):
  while (a[i] >= 1 & a[i+1] >= 1):
   a[i] -= 1
   a[i+1] -= 1
   count += 1
print (count)

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
 a.append(int(input()))
count = 0
for i in range(n):
 if (a[i] >= 2):
  count += int(a[i] / 2)
  a[i] = a[i] % 2
 if (i != n-1):
  if (a[i] >= a[i+1]):
   count += a[i+1]
   a[i] -= a[i+1]
   a[i+1] = 0
  else:
   count += a[i]
   a[i+1] -= a[i]
   a[i] = 0
print (count)
### BUGGY CODE ###

import heapq 
N=int(input())
A=list(map(int, input().split()))
ans=-float("inf")
for k in range(N, 2*N+1):
	left=A[:k]
	right=[-i for i in A[k:]] #各要素を-1倍する

	heapq.heapify(left)
	heapq.heapify(right)

	for _ in range(k-N):
		heapq.heappop(left)
	for _ in range(2*N-k):
		heapq.heappop(right)

	ans= max(sum(left)+sum(right), ans)
print(ans)

### FIXED CODE ###

#########################ABC解説実装#########################
import heapq
N=int(input())
A=list(map(int, input().split()))

left, right = A[:N], [-1 * i for i in A[2*N:]]
sum_left, sum_right = sum(left), sum(right)

results = [0] * (N+1)
results[0] = sum_left
results[N] = sum_right

heapq.heapify(left)
heapq.heapify(right)

for i in range(N, 2*N):
    v = A[i]
    p = heapq.heappushpop(left, v)
    sum_left += v - p
    results[i-N+1] += sum_left
    
for i in range(2*N-1, N-1, -1):
    v = -1 * A[i]
    p = heapq.heappushpop(right, v)
    sum_right += v - p
    results[i-N] += sum_right
print(max(results))
### BUGGY CODE ###

#feel like this is to easy

def read_input():
  n = int(input())
  a = []
  for i in range(n):
    a.append(int(input()))
  return n,a

def TLE():
  n,a = read_input()
  sheet = []
  for item in a:
    if item not in sheet:
      sheet.append(item)
    else:
      sheet.pop(sheet.index(item))
  print(len(sheet))
  
def main():
  n,a = read_input()
  items = list(set(a))
  count = 0
  for item in items:
    if a.count(item)%2 != 0:
      count += 1
  print(count)

if __name__ == '__main__':
  main()

### FIXED CODE ###

#feel like this is to easy

def read_input():
  n = int(input())
  a = []
  for i in range(n):
    a.append(int(input()))
  return n,a

def TLE():
  n,a = read_input()
  sheet = []
  for item in a:
    if item not in sheet:
      sheet.append(item)
    else:
      sheet.pop(sheet.index(item))
  print(len(sheet))
  
def TLE2():
  n,a = read_input()
  items = list(set(a))
  count = 0
  for item in items:
    if a.count(item)%2 != 0:
      count += 1
  print(count)

def main():
  n,a = read_input()
  a.sort()
  items = list(set(a)).sort()
  t = 1
  count = 0
  for i in range(len(a)):
    if i+1 == len(a):
      count += t%2
      break
    if a[i] == a[i+1]:
      t += 1
    else:
      count += t%2
      t = 1
  print(count)

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

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
ii0 = lambda: ii() - 1
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    N,M,L = mis()
    d = [[INF]*N for _ in range(N)]
    for i in range(N):
        d[i][i] = 0
    #
    for _ in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        if c <= L:
            d[a][b] = c
            d[b][a] = c
    #
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][k]+d[k][j], d[i][j])    
    #
    d2 = [[INF]*N for _ in range(N)]
    for i in range(N):
        d2[i][i] = 0
    for i in range(N):
        for j in range(N):
            if d[i][j] <= L:
                d2[i][j] = 1
    #
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d2[i][j] = min(d2[i][k]+d2[k][j], d2[i][j])    
    #
    Q = ii()
    for _ in range(Q):
        s,t = mis()
        s -= 1
        t -= 1
        dist = d2[s][t]
        if dist == INF:
            print(-1)
        else:
            print(dist-1)




main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
ii0 = lambda: ii() - 1
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    N,M,L = mis()
    from scipy.sparse.csgraph import floyd_warshall
    import numpy as np
    INF = np.iinfo(np.int64).max
    d = np.full((N,N), INF, dtype=np.uint64)
    for i in range(N):
        d[i,i] = 0
    #
    for _ in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        if c <= L:
            d[a,b] = c
            d[b,a] = c
    #
    '''
    for k in range(N):
        for i in range(N):
            np.minimum(d[i,:], d[i,k]+d[k,:], out=d[i,:])    
    '''
    d = floyd_warshall(d)
    #
    d2 = np.full((N,N), INF, dtype=np.uint64)
    for i in range(N):
        d2[i, i] = 0
    for i in range(N):
        for j in range(N):
            if d[i, j] <= L:
                d2[i, j] = 1
    #
    '''
    for k in range(N):
        for i in range(N):
            np.minimum(d2[i,:], d2[i,k]+d2[k,:], out=d2[i,:])    
    '''
    d2 = floyd_warshall(d2)
    #
    Q = ii()
    for _ in range(Q):
        s,t = mis()
        s -= 1
        t -= 1
        dist = d2[s,t]
        if dist == INF:
            print(-1)
        else:
            print(int(dist)-1)




main()
### BUGGY CODE ###

from heapq import heapify, heappush, heappop
def main():
    N, M = map(int, input().split())
    lst = list(map(int, input().split()))
    lst = [-l for l in lst]
    heapify(lst)
    
    for _ in range(M):
        b, c = map(int, input().split())
        for _ in range(b):
            heappush(lst, -c)
    
    ans = 0
    for _ in range(N):
        ans += heappop(lst)
    print(-ans)
main()

### FIXED CODE ###

from heapq import heapify, heappush, heappop
def main():
    N, M = map(int, input().split())
    lst = list(map(int, input().split()))
    lst = [(-l, 1) for l in lst]
    heapify(lst)
    
    for _ in range(M):
        b, c = map(int, input().split())
        heappush(lst, (-c, b))
    
    ans = 0
    cnt = 0
    while True:
        tmp = heappop(lst)
        flag = False
        for _ in range(tmp[1]):
            ans -= tmp[0]
            cnt += 1
            if cnt==N:
                flag = True
                break
        
        if flag:
            break
    
    print(ans)
main()
### BUGGY CODE ###

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

ans=0
for i in range(1,M//N+1):
    if M%i==0:
        ans=max(ans,i)
        
print(ans)

### FIXED CODE ###

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

ans=0
table=make_divisors(M)
table.sort()

for i in table:
    if i<=M//N:
        ans=i
        
print(ans)
### BUGGY CODE ###

In = input().split(" ")
T = int(In[0])
A = int(In[1])
K = int(In[2])
 
if K>=T+A:
  print("0 0")
  
elif (K > T):
  print("0 {0}".format(A-(K-T)))
elif (T > K):
  print("{0} {1}".format(T-K, A))
else:
  for i in range(K):
    if T >= 1:
      T -= 1
    else:
    	if A >= 1:
      		A -= 1
    	else:
      		break
  print("{0} {1}".format(T, A))

### FIXED CODE ###

In = input().split(" ")
T = int(In[0])
A = int(In[1])
K = int(In[2])
 
if K <= T:
  print("{0} {1}".format(T-K,A))
elif K <= T+A:
  print("0 {0}".format(A-(K-T)))
else:
  print("0 0")