Harryxun/stf_run huggingface dataset:
from collections import defaultdict 

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

if M == 0:
  print(-1)
  exit()

INF = 10**20
pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
G = defaultdict(dict)
lines = [set() for _ in range(N)]
for p,q,c in pqc:
  G[(p,c)][(q,c)] = G[(q,c)][(p,c)] = 0
  lines[p].add(c)
  lines[q].add(c)
  
for v in range(N):
  if len(lines[v])>1:
    tmp = list(lines[v])
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        G[(v,tmp[i])][(v,tmp[j])] = G[(v,tmp[j])][(v,tmp[i])] = 1
        
def dijkstra(start = 0):
    from heapq import heappop, heappush
    d = defaultdict(lambda:INF)
    d[start] = 0
    que = []
    heappush(que, (0, start))
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]: continue
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
    return d
  
ans = INF
for c in lines[0]:
  d = dijkstra((0,c))
  ans = min(ans, min(d[(N-1,c2)] for c2 in lines[N-1]))
  
print(ans+1 if ans < INF else -1)

### FIXED CODE ###

def main():
  N,M=map(int,input().split())

  if M == 0:
    print(-1)
    exit()

  INF = 10**6
  pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

  to1d={v:{} for v in range(N)}
  count=2
  for p,q,c in pqc:
    if not to1d[p].get(c):
      to1d[p][c] = count
      count += 1
    if not to1d[q].get(c):
      to1d[q][c] = count
      count += 1

  G = [{} for _ in range(N+count)]
  for p,q,c in pqc:
    v1,v2 = to1d[p][c],to1d[q][c]
    G[v1][v2] = G[v2][v1] = 0

  for i in range(N):
    if len(to1d[i])<=1: continue
    for c in to1d[i].keys():
      v = to1d[i][c]
      G[v][count] = 1
      G[count][v] = 0
    count += 1

  def dijkstra(start = 0, goal = 1):
      from heapq import heappop, heappush
      NN = len(G)
      d = [INF]*NN
      d[start] = 0
      que = []
      heappush(que, start)
      while que:
          p = divmod(heappop(que),NN)
          v = p[1]
          if d[v] < p[0]: continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, d[u]*NN+u)
          if v == goal: return d[goal]
      return d[goal]

  for c in to1d[0].keys():
    v = to1d[0][c]
    G[0][v] = 1
  for c in to1d[N-1].keys():
    v = to1d[N-1][c]
    G[v][1] = 0

  ans = dijkstra(0,1)
  print(ans if ans < INF else -1)
  
if __name__=="__main__":
  main()
h,w=map(int,input().split())
for i in range(w):
  a=input()
  print(a)
  print(a)

### FIXED CODE ###

h,w=map(int,input().split())
for i in range(h):
  a=input()
  print(a)
  print(a)
a,b=map(int,raw_input().split())

if a >= b:
  print 'a b'
else
  print 'b a'

### FIXED CODE ###

while 1:
  x, y = map(int, raw_input().split())
  if x == 0 and y ==0:
    break
  elif x > y:
    print "%d %d" % (y,x)
  else:
    print "%d %d" % (x,y)
s, t map(str, input().split())
ans = t + s
print(ans)

### FIXED CODE ###

s, t = map(str, input().split())
ans = t + s
print(ans)
N, M = map(int, input())

print(N*M)

### FIXED CODE ###

N, M = map(int,input().split())
print(N*M)
def gcd(a,b):
    if a<b:
     d=a
     a=b
     b=d

    if b==0:
     b=1
    if a==0:
     a=1

    c=a%b

    if c==0:
     return b
    else:
     return gcd(b,c)

def lcm(a,b):
    c=gcd(a,b)
    return a/c*b



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

for lop2 in range(n):
    t[lop2]=int(input())

ans=t[0]

for lop in range(1,n):
    ans=lcm(ans,t[lop])
print(int(ans))


### FIXED CODE ###

'''
def gcd(a,b):
    if a<b:
     c=a
     a=b
     b=c

    c=a%b

    if c==0:
     return b
    else:
     return gcd(b,c)
'''

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

