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

n, p = [int(i) for i in input().split()]
num = int(p ** (1 / n)) + 1
for i in range(num):
    pp = p
    dv = num - i
    if pp % (dv**n) == 0:
        ans = dv
        break
print(ans)

### FIXED CODE ###

n, p = [int(i) for i in input().split()]
if n >= 10 ** 4:
    print(1)
    exit()

num = int(p ** (1 / n)) + 1
for i in range(num):
    pp = p
    dv = num - i
    if pp % (dv ** n) == 0:
        ans = dv
        break
print(ans)
### BUGGY CODE ###

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

for i in range(18):
    if N > 10 ** i * K:
        for j in range(999):
            if N > j*10 ** i * K:
                N=N-j*10 ** i * K


while abs(N-K)<N:
    N=abs(N-K)

print(N)

### FIXED CODE ###

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



for i in reversed(range(18)):
    while N > 10 ** i * K:
        N=N-10 ** i * K


while abs(N-K)<N:

    N=abs(N-K)

print(N)
### BUGGY CODE ###

n = int(input())
slist = tuple(input() for i in range(n))
sset = set(slist)
slist2 = list(sset)
slist2.sort()
c = 0
for i in slist2:
  if slist.count(i) > c:
    c = slist.count(i)
for i in slist2:
  if c == slist.count(i):
    print(i)

### FIXED CODE ###

n = int(input())
cnt = {}
mx = 0
for i in range(n):
  s = input()
  if s not in cnt:
    cnt[s] = 0
  cnt[s] += 1
  mx = max(mx,cnt[s])
ans = []
for s in cnt:
  if cnt[s] == mx:
    ans.append(s)
ans.sort()
for i in ans:
  print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def segfunc(x,y):
  return max(x,y)

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r): #これで[l,r)から取り出す。
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)
INF = float("inf")
H,W,M = map(int,input().split())
A = [0 for _ in range(H)]
B = [0 for _ in range(W)]
Treeh = SegmentTree(A,segfunc,-INF)
Treew = SegmentTree(B,segfunc,-INF)
G = [[False]*W for _ in range(H)]
for i in range(M):
  h,w = map(int,input().split())
  h-=1;w-=1
  G[h][w] = True
  Treeh.add(h,1)
  Treew.add(w,1)
X = Treeh.sum(0,H)
Y = Treew.sum(0,W)
MaxX_L = []
for i in range(H):
  #print(Treeh.__getitem__(i))
  if Treeh.__getitem__(i) == X:
    MaxX_L.append(i)
MaxY_L = []
for i in range(W):
  #print(Treeh.__getitem__(i))
  if Treew.__getitem__(i) == Y:
    MaxY_L.append(i)
ans = X+Y
for x in MaxX_L:
  for y in MaxY_L:
    if not G[x][y]:
      print(ans)
      exit()
ans -= 1

print(ans)

### FIXED CODE ###

H,W,M = map(int,input().split())
Bomb = []
H_num = [0 for _ in range(H)]
W_num = [0 for _ in range(W)]
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  Bomb.append([a,b])
  H_num[a] += 1
  W_num[b] += 1

HMAX = max(H_num);WMAX = max(W_num)
ans = HMAX+WMAX
HMAX_list = set([]); WMAX_list = set([])
for i in range(H):
  if H_num[i] == HMAX:
    HMAX_list.add(i)
for i in range(W):
  if W_num[i] == WMAX:
    WMAX_list.add(i)
kosu = len(HMAX_list)*len(WMAX_list)
cnt = 0
for z in Bomb:
  x = z[0];y = z[1]
  if x in HMAX_list and y in WMAX_list:
    cnt += 1
#print(kosu,cnt)
if cnt < kosu:
  print(ans)
else:
  print(ans-1)
### BUGGY CODE ###

import numpy as np

if __name__ == '__main__':
	N = int(input())
	dam = np.array(list(map(int, input().split())))

	index_ = np.array([1 if i % 2 == 0 else -1 for i in range(N)])
	ans = np.array([])
	for i in range(N):
		index_ = np.roll(index_, 1)
		ans = np.append(ans, np.dot(dam, index_))
	ans = np.roll(ans, 1)
	ans = [str(int(i)) for i in ans]

	print(' '.join(ans))

