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

import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
inf = float('inf')
d = [[inf for j in range(N)] for i in range(N)]

for i in range(N):
    d[i][i] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    t = min(c, d[a][b])
    if d[a][b] > c:
        d[a][b], d[b][a] = t, t

for i in range(N):
    for j in range(N):
        for k in range(N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = inf
for i in list(itertools.permutations(r)):
    temp = 0
    flag = False
    for j in i:
        if flag:
            temp += d[prev][j - 1]
        else:
            flag = True
        prev = j - 1
    ans = min(ans, temp)

print(ans)

### FIXED CODE ###

from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())
    inf = float('inf')
    d = [[inf] * N for i in range(N)]

    for i in range(N):
        d[i][i] = 0

    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if d[a][b] > c:
            d[a][b], d[b][a] = c, c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                temp = d[i][k] + d[k][j]
                if d[i][j] > temp:
                    d[i][j] = temp

    ans = inf
    for i in permutations(r):
        temp = 0
        for j in range(len(i)-1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        if ans > temp:
            ans = temp

    print(ans)


main()
### BUGGY CODE ###

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

def merge(l) :
  length = len(l)
  
  if(length <= 1) :
    return 0, l
  
  flag, left = merge(l[0:int(length/2)])
  if(flag == 1) :
    return 1, l
  flag, right = merge(l[int(length/2):length])
  if(flag == 1) :
    return 1, l
  
  total = []
  while(True) :
    if(len(left) == 0) :
      total.extend(right)
      return 0, total
    if(len(right) == 0) :
      total.extend(left)
      return 0, total
    if(left[0] == right[0]) :
      return 1, l
    if(left[0] < right[0]) :
      total.append(left.pop(0))
    else :
      total.append(right.pop(0))
        
flag, temp = merge(a)
if(flag == 1) :
  print("NO")
else :
  print("YES")

### FIXED CODE ###

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

def merge(l) :
  length = len(l)
  
  if(length <= 1) :
    return 0, l
  
  flag, left = merge(l[0:int(length/2)])
  if(flag == 1) :
    return 1, l
  flag, right = merge(l[int(length/2):length])
  if(flag == 1) :
    return 1, l
  
  total = []
  while(True) :
    if(len(left) == 0) :
      total.extend(right)
      return 0, total
    if(len(right) == 0) :
      total.extend(left)
      return 0, total
    if(left[0] == right[0]) :
      return 1, l
    if(left[0] < right[0]) :
      total.append(left.pop(0))
    else :
      total.append(right.pop(0))
        
a.sort()
for i in range(0, len(a)-1) :
  if(a[i] == a[i+1]) :
    print("NO")
    exit()

print("YES")
### BUGGY CODE ###

n = int(input())
s = ["".join(sorted(input())) for _ in range(n)]
set_s = set(s)
seq_s = "".join(s)
ans = 0
start_i = 0
used_s = {}
for i in range(n):
    cnt = used_s.get(s[i],seq_s.count(s[i],start_i) if s[i] in set(s) else 0)
    ans += cnt - 1
    used_s[s[i]] = cnt - 1
    start_i += len(s[i])

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
used_s = {}
for _ in range(n):
    s = "".join(sorted(input()))
    if not s in used_s.keys():
        used_s[s] = 0
    else:
        used_s[s] += 1
        ans += 1 * used_s[s]

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

import functools

n = int(input())
R = [int(input()) for i in range(n)]

benefit = [[rj - ri for j,rj in enumerate(R[i:]) if j+i > i] for i,ri in enumerate(R)]
print(max(functools.reduce(lambda a,b: a+b, benefit)))

### FIXED CODE ###

n = int(input())
R = [int(input()) for i in range(n)]

minv = float('inf')
maxv = -float('inf')
for r in R:
    maxv = max(maxv, r-minv)
    minv = min(minv, r)
print(maxv)
### BUGGY CODE ###

import heapq
        
N, M = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)

for i in range(M):
    B, C = map(int, input().split())
    for j in range(B):
        if A[0] < C:
            heapq.heapreplace(A, C)
        else:
            break

ans = sum(A)
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
p = [[A[i], 1] for i in range(N)]   # Aのカードは各1枚ずつ

for i in range(M):
    B, C = map(int, input().split())
    p.append([C, B])    # CのカードをB枚追加

p.sort()
p.reverse()

