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

from collections import deque

def main():
    q =deque()
    H = 0
    for i in range(int(2e+06)):
        cmd = map(str,raw_input().split())
        if cmd[0] == "insert":
            q.append(int(cmd[1]))
            H += 1
            increase(q,H)
        elif cmd[0] == "extract":
            print q.popleft()
            H -= 1
            buildMaxHeap(q,H)
        else:
            break

def increase(A,i):
    p = i/2
    if 0 < p:
        if A[p-1] < A[i-1]:
            v = A[p-1]
            A[p-1] = A[i-1]
            A[i-1] = v
            increase(A,p)
            
def maxHeapify(A,i,H):
    l = 2*i
    r = 2*i+1
    if l <= H and A[l-1] > A[i-1]:
        largest = l
    else:
        largest = i
    if r <= H and A[r-1] > A[largest-1]:
        largest = r

    if largest != i:
        v = A[i-1]
        A[i-1] = A[largest-1]
        A[largest-1] = v
        maxHeapify(A,largest,H)

def buildMaxHeap(A,H):
    for j in range(H/2):
        i = H/2-j
        maxHeapify(A,i,H)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import heapq

def main():
    q = []
    while(True):
        cmd = map(str,raw_input().split())
        if cmd[0] == "insert":
            heapq.heappush(q,-int(cmd[1]))
        elif cmd[0] == "extract":
            print -heapq.heappop(q)
        else:
            break

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

N, K = [int(n) for n in input().split()]

A = [int(n) for n in input().split()]

count = 0
for i in range(1,N+1):
    A[i-1] %= K
    for j in range(1,N-i+2):
        if j == 1:
            s = sum(A[j-1:j-1+ i],0) % K
        else:
            s = s - A[j-2] + A[j-2+i]
        if s % K == i:
            count += 1

print(count)

### FIXED CODE ###

N, K = [int(n) for n in input().split()]

A = [int(n) for n in input().split()]

count = 0
for i in range(1,N+1):
    A[i-1] = A[i-1]-1

check = {0: [0,1,[0]]}

s = 0
for i in range(1,N+1):
    s = (s + A[i-1]) % K
    if s in check:
        j = check[s][0]
        l = check[s][1]
        while j < l and i - check[s][2][j] >= K:
            j += 1
        check[s][0] = j
        count += l - j
        check[s][2].append(i)
        check[s][1] = l + 1
    else:
        check[s] = [0,1,[i]]

print(count)
### BUGGY CODE ###

import math
n=int(input())
A=[int(i) for i in input().split()]
for i in range(n):
    A[i]-=i+1
ans=[]
for j in range(min(A),max(A)+1):
    B=A
    for i in range(n):
        B[i]-=j
        B[i]=abs(B[i])
    ans.append(sum(B))
print(min(ans))

### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
for i in range(n):
    A[i]-=i+1