### FIXED CODE ###

import numpy as np

if __name__ == '__main__':
	N = int(input())
	dam = np.array(list(map(int, input().split())))
	
	index_ = np.array([1 if i % 2 == 0 else -1 for i in range(N)])
	ans = [int(np.dot(dam, index_))]
	for i in range(N-1):
		ans.append(2 * (dam[i] - ans[i]//2))
	ans = [str(i) for i in ans]
	print(' '.join(ans))
### BUGGY CODE ###

a, b, c, d = list(map(int, input().split()))
count = 0
for i in range(a, b + 1):
    if i % c != 0 and i % d != 0:
        count += 1

print(count)

### FIXED CODE ###

a, b, c, d = list(map(int, input().split()))
def euqlid(x,y):
    if x < y :
        temp = x
        x = y
        y = temp
    while x % y != 0:
        temp = x
        x = y
        y = temp % y
    return y
def searchCount(p,q,k):
    min = 0
    max = 0
    if p % k == 0:
        min = p // k
    else:
        min = p//k + 1
    max = q//k
    return max - min + 1
lcm = euqlid(c,d)
gcd = int((c * d) / lcm)
print((b - a + 1) - searchCount(a,b,c) - searchCount(a,b,d) + searchCount(a,b,gcd))
### BUGGY CODE ###

def solve():
  h,w = (int(i) for i in input().split())
  maze = [input() for _ in range(h)]
  count = 0
  ans = 0
  
  white = []
  for i in range(h):
    for j in range(w):
      if maze[i][j] == ".":
        white.append((i,j))

  d = [(1,0),(0,1),(-1,0),(0,-1)]
  while white:
   x,y = white.pop(0)
   query = [(x,y,0)]
   visit = [[False]*w for i in range(h)]
   while query:
    x,y,move = query.pop(0)
    nm = move + 1
    for dx,dy in d:
      
     nx,ny  =x+dx,y+dy
     if nx < 0 or nx >= h or ny < 0 or ny >=w :
        continue
     else:
      if visit[nx][ny]:
        continue
      else:
        visit[nx][ny] = True

        if maze[nx][ny] == ".":
          query.append((nx,ny,nm))
         

        else:
          ans = max(ans,nm)
          query = []
          break

  print(ans)
solve()

### FIXED CODE ###


from collections import deque
def solve():
  h,w = (int(i) for i in input().split())
  maze = ["0"*(w+2)]
  for i in range(h):
    maze.append("0"+input()+"0")
  maze.append("0"*(w+2))
  black = deque([])
  count = 0
  visit = [[False]*(w+2) for _ in range(h+2)]
  
  for i in range(h+2):
    for j in range(w+2):
      if maze[i][j] == "#":
        black.append((0,i,j)) #move,h,w

  d = [(0,1),(1,0),(-1,0),(0,-1)]
  ans = 0
  
  while count != h*w:
    move,y,x = black.popleft()
    #print(move,y,x)
    if visit[y][x]:
      continue
    else:
      visit[y][x] = True
      count += 1
      for dy,dx in d:
        ny,nx = y+dy,x+dx
        if visit[ny][nx]:
          continue
        elif maze[ny][nx] ==".":
          black.append((move+1,ny,nx))
  print(move)
          

    
solve()
### BUGGY CODE ###

n, t = map(int, input().split())
ff = [list(map(int, input().split())) for _ in range(n)]


def main(p):
    f = ff[:]
    mf = f.pop(p)
    dp = [[0 for i in range(t)] for j in range(n)]
    for i in range(n - 1):
        for j in range(t):
            if j - f[i][0] >= 0:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - f[i][0]] + f[i][1])
            else:
                dp[i + 1][j] = dp[i][j]
    return dp[n - 1][t - 1] + mf[1]


res = 0
for i in range(n):
    res = max(res, main(i))

print(res)


### FIXED CODE ###