ans = 0
cnt = N
for v, n in p:
    num = min(cnt, n)    # 残り枚数とvのカード枚数の少ない方を採用
    ans += v * num
    cnt -= num
    if cnt == 0:
        break

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

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = ["".join(sorted([c for c in S()])) for _ in range(n)]
    r = 0
    for i in range(n):
        for j in range(i+1,n):
            if a[i] == a[j]:
                r += 1

    return r


print(main())





### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = collections.Counter(["".join(sorted([c for c in S()])) for _ in range(n)])
    r = 0
    for i in a.values():
        r += i * (i-1) // 2

    return r


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

N = int(input())
A = [None]*N
B = [None]*N
for i in range(N):
    A[i], B[i] = map(int, input().split())

now = 0

for i in range(N):
    job = B.index(min(B))
    now += A.pop(job)
    deadline = B.pop(job)
    if now > deadline:
        print("No")
        quit()
else:
    print("Yes")


### FIXED CODE ###

from sys import stdin

N = int(stdin.readline())
Job = [None]*N
for i in range(N):
    Job[i] = tuple(map(int, stdin.readline().split()))[::-1]

Job.sort()

Now = 0
for i in range(N):
    Deadline = Job[i][0]
    Now += Job[i][1]
    if Now > Deadline:
        print("No")
        quit()

else:
    print("Yes")
### BUGGY CODE ###

N=int(input())
ans=N
S=[input() for i in range(N)]
for i in range(N):
    a=1
    for j in range(N):
        if i>j:
            if S[i]==S[j]:
                a=0
            else:
                pass
    if a==0:
        ans=ans-1
    else:
        pass
print(ans)


### FIXED CODE ###

N=int(input())
ans=N
S=[input() for i in range(N)]
S.sort()
for i in range(N-1):
    if S[i]==S[i+1]:
        ans=ans-1
    else:
        pass
print(ans)
### BUGGY CODE ###

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

max_s = 0
for i in range(N):
  if i+K < N and P[i] < P[i+K]:
    continue
  elif i+K > N:
    continue
  sum_K = sum(P[0+i:K+i])
  if max_s < sum_K:
    max_s = sum_K
print((max_s+K) / 2)

### FIXED CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
s = [0] * 1000000
for i in range(N):
    s[i+1] = s[i] + A[i]

max_s = 0
for i in range(N):
    if max_s < s[i+K] - s[i]:
        max_s = s[i+K] - s[i]


print((max_s+K) / 2)
### BUGGY CODE ###

from math import *

def comb(n, r):
    ''' nCr '''
    if n == 1:
        return 0
    return int(factorial(n)/(factorial(r)*factorial(n-r)))

N = int(input())
a = [int(a_i) for a_i in input().split()]
s = []  # s[i] = a[0]からa[i+1]までの総和
sum = 0
for i in range(N):
    sum += a[i]
    s.append(sum)
ans = 0
s.sort()
val = float('inf')  # 前から見ていくときのs[i]の値
for s_i in s:
    if s_i == val:
        continue
    val = s_i
    if val == 0:
        ans += s.count(0) + comb(s.count(0), 2)
    else:
        ans += comb(s.count(val), 2)
print(ans)


### FIXED CODE ###

from collections import defaultdict

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

sum = [0]
for i in range(N):
    sum.append(sum[i] + A[i])

sum.sort()
dict = defaultdict(int)
for i in range(N + 1):
    dict[sum[i]] += 1

ans = 0
for key, val in dict.items():
    ans += val * (val - 1) // 2

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

N = int(input())
cnt = 0
for i in range(1,N+1):
  for j in range(1,N+1):
    if str(i)[0:1:] == str(j)[-1::] and str(i)[-1::] == str(j)[0:1:]:
      cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
cnt = [[0]*10 for _ in range(10)]
for i in range(1, N+1):
  head = int(str(i)[0])
  tail = int(str(i)[-1])
  cnt[head][tail] += 1
ans = 0
for i in range(1, 10):
  for j in range(1, 10):
    ans += cnt[i][j]*cnt[j][i]
print(ans)
### BUGGY CODE ###

n=int(input())
l=[]
for i in range(n):
  l.append(int(input()))
for i in range(n):
  a = l[i]
  l[i] = 0
  print(max(l))
  l[i] = a

### FIXED CODE ###

n=int(input())
l=[]
for i in range(n):
  l.append(int(input()))
m=max(l)
a=l.index(m)
for i in range(n):
  if i==a:
    l[i]=0
    print(max(l)) 
  else:print(m)