A.sort()
if n%2==0:
    B=A.copy()
    C=A.copy()
    for i in range(n):
        s=A[n//2]
        B[i]=abs(B[i]-s)
    a=sum(B)
    for i in range(n):
        t=A[n//2-1]
        C[i]=abs(C[i]-t)
    b=sum(C)

    print(min(a,b))
else:
    B=A.copy()
    for i in range(n):
        B[i]=abs(B[i]-A[n//2])
    print(sum(B))
### BUGGY CODE ###

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

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

ans = 0
for x in range(N+1):
  rest = K - A*x
  if rest % B == 0:
    y = rest // B
    for g in range(max(0, x+y-N), min(x, y)+1):
      r = x - g
      b = y - g
      ans += (fact[N] // fact[r] // fact[g] // fact[b] // fact[N-r-g-b]) % 99824
4353

print(ans)

### FIXED CODE ###

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

MOD = 998244353
factorials = [1]
inv_facts = [1]
for i in range(1, N+1):
    factorials.append(factorials[-1] * i % MOD)
    inv_facts.append(inv_facts[-1] * pow(i, MOD-2, MOD) % MOD)

def combi(n, k):
    ret = factorials[n]
    ret *= inv_facts[k]
    ret %= MOD
    ret *= inv_facts[n-k]
    ret %= MOD
    return ret

ans = 0
for a in range(N+1):
    rest = K - (A * a)
    if rest < 0:
        break
    if rest % B == 0:
        b = rest // B
        if b <= N:
            tmp = combi(N, a) * combi(N, b) % MOD
            ans += tmp
            ans %= MOD
print(ans)
### BUGGY CODE ###

n,m=[int(i) for i in input().split()]
a=sorted([int(i) for i in input().split()])
bc=sorted([[int(i) for i in input().split()] for _ in range(m)],key=lambda x:x[1])[::-1]
d=[]
ans=0
for b,c in bc:
    d+=[c]*b
for i in range(n):
    try:
        #元のカード列と置き換えるカード列で大きい方を選ぶ
        ans+=max(a[i],d[i])
    except:
        ans+=a[i]
print(ans)

### FIXED CODE ###

n,m=[int(i) for i in input().split()]
a=sorted([int(i) for i in input().split()])
bc=sorted([[int(i) for i in input().split()] for _ in range(m)],key=lambda x:x[1])[::-1]
d=[]
ans=0
for b,c in bc:
    d+=[c]*b
    if len(d)>=n:
        break
for i in range(n):
    try:
        #元のカード列と置き換えるカード列で大きい方を選ぶ
        ans+=max(a[i],d[i])
    except:
        ans+=a[i]
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)


def dfs(v):
    global dp
    if v in dp:
        return dp[v]
    res = 0
    for next_v in e[v]:
        res = max(dfs(next_v) + 1, res)
    dp[v] = res
    return res


def main():
    N, M = map(int, input().split())
    global e
    e = [[] for _ in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
    global dp
    dp = [-1]*N
    ans = -1
    for v in range(N):
        ans = max(ans, dfs(v))
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    e = [[] for _ in range(N)]
    input_edges = [0]*N
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
        input_edges[v] += 1
    queue = deque()
    dp = [-1] * N
    for i, input_edge in enumerate(input_edges):
        if input_edge == 0:
            queue.appendleft(i)
            dp[i] = 0
    topological_sorted = []
    while queue:
        v = queue.pop()
        topological_sorted.append(v)
        for other_side in e[v]:
            input_edges[other_side] -= 1
            if input_edges[other_side] == 0:
                queue.appendleft(other_side)
    for v in topological_sorted:
        for other_side in e[v]:
            dp[other_side] = max(dp[v] + 1, dp[other_side])
    print(max(dp))


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

N,M = map(int,input().split())
dp=[0]*(N+1)
path = [[] for _ in range(N+1)]
for i in range(M):
  x,y = map(int,input().split())
  path[x].append(y)
  dp[y]=-1
  
cur = []
for i in range(1,N+1):
  if dp[i]==0:
    cur.append(i)

while(cur):
  nxt = set()
  for x in cur:
    for y in path[x]:
      dp[y] = max(dp[y],dp[x]+1)
      nxt.add(y)
  cur = []
  for x in nxt:
    cur.append(x)
print(max(dp))

### FIXED CODE ###

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

path = [[] for _ in range(N)]
pin = [0]*N
for _ in range(M):
  ip,op = map(int,input().split())
  pin[op-1]+=1
  path[ip-1].append(op-1)

cur = []
for i in range(N):
  if pin[i]==0:
    cur.append(i)

ans = 0
while cur:
  ans += 1
  nxt = []
  for ip in cur:
    for op in path[ip]:
      pin[op] -= 1
      if pin[op]==0 and not(op in nxt):
        nxt.append(op)
  cur = [x for x in nxt]
print(ans-1)
### BUGGY CODE ###

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

if N%2==1:
    if A.count(0)!=1:
        print(0)
        exit()
    elif A.count(0)==1:
        for i in range(1,N//2):
            if A.count(2*i)==2:
                pass
            else:
                print(0)
                exit()
else:
    for i in range(N//2):
        if A.count(2*i+1)==2:
            pass
        else:
            print(0)
            exit()

print(2**(N//2))    


### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]
mod=10**9+7
A=sorted(A)

if N%2==0:
    if all(A[i]==A[i+1] and A[0]==1 and A[1]==1 and A[i]-2==A[i-2] for i in range(2,N,2)):
        print((2**(N//2))%mod)
    else:
        print(0)
else:
    if all(A[0]==0 and A[i]==A[i-1] and A[i]-2==A[i-2] and A[-1]==N-1 for i in range(2,N,2)):
        print((2**(N//2))%mod)
    else:
        print(0)
### BUGGY CODE ###

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

ma=0
for x in range(len(a)+1):
    sa=sum(a[:x])
    for y in range(len(b)+1):
        if sa+sum(b[:y])>k:break
        ma=max(ma,x+y)
print(ma)

### FIXED CODE ###

import itertools
import bisect

n,m,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
b=list(map(int,input().split()))
aa=list(itertools.accumulate(a))
bb=list(itertools.accumulate(b))
r=0
for i,ax in enumerate(aa):
    bis=bisect.bisect_right(bb,k-ax)
    if bis==0 and ax>k:continue
    r=max(r,i+bis)
print(r)
### BUGGY CODE ###

import numpy as np


S = input().strip()

MOD = 10 ** 9 + 7

N = len(S)
DP = np.zeros((N+1, 13))
DP[0, 0] = 1

for _i, s in enumerate(S):
    i = _i + 1

    if s == '?':
        candidate = range(10)
    else:
        candidate = [int(s)]

    for j in range(13):
        for c in candidate:
            m = (j * 10 + c) % 13
            DP[i, m] += DP[i-1, j]
    DP[i] %= MOD

print(int(DP[-1, 5]))

### FIXED CODE ###

S = input().strip()

MOD = 10 ** 9 + 7

N = len(S)
DP = [[0] * 13 for i in range(N+1)]
DP[0][0] = 1

for _i, s in enumerate(S):
    i = _i + 1

    if s == '?':
        candidate = range(10)
    else:
        candidate = [int(s)]

    for j in range(13):
        for c in candidate:
            m = (j * 10 + c) % 13
            DP[i][m] += DP[i-1][j]
    for j in range(13):
        DP[i][j] %= MOD

print(int(DP[-1][5]))
### BUGGY CODE ###

import math
import random

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

def quick(x):
  pri = math.floor(A * x / B)
  lat = A * math.floor(x / B)
  return math.floor(pri - lat)

max = quick(N)
for i in range(1000000000):
  ran = math.floor(random.uniform(0, N))
  tem = quick(ran)
  if(max < tem):
    max = tem

print(max)

### FIXED CODE ###

import math
import random

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

def quick(x):
  pri = (A * x // B)
  lat = A * (x // B)
  return math.floor(pri - lat)

max = quick(N)
for i in range(8000000):
  ran = math.floor(random.uniform(0, N))
  tem = quick(ran)
  if(max < tem):
    max = tem

print(max)
### BUGGY CODE ###

S = str(input())
T = str(input())
A = ''

for i in range(len(S)+1):
	s = str(S[i:i+1])
	t = str(T[i:i+1])
	S = S.replace(s,'A')
	S = S.replace(t,s)
	S = S.replace('A',t)

answer = 'No'


if S == T:
	answer = 'Yes'
	
print(answer)

### FIXED CODE ###

#coding:utf-8

"""
自分の解答。これだとTLEになってしまったので、復習をします
from collections import Counter
S = str(input())
T = str(input())

for i in range(len(S)+1):
	s = str(S[i:i+1])
	t = str(T[i:i+1])
	S = S.replace(s,'A').replace(t,s).replace('A',t)

answer = 'No'

if S == T:
	answer = 'Yes'
	
print(answer)
"""

"""
対応表を作るイメージ。
azzel→appleにするのには
a a
z p
e i
l e
という変化を回せればおっけー

#初期値-1で、要素26コの対応表をつくる
start = [-1]*26
goal = [-1]*26
print(start)

"""


S = str(input())
T = str(input())

#辞書型を使ってみる。defaultdictは便利らしい。どこがかはちょっとよく分からなかった。
from collections import defaultdict
s = defaultdict(int)
t = defaultdict(int)


for i in S:
	s[i] += 1

for j in T:
	t[j] += 1

#辞書型をソートできるsoted()を使う。
#values()で辞書型のkey valueのvalueだけを取り出している。

ss = sorted(s.values())
tt = sorted(t.values())

if ss == tt:
	print('Yes')
else:
	print('No')
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
L.sort(reverse=True)

ans=0
for i in range(N-2):
  a=L[i]
  for j in range(i+1,N-1):
    b=L[j]
    for k in range(j+1,N):
      c=L[k]
      if a<b+c:
        ans+=1
      else:
        break
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
L=list(map(int,input().split()))

L.sort()
ans=0
for i in range(N-1):
  a=L[i]
  for j in range(i+1,N):
    b=L[j]
    right=bisect.bisect_left(L,a+b)
    ans+=right-j-1
print(ans)
### BUGGY CODE ###

import math
import itertools
n=int(input())
k=int(input())
def comb(n,k):
    return len(list(itertools.combinations(range(n), k)))
x=str(n)
m=len(x)
ans=0
for i in range(1,m):
    ans+=(comb(i-1,k-1)*(9**k))
if k==1:
    for i in range(1,10):
        if i*(10**(m-1))<=n:
            ans+=1
elif k==2:
    for i in range(1,10):
        if i*(10**(m-1))<=n:
            for j in range(m-1):
                for a in range(1,10):
                    if i*(10**(m-1))+a*(10**(j))<=n:
                        ans+=1
                    else:
                        break
        else:
            break
else:
    for i in range(1,10):
        if i*(10**(m-1))<=n:
            for j in range(m-1):
                for a in range(1,10):
                    if i*(10**(m-1))+a*(10**(j))<=n:
                        for b in range(j):
                            for c in range(1,10):
                                if i*(10**(m-1))+a*(10**(j))+c*(10**(b))<=n:
                                    ans+=1
                                else:
                                    break
                    else:
                        break
        else:
            break
print(ans)


### FIXED CODE ###

import math
import itertools
n=int(input())
k=int(input())
def comb(n,k):
    return len(list(itertools.combinations(range(n), k)))
x=str(n)
m=len(x)
ans=0
for i in range(1,m):
    ans+=(comb(i-1,k-1)*(9**k))
if k==1:
    for i in range(1,10):
        if i*(10**(m-1))<=n:
            ans+=1
elif k==2:
    for i in range(1,10):
        if i*(10**(m-1))<=n:
            for j in range(m-1):
                for a in range(1,10):
                    if i*(10**(m-1))+a*(10**(j))<=n:
                        ans+=1
                    else:
                        break
        else:
            break
else:
    po=[10**i for i in range(m)]
    for i in range(1,10):
        if i*po[m-1]<=n:
            for j in range(m-1):
                for a in range(1,10):
                    if i*po[m-1]+a*po[j]<=n:
                        for b in range(j):
                            for c in range(1,10):
                                ans+=(i*po[m-1]+a*po[j]+c*po[b]<=n)
                    else:
                        break
        else:
            break
print(ans)
### BUGGY CODE ###

n=list(map(int,input().split()))
p=list(map(int,input().split()))

x=[]
for i in range(n[0]):
    x.append((p[i]+1)/2)
y=[]
for i in range(n[0]-n[1]+2):
    y.append(sum(x[i:i+n[1]]))
print(max(y))

### FIXED CODE ###

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

for i in range(n):
    p[i]=(p[i]+1)/2#p[i]を期待値に変更
    
p_sum=[0]*n
ans=0
for i in range(n):
    if i==0:
        p_sum[i]=p[i]
        ans=p_sum[i]
    elif i<k:
        p_sum[i]=p_sum[i-1]+p[i]
        if p_sum[i]>ans:
            ans=p_sum[i]
    else:
        p_sum[i]=p_sum[i-1]+p[i]-p[i-k]
        if p_sum[i]>ans:
            ans=p_sum[i]
print(ans)
### BUGGY CODE ###

[n,k] = [int(i) for i in input().split()]
p = [(int(i)+1)/2 for i in input().split()]

a = []
#print(a)
ans = -1
ruiseki = []
for i in range(n-k+1):
    ruiseki.append(sum(p[i:i+k]))
print(max(ruiseki))


### FIXED CODE ###

[n,k] = [int(i) for i in input().split()]
p = [(int(i)+1)/2 for i in input().split()]
sm_l = [0]
#sm_r = [0]
for i in range(n):
	sm_l.append(sm_l[-1] + p[i])
	#sm_r.append(sm_r[-1] + p[-i-1])
ans = 0
for i in range(n-k+1):
	ans = max(ans,sm_l[i+k]-sm_l[i])
print(ans)
### BUGGY CODE ###

import collections
n = int(input())
s = [input() for i in range(n)]
c = collections.Counter(s)
x = c.most_common()[0][1]
a = []
for i in range(len(c)):
    y = c.most_common()[i][1]
    if y==x:
        a.append(c.most_common()[i][0])
a = sorted(a)
for i in a:
  print(i)

### FIXED CODE ###

import collections

N = int(input())
S = list(input() for i in range(N))
S.sort()

common = collections.Counter(S).most_common()
N_common = common[0][1]

candidates = [cand for cand in common if cand[1] == N_common]

for i in sorted(candidates):
    print(i[0])
### BUGGY CODE ###

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

    for v in range(1, N + 1):
        print(A.index(v) + 1, end=" ")

    print()


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans_list = [None for _ in range(N)]

    for i in range(N):
        ans_list[A[i] - 1] = i

    for v in ans_list:
        print(v + 1, end=" ")

    print()


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

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
tmp=[]
change=[]
for i in range(m):
    q,r=map(int,input().split())
    tmp.append([r,q])
tmp.sort(reverse=True)

for i in range(0,m):
    t=0
    cnt=0
    while t<tmp[i][1]:
        change.append(tmp[i][0])
        t+=1
        cnt+=1
    i+=cnt

if len(change)<n:
    while len(change)<=n:
        change.append(0)

for i in range(0,n):
    a[i]=max(a[i],change[i])

print(sum(a))


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
rep=[]
for i in range(m):
    b,c=map(int,input().split())
    rep.append([c,b])
rep.sort(reverse=True)
Card=[0]*n
cnt=0
fg=0
while fg<n and cnt<m:
    tt=0
    while tt<rep[cnt][1] and fg+tt <n :
        Card[fg+tt]=rep[cnt][0]
        tt+=1
    fg+=tt
    cnt+=1

a.sort()
ans=[]
for i in range(n):
    ans.append(max(a[i],Card[i]))

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

import bisect
n = int(input())
*l, = sorted(map(int, input().split()))

ans = 0
for i in range(n):
    for j in range(i+1, n):
        bc = l[i]+l[j]
        index = bisect.bisect_left(l, bc)
        ans += len(l[j+1:index])

print(ans)


### FIXED CODE ###

import bisect
n = int(input())
*l, = sorted(map(int, input().split()))

ans = 0
for i in range(n):
    for j in range(i+1, n):
        bc = l[i]+l[j]
        ans += bisect.bisect_left(l, bc)-(j+1)

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

def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    inlis = list(map(int, input().split()))
    ans = 1
    for i in inlis:
        ans *= i
        #print(ans)
    if ans > 10 ** 18:
        ans = -1
    print(ans)
    
 
 
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    inlis = list(map(int, input().split()))
    if 0 in inlis:
        ans = 0
    else:
        ans = 1
        for i in inlis:
            ans *= i
            #print(ans)
            if ans > 10 ** 18:
                ans = -1
                break
    print(ans)
    
 
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
p = list(map(int, readline().split()))
cnt = 0
for i in range(n):
    if all(p[i]<=p[j] for j in range(i+1)):
        cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 0
m = 10**6
for i in p:
    if i < m:
        m = i
        cnt += 1
print(cnt)
### BUGGY CODE ###

import sys

MOD = 998244353

def main():
    N, S = map(int, input().split())
    X = [int(x) for x in sys.stdin.readline().split()]

    dp = [[0 for _ in range(S+1)] for _ in range(N+1)]
    dp[0][0] = 1

    for i in range(1, N+1):
        xi = X[i-1]
        for j in range(S+1):
            # xi を U に加えない場合
            dp[i][j] += dp[i-1][j]*2 % MOD # T に加える／加えない
            dp[i][j] %= MOD
            # xi を U に加える場合
            if j+xi > S: continue
            dp[i][j+xi] += dp[i-1][j] % MOD
            dp[i][j+xi] %= MOD

    print(dp[N][S] % MOD)

main()

### FIXED CODE ###

import sys

MOD = 998244353

def main():
    N, S = map(int, input().split())
    X = [int(x) for x in sys.stdin.readline().split()]

    # dp = np.zeros((N+1)*(S+1), dtype=np.int).reshape((N+1),(S+1))
    dp = [[0 for _ in range(S+1)] for _ in range(N+1)]

    dp[0][0] = 1

    for i in range(N):
        xi = X[i]
        # xi を U に加えない場合
        for j in range(S+1):
            dp[i+1][j] += dp[i][j]*2  # T に加える／加えない
            dp[i+1][j] %= MOD
            # xi を U に加える場合
            if j+xi > S: continue
            dp[i+1][j+xi] += dp[i][j]
            dp[i+1][j+xi] %= MOD

    print(dp[N][S] % MOD)

main()
### BUGGY CODE ###

import copy
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
n,m,r=map(int,input().split())
R=list(map(int,input().split()))
for i in range(r):
  R[i]=R[i]-1
d=[[10**10]*n for i in range(n)] 
for i in range(m):
  a,b,c=map(int,input().split())
  a=a-1
  b=b-1
  d[a][b]=c
  d[b][a]=c
for i in range(n):
  d[i][i]=0
D=warshall_floyd(d)
s=1
S=[]
for i in range(1,r+1):
  s=s*i
  S.append(s)
ans=10**10
for i in range(s):
  RR=copy.copy(R)
  E=[]
  for j in range(r-1):
    E.append(RR[i//S[r-j-2]])
    RR.pop(i//S[r-j-2])
    i=i-S[r-j-2]*(i//S[r-j-2])
  E.append(RR[0]) 
  di=0
  for i in range(r-1):
    di=di+D[E[i]][E[i+1]]
  if di<ans:
    ans=di
print(ans)

### FIXED CODE ###

import copy
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
n,m,r=map(int,input().split())
R=list(map(int,input().split()))
for i in range(r):
  R[i]=R[i]-1
d=[[10**10]*n for i in range(n)] 
for i in range(m):
  a,b,c=map(int,input().split())
  a=a-1
  b=b-1
  d[a][b]=c
  d[b][a]=c
for i in range(n):
  d[i][i]=0
D=warshall_floyd(d)
s=1
S=[]
for i in range(1,r+1):
  s=s*i
  S.append(s)
ans=10**10
for i in range(s):
  RR=copy.copy(R)
  E=[]
  for j in range(r-1):
    E.append(RR[i//S[r-j-2]])
    RR.pop(i//S[r-j-2])
    i=i-S[r-j-2]*(i//S[r-j-2])
  E.append(RR[0]) 
  di=0
  for i in range(r-1):
    di=di+D[E[i]][E[i+1]]
  if di<ans:
    ans=di
print(ans)
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for i in range(k+1):
  for j in range(k+1):
    if s == i + j + (s - i - j) and 0 <= s-i-j <= k:
      ans += 1
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for i in range(k+1):
  for j in range(k+1):
    z = s - i - j
    if 0 <= z <= k:
      ans += 1
print(ans)
### BUGGY CODE ###

import math
n=int(input())
a=list(map(int,input().split()))
l=[0]*(n)
l1=[0]*(n)
for i in range(n):
    l[a[i]-1]+=1
    
def combinations_count(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

for i in range(n):
    if l[i]>=2:
        l1[i]+=combinations_count(l[i],2)

l1sum=sum(l1)
for i in range(n):
    if l[a[i]-1]-1>=2:print(l1sum-l1[a[i]-1]+combinations_count(l[a[i]-1]-1,2))
    else:print(l1sum-l1[a[i]-1])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l=[0]*(n)
l1=[0]*(n)
for i in range(n):
    l[a[i]-1]+=1
    
for i in range(n):
    if l[i]>=2:
        l1[i]+=l[i]*(l[i]-1)//2

l1sum=sum(l1)
for i in range(n):
    if l[a[i]-1]-1>=2:print(l1sum-l1[a[i]-1]+ (l[a[i]-1]-1)*(l[a[i]-1]-2)//2)
    else:print(l1sum-l1[a[i]-1])
### BUGGY CODE ###

n=int(input())
li=list(map(int, input().split()))
ans="YES"
for i in range(n):
  if li.count(li[i]) >= 2:
    ans="NO"
    break
print(ans)

### FIXED CODE ###

n=int(input())
li=list(map(int, input().split()))
if n==len(set(li)):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

N, M = list(map(int, input().split()))
C = list(map(int, input().split()))
C = sorted(C)
AB = [list(map(int, input().split())) for i in range(M)]
AB = sorted(AB, key=lambda x: x[1], reverse=True)
AB = [ab[1] for ab in AB for i in range(ab[0])]

result = sum(C)
result += sum([AB[i] - C[i] for i in range(min([len(C), len(AB)])) if AB[i] > C[i]])
print(result)

### FIXED CODE ###

def main():
  N, M = list(map(int, input().split()))
  C = list(map(int, input().split()))
  C = sorted(C)
  AB = [list(map(int, input().split())) for i in range(M)]
  AB = sorted(AB, key=lambda x: x[1], reverse=True)
  
  result = 0
  i, j = 0, 0
  while i < N:
    A, B = AB[j] if j < M else (0, 0)
    j += 1
    if i+A < N and B >= C[i+A]:
      i += A
      result += A * B
    else:
      break
    
  while i < N:
    if C[i] > B:
      result += sum(C[i:])
      break
    else:
      result += B
      A -= 1      
      if j < M and A == 0:
        A, B = AB[j] if j < M else (0, 0)
        j += 1
    
    i += 1
  
  print(result)

if __name__ == "__main__":
  main()