def main():
    n, t = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(n)]
    dp1 = [[0 for i in range(t)]for j in range(n+1)]
    dp2 = [[0 for i in range(t)]for j in range(n+1)]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[i][0] >= 0:
                dp1[i+1][j] = max(dp1[i][j - f[i][0]] + f[i][1],dp1[i][j])
            else:
                dp1[i+1][j] = dp1[i][j]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[n-1-i][0] >= 0:
                dp2[i+1][j] = max(dp2[i][j - f[n-1-i][0]] + f[n-1-i][1],dp2[i][j])
            else:
                dp2[i+1][j] = dp2[i][j]

    res = 0
    for i in range(n):
        for j in range(t):
            res = max(res,dp1[i][j]+f[i][1]+dp2[n-1-i][t-1-j])

    return res




print(main())
### BUGGY CODE ###

cnt=0
S=str(input())
for i in range(5,len(S)+1):
    for j in range(0,len(S)-i+1):
        s=S[j:j+i] 
        if int(s)%2019==0:
            cnt+=1
print(cnt)


### FIXED CODE ###

S=input()
mc=[0]*2019

tg=0
digit=1
for s in S[::-1]:
    tg+=int(s)*digit
    mc[tg%2019]+=1
    digit=digit*10%2019

ans=sum(m*(m-1)//2 for m in mc)
print(ans+mc[0])
### BUGGY CODE ###

def main():
    import sys
    readline = sys.stdin.readline
    sys.setrecursionlimit(10 ** 7)

    n = int(input())
    *a, = map(int, readline().split())

    def calc(l=0, r=n - 1):
        """[l,r]"""
        if memo[l][r] != -1:
            return memo[l][r]
        if l == r:
            return a[l]

        ret = max(
            a[l] - calc(l + 1, r),
            a[r] - calc(l, r - 1)
        )

        memo[l][r] = ret
        return ret

    memo = [[-1] * n for _ in range(n)]

    ret = calc()

    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

n = int(input())
a = tuple(int(x) for x in input().split())

memo = tuple([None] * n for _ in range(n))
for i, aa in enumerate(a):
    memo[i][i] = aa

for l in range(n - 1, -1, -1):
    for r in range(l, n):
        if memo[l][r] is None:
            memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

print(memo[0][n - 1])
### BUGGY CODE ###

from collections import deque

S = deque(list(input()))
Q = int(input())
for i in range(Q):
    q = input().split()
    if q[0] == "1":
        S.reverse()
    else:
        f, c = q[1:]
        if f == "1":
            S.appendleft(c)
        else:
            S.append(c)

print("".join(S))

### FIXED CODE ###

from collections import deque

S = deque(list(input()))
Q = int(input())
r = False
left = deque()
right = deque()
for i in range(Q):
    q = input().split()
    if q[0] == "1":
        r = not r
    else:
        f, c = q[1:]
        if f == "1":
            if r:
                right.append(c)
            else:
                left.appendleft(c)
        else:
            if r:
                left.appendleft(c)
            else:
                right.append(c)

S, left, right = map(list, (S, left, right))
left.extend(S)
left.extend(right)
print("".join(left[::-1] if r else left))
### BUGGY CODE ###


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

dp = [float("inf")] * N
dp[0] = 0

for i in range(N):
    for j in range(1, K + 1):
        if i>=j:
                dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])

print(dp[-1])

### FIXED CODE ###


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

dp = [float("inf")] * N
dp[0] = 0

for i in range(N):
    for j in range(1, K + 1):
        if i>=j:
                dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])

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

import sys
from operator import itemgetter

input = sys.stdin.readline


def main():
    H, N = [int(x) for x in input().split()]
    AB = []
    for _ in range(N):
        a, b = [int(x) for x in input().split()]
        AB.append([a, b])

    dp = [0] * (H + 1)

    for i in range(1, H + 1):
        mi = float("inf")
        for a, b in AB:
            mi = min(mi, dp[max(i - a, 0)] + b)
        dp[i] = mi

    print(dp[H])



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from operator import itemgetter

input = sys.stdin.readline