def lcm(e,f):
    c=gcd(e,f)
    g=e*f
    return g//c



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

for lop2 in range(n):
    t[lop2]=int(input())

ans=t[0]

for lop in range(1,n):
    ans=lcm(ans,t[lop])
print(int(ans))
alpha = list("abcdefghijklmnopqrstuvwxyz")
s = input()

found = False
for chr in s:
    del alpha[alpha.index(chr)]

if len(alpha) == 0:
    print("None")
else:
    print(alpha[0])


### FIXED CODE ###

alpha = list("abcdefghijklmnopqrstuvwxyz")
s = input()

found = False
for chr in s:
    if chr in alpha:
        del alpha[alpha.index(chr)]

if len(alpha) == 0:
    print("None")
else:
    print(alpha[0])
N,K = map(int,input().split())
x = list(map(int,input().split()))

ans = sum([abs(i) for i in x])
for i in range(N - K + 1):
    t = min(abs(x[i])+abs(x[i+K-1] - x[i]),abs(x[i+K-1]+abs(x[i+K-1]-x[i]))
    if t < ans:
        ans = t:

print(ans)

### FIXED CODE ###

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

min_t = 10e9
for i in range(N - K + 1):
    e = i + K - 1
    l = min(x[i], 0)
    r = max(x[e], 0)

    t = min(-l, r) * 2 + max(-l, r)
    min_t = min(min_t, t)

print(min_t)
n = int(input())
X = input()

def goes_to_zero(n):
  cnt = 0
  while(n > 0):
    n %= bin(n).count('1')
    cnt += 1
  return cnt
  
c1 = X.count('1')
xint = int(X,2)
xtp = xint % (c1 + 1)
if (c1 - 1) == 0:  
  xtm = 0
else:
  xtm = xint % (c1 - 1)
  
for i in range(n)  :
  if x[i] == '0':
    print(goes_to_zero( (xtp + pow(2,n-1-i,(c1+1))) % (c1+1) ) + 1)
  else:
    if (c1-1) == 0:
      print(0)
    else:
      print(goes_to_zero( (xtm - pow(2,n-1-i,(c1-1)) ) % (c1-1) ) +1)

### FIXED CODE ###

n = int(input())
X = input()

def goes_to_zero(n):
  cnt = 0
  while(n > 0):
    n %= bin(n).count('1')
    cnt += 1
  return cnt
  
c1 = X.count('1')
xint = int(X,2)
xtp = xint % (c1 + 1)
if (c1 - 1) == 0:  
  xtm = 0
else:
  xtm = xint % (c1 - 1)
  
for i in range(n)  :
  if X[i] == '0':
    print(goes_to_zero( (xtp + pow(2,n-1-i,(c1+1))) % (c1+1) ) + 1)
  else:
    if (c1-1) == 0:
      print(0)
    else:
      print(goes_to_zero( (xtm - pow(2,n-1-i,(c1-1)) ) % (c1-1) ) +1)
def main():
	N, M = map(int, input().split())
	points = [[] for _ in range(N+1)]
	for i in range(1, M+1):
		a, b, c = map(int, input().split())
		points[a].append([b, c, i])
		points[b].append([a, c, i])
	use = set()
	def dijksta(start):
		is_visited = [False]*(N+1)
		is_visited[0] = True
		is_visited[start] = True
		stack = list(points[start])
		while stack:
			stack.sort(key=lambda x: x[1])
			use_edge = stack.pop()
			cur = use_edge[0]
			dist = use_edge[1]
			use.add(use_edge[2])
			is_visited[cur] = True
			if all(is_visited):
				break
			add_stack = list(points[cur])
			removes = []
			for i, pair in enumerate(add_stack):
				if is_visited[pair[0]]:
					removes.append(i)
					continue
				add_stack[i][1] += dist
			removes.reverse()
			for i in removes:
				add_stack.pop(i)
			stack.extend(add_stack)
	for i in range(1, M+1):
		dijksta(i)
	ans = M - len(use)
	print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
	INF = 10**9+7
	N, M = map(int, input().split())
	dist = [[INF for _ in range(N+1)] for _ in range(N+1)]
	for i in range(1, N+1):
		for j in range(1, N+1):
			if i == j:
				dist[i][j] = 0
	a, b, c = [0]*M, [0]*M, [0]*M
	for i in range(M):
		a[i], b[i], c[i] = map(int, input().split())
		dist[a[i]][b[i]] = min(dist[a[i]][b[i]], c[i])
		dist[b[i]][a[i]] = min(dist[b[i]][a[i]], c[i])
	for k in range(1, N+1):
		for i in range(1, N+1):
			for j in range(1, N+1):
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
	ans = M
	for i in range(M):
		shrotest = False
		for j in range(1, N+1):
			if dist[j][a[i]]+c[i] == dist[j][b[i]]:
				shrotest = True
		if shrotest:
			ans -= 1
	print(ans)

if __name__ == '__main__':
    main()
X, A = map(int, input().split())
print(0 if X < a else 10)


### FIXED CODE ###

X, A = map(int, input().split())
print(0 if X < A else 10)
import queue
n = int(input())

wl = [[] for i in range(n+1)]

for i in range(2,n+1):
    ai = int(input())
    wl[ai].append(i)

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

def calc_dp(a):
    if len(wl[a]) == 0:
        return 0
    else:
        dps = []
        for i in wl[a]:
            dps.append(calc_dp(i))
        dps.sort(reverse=True)
        ma = 0
        for i,dpi in enumerate(dps):
            if ma < dpi+i:
                ma = dpi+i
        return ma+1

print(calc_dp(1))


### FIXED CODE ###

import sys
import resource
n = int(input())
sys.setrecursionlimit(10**5)

wl = [[] for i in range(n+1)]

for i in range(2,n+1):
    ai = int(input())
    wl[ai].append(i)

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

def calc_dp(a):
    if len(wl[a]) == 0:
        return 0
    else:
        dps = []
        for i in wl[a]:
            dps.append(calc_dp(i))
        dps.sort(reverse=True)
        ma = 0
        for i,dpi in enumerate(dps):
            if ma < dpi+i:
                ma = dpi+i
        return ma+1

print(calc_dp(1))
N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 'YES'
for i in range(N-1):
  if a[i] == a[i+1]:
    ans = 'NO'
    break
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = "YES"
for i in range(1,N):
    if A[i-1] == A[i]:
        ans = "NO"
        break
print(ans)
n=int(input())
m,a,r,c,h=0,0,0,0,0
for i in range(n):
    s=input()
    if s[0]=='M':
        m+=1
    elif s[0]=='A':
        a+=1
    elif s[0]=='R':
        r+=1
    elif s[0]=='C':
        c+=1
    elif s[0]=='H':
        h+=1
x=del ([m,a,r,c,h],0)
x.sort()
l=len(x)
if l<3:
    print(0)
elif l==3:
    print(x[0]*x[1]*x[2])
elif l==4:
    print()
else:
    print()

### FIXED CODE ###

n=int(input())
m,a,r,c,h=0,0,0,0,0
for i in range(n):
    s=input()
    if s[0]=='M':
        m+=1
    elif s[0]=='A':
        a+=1
    elif s[0]=='R':
        r+=1
    elif s[0]=='C':
        c+=1
    elif s[0]=='H':
        h+=1
x=[m,a,r,c,h]
cnt=x.count(0)
for i in range(cnt):
    x.remove(0)

l=len(x)
if l<3:
    print(0)
elif l==3:
    print(x[0]*x[1]*x[2])
elif l==4:
    a,b,c,d=x[0],x[1],x[2],x[3]
    print(a*b*c+a*b*d+a*c*d+b*c*d)
else:
    a,b,c,d,e=x[0],x[1],x[2],x[3],x[4]
    print(a*b*c+a*b*d+a*c*d+b*c*d\
         +e*a*b+e*a*c+e*a*d+e*b*c+e*b*d\
         +e*c*d)
N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
ans = [0]*(10**10)
A.sort()
count = 0
for b,c in BC:
    ans[count:b] = [c]*b
    count += b
ans.extend(A)
ans = sorted(ans,reverse = True)
print(sum(ans[:N]))

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [(A[i], 1) for i in range(N)]
for _ in range(M):
    B, C = map(int, input().split())
    BC.append((C,B))
BC = sorted(BC,reverse = True)
ans = 0
a = 0
count = N
for c,b in BC:
  lamb = min(count,b)
  ans += c * lamb
  count -= lamb

print(ans)
def maxreturn(t,n,a):
    ma=[0]*3
    if t==n-1:
        for i in range(3):
           ma[i]=a[n-1][i]
    else:
      b=list(maxreturn(t+1,n,a))
      
      for i in range(3):
        for j in range(3):
            if i!=j:
                ma[i]=max(ma[i],a[t][i]+b[j])
                
    return ma
n=int(input())
a=[[0]*3]*n
for i in range(n):
    a[i]=list(map(int,input().split()))
ma=maxreturn(0,n,a)
print(max(ma))

### FIXED CODE ###

n=int(input())
a=[[0]*3]*n
for i in range(n):
    a[i]=list(map(int,input().split()))
b=[0]*3
for i in range(n-2,-1,-1):
    for j in range(3):
        t=0
        for k in range(3):
            if j!=k:
                t=max(t,a[i][j]+a[i+1][k])
        a[i][j]=t
print(max(a[0]))
n = int(input())
s = [i for i in input().split()]

red = count('R')
blue = count('B')

if red > blue:
  print('Yes')
else:
  print ('No')

### FIXED CODE ###

n = int(input())
s = [i for i in input()]

red = s.count('R')
blue = s.count('B')

if red > blue:
  print('Yes')
else:
  print ('No')
def marubatu():
    N=list(input())
    for koma in ["o","x"]:
        for i in range(3):
            if N[i:9:3].count(koma)==3 or N[3*i:3*i+3].count(koma)==3:return koma
        if N[0:9:4].count(koma)==3 or N[2:7:2].count(koma)==3:return koma
    return "d"
while 1:
    print(marubatu())


### FIXED CODE ###

def marubatu():
    N=list(input())
    for koma in ["o","x"]:
        for i in range(3):
            if N[i:9:3].count(koma)==3 or N[3*i:3*i+3].count(koma)==3:return koma
        if N[0:9:4].count(koma)==3 or N[2:7:2].count(koma)==3:return koma
    return "d"
while 1:
    try:print(marubatu())
    except:break
A = list(map(int,input().split())
a = sum(A)
if a >= 22:
    print("bust")
else:
    print("win")

### FIXED CODE ###

A = list(map(int,input().split()))
a = sum(A)
if a >= 22:
    print("bust")
else:
    print("win")
n,ma,mb=map(int,input().split())
dpn=10**6
dp=[10**6]*dpn
dp[0]=0
for i in range(n):
    a,b,c=map(int,input().split())
    for j in range(dpn,-1,-1):
        if j==0 or dp[j]!=10**6:
            dp[j+a*1000+b]=min(dp[j+a*1000+b],dp[j]+c)
ans=10**6
s=1000*ma+mb
p=1
while s*p<10**6:
    ans=min(ans,dp[s*p])
    p+=1
print(ans)

### FIXED CODE ###

n,ma,mb=map(int,input().split())
dpn=400001
dp=[10**6]*dpn
dp[0]=0
for i in range(n):
    a,b,c=map(int,input().split())
    for j in range(dpn-1,-1,-1):
        if j==0 or dp[j]!=10**6:
            dp[j+a*1000+b]=min(dp[j+a*1000+b],dp[j]+c)
ans=10**6
s=1000*ma+mb
p=1
while s*p<dpn:
    ans=min(ans,dp[s*p])
    p+=1
if ans==10**6:
    print(-1)
else:
    print(ans)
n, m = map(int, input().split())
l1 = []
for i in range (m):
    ai = int(input())
    l1.append(ai)
s = sum(l1)
r = (n - s)
if r >= 0:
    print(r)
else:
    print("-1")

### FIXED CODE ###

import math
r = int(input())
p = math.pi
a = p * (r * 2)
print(a)
S = str(input())
for i in range(S):
  S = "x"*len(S)
print(S)

### FIXED CODE ###

S = str(input())
S = "x"*len(S)
print(S)
import math
from collections import defaultdict


def main():
    N, = [int(a) for a in input()]
    W = [input() for _ in range(N)]

    if len(set(W)) != len(W):
        print("No")
        return

    for i in range(len(W) - 1):
        if W[i][-1] != W[i + 1][0]:
            print("No")
            return
    print("Yes")


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math


def main():
    N = int(input())
    W = [input() for _ in range(N)]

    if len(set(W)) != len(W):
        print("No")
        return
    W = [list(a) for a in W]

    for i in range(len(W) - 1):
        if W[i][-1] != W[i + 1][0]:
            print("No")
            return
    print("Yes")


if __name__ == '__main__':
    main()
#editorial
n=int(input())
*a,=map(int, input().split())
pre=a[1]-a[0]
ans=1
for i in range(2,n):
    if pre*(a[i]-a[i-1])<0:
        pre=0
        ans+=1
    else:
        pre=a[i]-a[i-1]
print(ans)


### FIXED CODE ###

def f(n,a):
    if n==1:
        print(1)
        exit()
    pre=a[1]-a[0]
    ans=1
    for i in range(2,n):
        if pre*(a[i]-a[i-1])<0:
            pre=0
            ans+=1
        else:
            if a[i]-a[i-1]:###
                pre=a[i]-a[i-1]
    return ans

n=int(input())
*a,=map(int,input().split())
print(f(n,a))
def gcd(x,y):
  while y:
    x,y = y,x%y
  return x

A,B,C,D = map(int,input().split())
lcm = C*D // gcd(C,D)
print(B-A-(B//C-A//C)-(B//D-A//D)+(B//lcm-A//lcm))+1


### FIXED CODE ###

def gcd(x,y):
  while y:
    x,y = y,x%y
  return x

def calc(x,a,b,l):
  return x - (x//a) - (x//b) + (x//l)

A,B,C,D = map(int,input().split())
lcm = C*D // gcd(C,D)
print(calc(B,C,D,lcm) - calc(A-1,C,D,lcm))
a,b,c = map(int,input().split())

big = max(a,b,c)
total = a + b + c
if total = big*2:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

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

big = max(a,b,c)
total = a + b + c
if total == big*2:
    print("Yes")
else:
    print("No")
# ans

import sys
input = sys.stdin.readline
N = int(input())
d = list(map(int, input().split()))
d.sort()

print(d[N/2] - (d[N/2] - 1))

### FIXED CODE ###

# ans

import sys
input = sys.stdin.readline
N = int(input())
d = list(map(int, input().split()))
d.sort()

print(d[N // 2] - d[N // 2 - 1])
from itertools import combinations
from collections import Counter

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

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

fact = []
for a in A:
    x = prime_factorize(a)
    fact.append(x)

result = []
for f in fact:
    for i in range(1, len(f)+1):
        c = list(set(combinations(f, i)))
        for cc in c:
            result.append(cc)

count = dict(Counter(result))

ans = []
for key, value in count.items():
    temp = 1
    if value >= N-1:
        for k in key:
            temp *= k
        ans.append(temp)
        

print(max(ans))

### FIXED CODE ###

from math import gcd

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

A = [0] + A + [0]

#Left side
L = [A[1]]
tempL = A[1]
for i in range(1, N):
    tempL = gcd(tempL, A[i+1])
    L.append(tempL)
L = [0] + L
    
#Right side
R = [A[-2]]
tempR = A[-2]
for i in range(1, N):
    tempR = gcd(tempR, A[-i-2])
    R.append(tempR)
R = list(reversed(R)) + [0]

ans = []
for i in range(N):
    result = gcd(L[i], R[i+1])
    ans.append(result)

print(max(ans))
from scipy.special import comb

S = int(input())

n = S//3
k = S%3
Q = 10**9+7
ans = 0
for i in range(n):
    #iはしきりをとった数
    m = n-i #要素数
    ans += comb(n-1,i,exact=true)*comb(m,k,exact=True)
    if k==2:
        ans += k
    ans %=Q
print(ans)

### FIXED CODE ###

S = int(input())
A = [0]*(S+1)
A[0] = 1
MOD = 10**9+7

if S<=2:
    print(A[S])
    exit()

for i in range(3,S+1):
    for j in range(i-2):
        A[i] += A[j]
    A[i]%=MOD
print(A[S])
N = input()

While N > 0:
  OTURI = 1000 - N
  N -= 1000
  
print(OTURI)

### FIXED CODE ###

N = input()
Num = int(N)

while Num > 0:
    OTURI = 1000 - Num
    Num -= 1000
  
print(OTURI)
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
from operator import itemgetter
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


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

n, k = map(int, input().split())
ab = [readints() for _ in range(n)]
# print(ab)
abab = sorted(ab)
# print(abab)
tmp = 0
for i in range(n):
    tmp += ab[i][1]
    if tmp >= k:
        print(ab[tmp-k][0])
        exit()


### FIXED CODE ###

import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
from operator import itemgetter
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


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

n, k = map(int, input().split())
ab = [readints() for _ in range(n)]
# print(ab)
abab = sorted(ab)
# print(abab)
tmp = 0
for i in range(n):
    tmp += abab[i][1]
    if tmp >= k:
        print(abab[i][0])
        break
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    """
    cards_d = {}
    for card in cards:
        if not in cards_d:
            cards_d[card] = 1
        else:
            cards_d[card] += 1
    """
    S = sorted(_S, key=lambda x: x[1])
    i = 1
    while(i < len(S)):
        b = S[i][0]
        c = S[i][1]
        if S[i-1][1] == c:
            S[i-1][0] += b
            S.pop(i)
            i -= 1
        i += 1
    #print(S)

    for s in S:
        b = s[0]
        c = s[1]
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
        else:
            break
    #print(cards)
    return sum(cards)
    #else:
    #    return len(ra)



def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)
A,B,C=map(int(),input().split())
print((A*B)//2)

### FIXED CODE ###

a,b,c=map(int,input().split())
print(a*b//2)
import sys
n = int(input())
A = list(map(int,input().split()))
ANS = 1
for i in range(n):
    ANS *= A[i]
    if ANS > 10**18:
        print(-1)
        sys.exit(1)
print(ANS)

### FIXED CODE ###

import sys
n = int(input())
A = list(map(int,input().split()))
if A.count(0)>0:
    print(0)
else:
    ANS = 1
    for i in range(n):
        ANS *= A[i]
        if ANS > 10**18:
            print(-1)
            sys.exit()
    print(ANS)
def main():
    n,m=map(int,input().split())
    res=[1,1]
    a=int(input())
    gap=[a-1]
    flg=0
    mod=10**9+7
    for i in range(m-1):
        b=int(input())
        dif=b-a-1
        if dif==0:
            flg=1
            break
        else:
            gap.append(dif-1)
            a=b
    if flg==1:
        print(0)
    else:
        gap.append(n-a-1)
        for i in range(2,max(gap)+1):
            res.append((res[i-1]+res[i-2])%mod)
        ans=1
        for i in gap:
            ans=(ans*res[i])%mod
        print(ans)
if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    n,m=map(int,input().split())
    res=[1,1]
    flg=0
    mod=10**9+7
    a=n
    gap=[]
    if m!=0:
        a=int(input())
        gap.append(a-1)
        for i in range(m-1):
            b=int(input())
            dif=b-a-1
            if dif==0:
                flg=1
                break
            else:
                gap.append(dif-1)
                a=b
        gap.append(n-a-1)
    else:
        gap.append(n)
    if flg==1:
        print(0)
    else:
        for i in range(2,max(gap)+1):
            res.append((res[i-1]+res[i-2])%mod)
        ans=1
        for i in gap:
            ans=(ans*res[i])%mod
        print(ans)
if __name__=="__main__":
    main()