### BUGGY CODE ###

n=int(input())
s=1
f=0
x=[int(x) for x in input().split()]
for i in range(len(x)):
    s=s*x[i]
if s>10**18:
    print(-1)
else:print(s)

### FIXED CODE ###

n=int(input())
s=1
f=0
x=[int(x) for x in input().split()]
if x.count(0)>0:
    print(0)
else:
    for i in range(len(x)):
        s=s*x[i]
        if s>10**18:
            f=1
            break
    if f:
        print(-1)
    else:print(s)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

  dp=[inf]*100010
  dp[0]=0

  for i in range(n):
    for j in range(1,k+1):
      if i+j<n:
        dp[i+j]=min(dp[i+j],dp[i]+abs(l[i]-l[i+j]))

  return dp[n-1]

print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

  dp=[inf]*100010
  dp[0]=0
  for i in range(n):
    for j in range(1,k+1):
      if i+j<n:
        dp[i+j]=min(dp[i+j],dp[i]+abs(l[i+j]-l[i]))

  return dp[n-1]

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

q=int(input())
import math
def is_prime(n):
    if n==1:return False
    for k in range(2,int(math.sqrt(n))+1):
        if n%k==0:
            return False
    return True
ko=[]
for i in range(1,10**5,2):
    if is_prime((i+1)//2)==True:
        if is_prime(i)==True:
            ko.append(i)      
for i in range(q):
    l,r=map(int,input().split())   
    ans0=1
    ans1=0
    for i in range(len(ko)):
        if l<=ko[i]:
            ans0=i
            break
    for i in range(len(ko)):
        if r<ko[i]:
            ans1=i-1
            break
    print(ans1-ans0+1)

### FIXED CODE ###

q=int(input())
import math
import numpy as np
def is_prime(n):
    if n==1:return False
    for k in range(2,int(math.sqrt(n))+1):
        if n%k==0:
            return False
    return True
def is_is_prime(n):
    an=0
    if is_prime((n+1)//2)==True:
        if is_prime(n)==True:
            an=1
    return an
ko=[]
for i in range(1,10**5,2):
    ko.append(is_is_prime(i))

koko=np.cumsum(ko)

for i in range(q):
    l,r=map(int,input().split()) 
    if l==1:
        ans=koko[(r-1)//2]-koko[(l-1)//2]
    else:
        ans=koko[((r-1)//2)]-koko[((l-1)//2)-1]
    print(ans)
### BUGGY CODE ###

from math import sqrt

person = int(input())
longs = list(map(int, input().split(" ")))

sum = 0
for i in range(person):
    for j in range(i, person):
        if (j - i) == longs[i] + longs[j]:
            sum += 1
print(sum)

### FIXED CODE ###

from math import sqrt

person = int(input())
longs = list(map(int, input().split(" ")))

longsi_dic = {}
for i in range(len(longs)):
    if str(i + longs[i]) not in longsi_dic:
        longsi_dic[str(i + longs[i])] = 0
    longsi_dic[str(i + longs[i])] += 1

longsj_dic = {}
for j in range(len(longs)):
    if str(j - longs[j]) not in longsj_dic:
        longsj_dic[str(j - longs[j])] = 0
    longsj_dic[str(j - longs[j])] += 1

sum = 0
for val, sumi in longsi_dic.items():
    if val not in longsj_dic:
        continue
    sum += int(sumi) * int(longsj_dic[val])

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

n = int(input())
s = list(input())
pin_li = []
for i in range(len(s)):
    for j in range(i+1,len(s)):
        for k in range(j+1,len(s)):
            pin_li.append(s[i]+s[j]+s[k])
print(len(set(pin_li)))

### FIXED CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(1000):
    p = '{:03}'.format(i)
    s2 = s
    for j in range(3):#indexのループ
        if s2.find(p[j]) == -1:
            break
        s2 = s2[s2.find(p[j]) +1:]
    else:
        cnt+=1
print(cnt)
### BUGGY CODE ###

from collections import deque

INF = 10**12

H, W = map(int, input().split())
sx, sy = map(lambda x: int(x) - 1, input().split())
gx, gy = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3)
        for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
d = [[INF] * W for _ in range(H)]
d[sx][sy] = 0
q.append((sx, sy, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] > s:
            d[nx][ny] = s
            q.appendleft((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] > s+1:
            d[nx][ny] = s + 1
            q.appendleft((nx, ny, s+1))

ans = d[gx][gy] if d[gx][gy] < INF else -1
print(ans)


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

x,y,z,k = map(int,input().split())

A = sorted(map(int,input().split()))[::-1]
B = sorted(map(int,input().split()))[::-1]
C = sorted(map(int,input().split()))[::-1]

AB = [a+b for a in A for b in B]
AB.sort(reverse = True)

ans = [ab + c for ab in AB[:k] for c in C]
ans.sort(reverse = True)

for i in ans[:k]:
    print(i)



### FIXED CODE ###

# coding: utf-8
# Your code here!

x,y,z,k = map(int,input().split())

A = sorted(map(int,input().split()))[::-1]
B = sorted(map(int,input().split()))[::-1]
C = sorted(map(int,input().split()))[::-1]

AB = sorted([a+b for a in A for b in B])[::-1]

ans = sorted([ab + c for ab in AB[:k] for c in C])[::-1]

for i in ans[:k]:
    print(i)
### BUGGY CODE ###

#!/usr/bin/env python3

from typing import Iterable


def main() -> None:
    N = ri()
    A = rmi()
    num = tuple(range(1, N + 1))
    cand = 0
    for a in range(N):
        for b in range(a + 1, N):
            diff_num = b - a
            sum_height = A[a] + A[b]
            if diff_num == sum_height:
                cand += 1
    w(cand)


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> int:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(data: Iterable) -> None:
    print(' '.join(list(map(str, data))))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

from typing import Iterable


def main() -> None:
    N = ri()
    A = rmi()
    num = tuple(range(1, N + 1))
    cand = 0
    log = {}
    for i in range(0, N):
        if i + 1 - A[i] in log:
            cand += log[i + 1 - A[i]]
        if i + 1 + A[i] in log:
            log[i + 1 + A[i]] += 1
        else:
            log[i + 1 + A[i]] = 1
    w(cand)


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> int:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(data: Iterable) -> None:
    print(' '.join(list(map(str, data))))


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

n=input()
l1=list(n)
l1=l1[::-1]
num=len(n)
ans=[0 for i in range(13)]
if l1[0]=="?":
  for i in range(0,10):
    ans[i]=1
else:
  ans[int(l1[0])]=1
for i in range(1,num):
  mod=(10**i)%13
  dp=[ans[i] for i in range(13)]
  if l1[i]=="?":
    lmod=[(j*mod)%13 for j in range(10)]
    for j in range(13):
      ans1=0
      for k in lmod:
        if j-k>=0:
          mod2=j-k
        else:
          mod2=13+j-k
        ans1=(ans1+dp[mod2])%(10**9+7)
      ans[j]=ans1%(10**9+7)
  else:
    num1=int(l1[i])
    mod1=(num1*mod)%13
    for j in range(13):
      if j-mod1>=0:
        mod2=j-mod1
      else:
        mod2=13+j-mod1
      ans[j]=dp[mod2]
print(ans[5]%(10**9+7))

### FIXED CODE ###

n=input()
l1=list(n)
l1=l1[::-1]
num=len(n)
ans=[0 for i in range(13)]
modlist=[1,10,9,12,3,4]
if l1[0]=="?":
  for i in range(0,10):
    ans[i]=1
else:
  ans[int(l1[0])]=1
for i in range(1,num):
  mod=modlist[i%6]
  dp=[ans[i] for i in range(13)]
  if l1[i]=="?":
    lmod=[(j*mod)%13 for j in range(10)]
    for j in range(13):
      ans1=0
      for k in lmod:
        if j-k>=0:
          mod2=j-k
        else:
          mod2=13+j-k
        ans1=(ans1+dp[mod2])%(10**9+7)
      ans[j]=ans1%(10**9+7)
  else:
    num1=int(l1[i])
    mod1=(num1*mod)%13
    for j in range(13):
      if j-mod1>=0:
        mod2=j-mod1
      else:
        mod2=13+j-mod1
      ans[j]=dp[mod2]
print(ans[5]%(10**9+7))
### BUGGY CODE ###

import math

K=int(input())

ans=0
for i in range(K):
    for j in range(K):
        for k in range(K):
            ans+=math.gcd(math.gcd(j+1,k+1),i+1)

print(ans)

### FIXED CODE ###

import math

K=int(input())

ans=0
for i in range(K):
    for j in range(K):
        for k in range(K):
            ans+=math.gcd(math.gcd(j+1,k+1),i+1)

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

import heapq as hq

N, M = [int(_) for _ in input().split()]
A = []
for a in input().split():
    hq.heappush(A, int(a))

for i in range(M):
    b, c = [int(_) for _ in input().split()]

    for j in range(b):
        if not A: break
        if A[0] >= c: break
        if A[0] < c:
            hq.heappop(A)
            hq.heappush(A, c)

print(sum(A))

### FIXED CODE ###

N, M = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
A.sort()

BC = []
for i in range(M):
    v = [v for v in input().split()]
    BC.append((int(v[0]), int(v[1])))

BC.sort(key=lambda x: -x[1])

i = 0

fin = False
for b, c in BC:
    for _ in range(b):
        if i >= N:
            fin = True
            break

        if A[i] < c:
            A[i] = c
            i += 1
        else:
            fin = True
            break
    if fin:
        break
print(sum(A))
### BUGGY CODE ###

import sys
n, limit= map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

#各重さとi番目の荷物を入れ終わった状態のテーブルをつくる
dp = [[0 for _ in range(limit+1)] for _ in range(n)]

#初期状態
for w in range(limit+1):
    if L[0][0] <=w:
        dp[0][w] = L[0][1]

for i in range(n):
    for w in range(limit+1):
        if w < L[i][0]: #場合分け 荷物よりも容量が小さいとき
            dp[i][w] = dp[i-1][w]
        else:           # 荷物よりも容量が大きいとき
            dp[i][w] = max(L[i][1] + dp[i-1][w-L[i][0]], dp[i-1][w]) # w = (w - L[i][0]) + L[i][0]

print(max(dp[-1]))

### FIXED CODE ###

import sys
n, W = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [[0 for _ in range(W+1)] for _ in range(n)]
for w in range(W+1):
    if w>=L[0][0]:
        dp[0][w] = L[0][1]

#print(dp)
for i in range(1, n):
    for w in range(W+1):
        if w <L[i][0]: #そもそも加えられないとき
            dp[i][w] = dp[i-1][w] #前回の状態を代入。
        else: #加えようとしたら入るとき
            dp[i][w] = max(dp[i-1][w-L[i][0]] + L[i][1], dp[i-1][w]) #max(加えた時の価値, 前回の状態)
            
#print(dp)
print(max(dp[-1]))
### BUGGY CODE ###

import sys

n,k=map(int,input().split())
be=n

if n%k==0:
  print(0)
  
else:
  while True:
    if abs(n-k)<=be:
      be=abs(n-k)
    else:
      print(be)
      sys.exit()
    n=abs(n-k)

### FIXED CODE ###

import math

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

be=n%k
af=abs(k-be)

print(be if be<=af else af)
### BUGGY CODE ###

N = int(input())
Sn = set()
for i in range(N):
    s = {input()}
    Sn = Sn | s
print(len(Sn))


### FIXED CODE ###

N = int(input())
Sn = []
for i in range(N):
    s = input()
    Sn.append(s)
print(len(set(Sn)))
### BUGGY CODE ###

h, n = map(int, input().split())
a = []
b = []
for i in range(n):
    a_tmp, b_tmp = map(int, input().split())
    a.append(a_tmp)
    b.append(b_tmp)

a_max = max(a)
dp_max = 100000000
dp = [dp_max] * (h + a_max + 1)
dp[0] = 0

for i in range(h):
    if dp[i] == dp_max:
        continue
    for j in range(n):
        a_current = a[j]
        b_current = b[j]
        if dp[i] + b_current < dp[i + a_current]:
            dp[i + a_current] = dp[i] + b_current

dp_min = dp_max
for i in range(h, h + a_max + 1):
    if dp[i] < dp_min:
        dp_min = dp[i]

print(dp_min)

### FIXED CODE ###

h, n = map(int, input().split())
a = []
b = []
for i in range(n):
    a_tmp, b_tmp = map(int, input().split())
    a.append(a_tmp)
    b.append(b_tmp)

a_max = 10000
dp_max = 100000000
dp = [dp_max] * (h + a_max + 1)
dp[0] = 0

for i in range(h):
    if dp[i] == dp_max:
        continue
    for j in range(n):
        a_current = a[j]
        b_current = b[j]
        if dp[i] + b_current < dp[i + a_current]:
            dp[i + a_current] = dp[i] + b_current

dp_min = dp_max
for i in range(h, h + a_max + 1):
    if dp[i] < dp_min:
        dp_min = dp[i]

print(dp_min)