def main():
    H, N = [int(x) for x in input().split()]
    AB = []
    for _ in range(N):
        a, b = [int(x) for x in input().split()]
        AB.append([a, b])

    dp = [0] * (H + 1)

    for i in range(1, H + 1):
        mi = float("inf")
        for a, b in AB:
            mi = min(mi, dp[max(i - a, 0)] + b)
        dp[i] = mi

    print(dp[H])



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

from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
dist = [[float('inf')]*w for _ in range(h)]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0))

def bfs(li):
  q = deque(li)
  visited = [[0]*w for _ in range(h)]
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      ny = y + dy 
      nx = x + dx 
      if 0<=ny<h and 0<=nx<w and a[ny][nx]=='.' and visited[ny][nx]==0 and dist[ny][nx]>dist[y][x]+1:
        dist[ny][nx] = dist[y][x] + 1
        visited[ny][nx] = 1
        q += [[ny, nx]]

li = []
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      li += [[i, j]]
      dist[i][j] = 0

bfs(li)

ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, dist[i][j])

print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
ans = 0
searched = [[0 for _ in range(w)] for _ in range(h)]
q = deque([])

def bfs():
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      next_y = y + dy
      next_x = x + dx 
      if 0 <= next_y < h and 0 <= next_x < w and searched[next_y][next_x] == 0 and a[next_y][next_x] == '.' and cnt[next_y][next_x] > cnt[y][x]+1:
        searched[next_y][next_x] = 1
        q.append([next_y, next_x])
        cnt[next_y][next_x] = cnt[y][x]+1

for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      cnt[i][j] = 0
      searched[i][j] = 1
      q.append([i, j])

bfs()
for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])

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

INF=10**30
H,N=map(int,input().split())
A,B=[],[]
for i in range(N):
    a,b=map(int,input().split())
    A.append(a);B.append(b)
dp=[INF]*(H+10)
dp[0]=0
for i in range(N):
    for j in range(H+1):
        if(j<A[i]):
            dp[j]=min(dp[j],dp[0]+B[i])
        else:
            dp[j]=min(dp[j],dp[j-A[i]]+B[i])
print(dp[H])

### FIXED CODE ###

INF=10**30
H,N=map(int,input().split())
A,B=[],[]
for i in range(N):
    a,b=map(int,input().split())
    A.append(a);B.append(b)
dp=[[INF]*(H+10) for i in range(N+1)]
dp[0][0]=0
for i in range(N):
    for j in range(H+1):
        if(j<A[i]):
            dp[i+1][j]=min(dp[i][j],dp[i][0]+B[i])
        else:
            dp[i+1][j]=min(dp[i][j],dp[i+1][j-A[i]]+B[i])
print(dp[N][H])
### BUGGY CODE ###

def main():
    # rankを出力、modを使って実装
    def matrix_rank(a, mod=2):
        n, m = len(a), len(a[0])
        M = [[j for j in i] for i in a]
        rank = min(n, m)
        i, j = 0, 0
        while i < n and j < m:
            if M[i][j] == 0:
                for k in range(i+1, n):
                    if M[k][j] != 0:
                        for l in range(j, m):
                            M[i][l] = (M[i][l]+M[k][l]) % mod
                        break
                else:
                    j += 1
                    continue
            pinv = pow(M[i][j], mod-2, mod)
            for k in range(m):
                M[i][k] = M[i][k]*pinv % mod
            M2 = M[i]
            for k in range(i+1, n):
                M3 = M[k][j]
                M[k][j] = 0
                for l in range(j+1, m):
                    M[k][l] = (M[k][l]-M3*M2[l]) % mod
            i += 1
            j += 1
        return i

    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        r = 0
        m = []
        m2 = []
        for i in range(n-1, -1, -1):
            ai = a[i]
            b = [[(ai >> j) & 1 for j in range(64)]]
            newr = matrix_rank(m+b)
            if s[i] == "0":
                if newr > r:
                    r += 1
                    m += b
                    m2 += [ai]
            else:
                if newr > r:
                    print(1)
                    break
        else:
            print(0)


main()


### FIXED CODE ###

def main():
    t = int(input())
    for _ in range(t):
        nn, aa, s, r, mm = int(input()), list(map(int, input().split())), input(), 0, []
        for ii in range(nn-1, -1, -1):
            ai = aa[ii]
            mm += [[(ai >> jj) & 1 for jj in range(64)]]
            n, i, j = r+1, 0, 0
            while i < n and j < 64:
                if mm[i][j] == 1 and mm[n-1][j] == 0:
                    i += 1
                    j += 1
                    continue
                if mm[i][j] == 0:
                    if mm[n-1][j] != 0:
                        for l in range(j, 64):
                            mm[i][l] ^= mm[n-1][l]
                    else:
                        j += 1
                        continue
                M2 = mm[i]
                for k in range(i+1, n):
                    M3 = mm[k][j]
                    mm[k][j] = 0
                    for l in range(j+1, 64):
                        mm[k][l] ^= M3*M2[l]
                i += 1
                j += 1
    
            if s[ii] == "0":
                if i > r:
                    r += 1
                else:
                    mm.pop()
            else:
                mm.pop()
                if i > r:
                    print(1)
                    break
        else:
            print(0)


main()
### BUGGY CODE ###

num = int(input())
ans = 0
for x in range(num):
    for y in range(x,num):
        val = (x+1) * (y+1)
        if val < num and x == y: ans += 1
        elif val < num and x != y: ans += 2
        else: break
print(ans)

### FIXED CODE ###

num = int(input())
ans = 0
for x in range(num):
    if num % (x + 1) == 0: ans += num // (x + 1) - 1
    else: ans += num // (x + 1)
print(ans)
### BUGGY CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    a.sort()
    yn = [0]*(10**6+1)
    for i in a:
        yn[i] += 1

    def yakusu(n):
        if n == 1:
            return []
        ys = [1]
        ni = 2
        while ni**2 <= n:
            if n%ni == 0:
                ys.append(ni)
                ys.append(n//ni)
            ni += 1
        return ys
    ans = 0
    for i in a:
        f = True
        if yn[i] != 1:
            continue
        for j in yakusu(i):
            if yn[j]:
                f = False
                break
        if f:
            ans += 1

    print(ans)

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    a.sort()
    ma = max(a)+1
    al = [True]*ma
    ans = 0
    pi = 0
    for i in a:
        if al[i]:
            ans += 1
            for j in range(i,ma,i):
                al[j] = False
            pi = i
        else:
            if i == pi:
                ans -= 1
                pi = 0

    print(ans)

    return

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

p = int(input())
a_list = list(map(int, input().split()))
r_list = [0] * p

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

fact_inv = [pow(fact[i], p-2, p) for i in range(p)]

for j in range(p):
    if a_list[j] == 0:
        continue
    for i in range(p):
        s = fact[p-1] * fact_inv[p-1-i] * fact_inv[i] * pow(-j, p-1-i, p)
        s = s % p
        r_list[i] -= s
    r_list[0] += 1


print(" ".join([str(r % p) for r in r_list]))


### FIXED CODE ###

p = int(input())
a_list = list(map(int, input().split()))
r_list = [0] * p

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

fact_inv = [0] * p
fact_inv[-1] = pow(fact[-1], p-2, p)
for i in range(p-2, -1 ,-1):
    fact_inv[i] = (fact_inv[i+1] * (i+1)) % p

ncr = [(fact[p-1] * fact_inv[p-1-i] * fact_inv[i]) % p for i in range(p)]

for j in range(p):
    if a_list[j] == 0:
        continue
    k = 1
    for i in range(p-1, -1, -1):
        r_list[i] -= ncr[i] * k
        r_list[i] %= p
        k *= -j
        k %= p
    r_list[0] += 1

r_list[0] %= p
print(*r_list)
### BUGGY CODE ###

from collections import deque
s = deque(input())
q = int(input())
for _ in range(q):
    que = input()
    if que == "1":
        s.reverse()
    else:
        f,c = que[2:].split()
        if f == "1":
            s.appendleft(c)
        else:
            s.append(c)

print("".join(s))


### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())
rev = False
for _ in range(q):
    que = input()
    if que == "1":
        rev = not rev
    else:
        f,c = que[2:].split()
        if (f == "1") ^ rev:
            s.appendleft(c)
        else:
            s.append(c)

if rev: s.reverse()

print("".join(s))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)

from heapq import *
f_inf = float('inf')

def dijkstra(start,node,edge):
    #始点sから各頂点への距離
    #node:頂点数
    #d:各頂点へのコスト(存在しないときはinf)
    d = [0] * node
    d[start] = 0
    #q:キュー(スタートからのコスト,頂点)
    #スタートをキューに入れる
    q = [(0,start)]
    while(len(q) != 0):
    #キューの先頭を取得
      ci, i = heappop(q)
    #キューの先頭から繋がっている頂点を探索
      for j in edge[i]:
        nc = ci + 1
        d[j] = nc
        heappush(q, (nc, j))
    return max(d)
#入力
N,M = (int(x) for x in input().split())
#エッジ
E = [[] for _ in [0]*N]

for i in range(M):
  a,b = (int(x) for x in input().split())
  E[a-1].append(b-1)

ans = 0
for i in range(N):
  ans = max(ans, dijkstra(i,N,E))


#出力
print(ans)


### FIXED CODE ###

import sys
from heapq import *
sys.setrecursionlimit(200000)

def rec(i):
  if dp[i] != 0:
    return dp[i]
  res = 0
  for j in E[i]:
    res = max(rec(j) + 1, res)
  dp[i] = res
  return dp[i]


#入力
N,M = (int(x) for x in input().split())
#エッジ
E = [[] for _ in [0]*N]
dp = [0]*N

for i in range(M):
  a,b = (int(x) for x in input().split())
  E[a-1].append(b-1)

ans = 0
for i in range(N):
  ans = max(ans, rec(i))

#出力
print(ans)
### BUGGY CODE ###

#152
def main():
    N = int(input())
    P = list(map(int,input().split()))
    count = 1
    for i in range(1, N):
        p = P[:i]
        if(min(p)>=P[i]):
            count+=1
    print(count)
main()

### FIXED CODE ###

#152
def main():
    N = int(input())
    P = list(map(int,input().split()))
    count = 0
    min = 10000000000
    for p in P:
        if(p<=min):
            count+=1
            min=p
    print(count)
main()
### BUGGY CODE ###

#! /usr/bin/env python3

D = 10**9+7
N = int(input())
A = list(map(int, input().split()))
M = N%2>0
b = 1
if M:
    if A.count(0) != 1 : b = 0
    for i in range(2, N, 2):
        if A.count(i) != 2 : b = 0
else:
    for i in range(1, N, 2):
        if A.count(i) != 2 : b = 0


print((2**(N//2))%D if b else 0)

### FIXED CODE ###

#! /usr/bin/env python3

D = 10**9+7
N = int(input())
A = list(map(int, input().split()))
M = N%2>0
b = 1
C = [0] * (N//2+1)
if M:
    for i in A:
        if i%2 < 1:
            C[i//2] += 1 
    b = (N//2) == sum(1 for x in C[1:] if x == 2) and C[0] == 1
    
else:
    for i in A:
        if i%2 > 0:
            C[i//2] += 1 
    b = (N//2) == sum(1 for x in C if x == 2)

print((2**(N//2))%D if b else 0)
### BUGGY CODE ###

n,k = map(int,input().split())
li = list(map(int,input().split()))
rc = [list(map(int,input().split())) for i in range(k)]

for i in rc:
    li = li + [i[1]]*i[0]

print(sum(sorted(li, reverse=True)[0:n]))

### FIXED CODE ###

n,k = map(int,input().split())
li = list(map(int,input().split()))
rc = [list(map(int,input().split())) for i in range(k)]

rc.sort(key=lambda x:x[1], reverse=True)

tmp = 0

for i in rc:
    li += [i[1]]*i[0]
    tmp += i[0]
    if tmp>n:
        break 

print(sum(sorted(li, reverse=True)[0:n]))