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

import itertools


def warshal_floyd(d):
    # d[i][j] := iからjへの最短距離
    global N
    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])
    # "今現在求まっているiからjへの最短距離"と"今現在求まっているiからkへの最短距離 + 今現在求まっているkからjへの最短距離 の和"を比較する
    return d


N, M, R = map(int, input().split())  # N個の町, M本の道, R個の町を訪れることになった
town = list(map(lambda x: int(x)-1, input().split()))
distant = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    distant[a][b] = c
    distant[b][a] = c
for i in range(N):
    distant[i][i] = 0


warshal_floyd(distant)
ans = 10**9
for x in itertools.permutations(town):
    x = list(x)
    now = x[0]
    tmp = 0
    for i in range(1, len(x)):
        tmp += distant[now][x[i]]
        now = x[i]
    ans = min(ans, tmp)
print(int(ans))

### FIXED CODE ###

# from scipy.sparse.csgraph import floyd_warshall
import itertools


def warshal_floyd(d):
    # d[i][j] := iからjへの最短距離
    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])
    # "今現在求まっているiからjへの最短距離"と"今現在求まっているiからkへの最短距離 + 今現在求まっているkからjへの最短距離 の和"を比較する
    return d


N, M, R = map(int, input().split())  # N個の町, M本の道, R個の町を訪れることになった
town = list(map(lambda x: int(x)-1, input().split()))
distant = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    distant[a][b] = c
    distant[b][a] = c
for i in range(N):
    distant[i][i] = 0

warshal_floyd(distant)
# print(distant)  # Rは最大8だから全てを試しても大丈夫
ans = 10**9
for x in itertools.permutations(town):
    x = list(x)
    now = x[0]
    tmp = 0
    for i in range(1, len(x)):
        tmp += distant[now][x[i]]
        now = x[i]
    ans = min(ans, tmp)
print(ans)
### BUGGY CODE ###

import math
K = int(input())
S = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for l in range(1,K+1):
      S = S + math.gcd(l, math.gcd(j,i))

print(S)


### FIXED CODE ###

import math
K = int(input())
S = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for l in range(1,K+1):
      S = S + math.gcd(l, math.gcd(j,i))

print(S)
### BUGGY CODE ###

# D - Integer Cards

import numpy as np

n, m = map(int, input().split())
A = np.array(list(int(x) for x in input().split()))

def binary_search(searchList, target):
    l = -1
    r = len(searchList)
    while l+1<r:
        m = (l+r)//2
        if target>=searchList[m]:
            l = m
        else:
            r = m
    return l

for j in range(m):
    A = np.sort(A)
    b, c = map(int, input().split())
    cnt = binary_search(A, c)
    A[0:min(b, cnt+1)] = c
    #print(A)

print(sum(A))



### FIXED CODE ###

# D - Integer Cards

import heapq
from collections import Counter

n, m = map(int, input().split())
A = list(int(x)*-1 for x in input().split())

C = Counter(A)
L = list(C.items())

for j in range(m):
    b, c = map(int, input().split())
    L.append((-c, b))

heapq.heapify(L)

ans = 0
for i in range(n):
    p, q = heapq.heappop(L)
    ans += p
    if q>1:
        heapq.heappush(L, (p, q-1))

print(ans*-1)
### BUGGY CODE ###

a = int(input())
num_list = list(map(int, input().split()))
for i in range(a):
    print(num_list.count(i+1))

### FIXED CODE ###


from collections import Counter
a = int(input())
num_list = list(map(int, input().split()))
D = Counter(num_list)
for i in range(a):
    print(D[i+1])
### BUGGY CODE ###

n=int(input())
l=sorted([int(i) for i in input().split()],reverse=True)

#print(l)
co=0
for i in range(n-2):
    c=l[i]
    x=0
    for j in range(i+1,n-1):
        b=l[j]
        for k in range(j+1,n):
            a=l[k]
            if c<(a+b):
                co+=1
            else:
                if k==j+1:
                    x=1
                break
        if x==1:
            break

print(co)

### FIXED CODE ###

import bisect

def solve():
    N = int(input())
    Ls = list(map(int, input().split()))
    Ls.sort()

    # O(N^2 * logN)の全探索で解く
    ans = 0
    for a_i in range(N):
        for b_i in range(a_i+1, N):
            c_i = bisect.bisect_left(Ls, Ls[a_i]+Ls[b_i])
            if c_i > b_i:
                ans += c_i - b_i - 1
            else:
                pass

    print(ans)

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

def main():
    n,m,k = map(int,input().split())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    ma = 0
    a2 = [0]
    b2 = [0]
    for i in range(len(a)):
        a2.append(a[i]+a2[i])
    for i in range(len(b)):
        b2.append(b[i]+b2[i])
    jj = len(b2)-1
    for i in range(len(a2)):
        cnt = i
        if(a2[i]>k):
            break
        j = jj
        while((a2[i]+b2[j])>k):
            j -= 1
        ma = max(ma,i+j)


    print(ma)
            
main()

### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

from copy import copy
import random
import math
import sys
input = sys.stdin.readline
D = int(input())
c = list(map(int,input().split()))
s = [list(map(int,input().split())) for _ in range(D)]
last = [0]*26
ans = [0]*D
score = 0
for i in range(D):
    ps = [0]*26
    for j in range(26):
        pl = copy(last)
        pl[j] = i+1
        ps[j] += s[i][j]
        for k in range(26):
            ps[j] -= c[k]*(i+1-pl[k])
    idx = ps.index(max(ps))
    last[idx] = i+1
    ans[i] = idx+1
    score += max(ps)
for k in range(1,41001):
    na = copy(ans)
    x = random.randint(1,365)
    y = random.randint(1,365)
    if x == y:
        continue
    na[x-1],na[y-1] = na[y-1],na[x-1]
    last = [0]*26
    ns = 0
    for i in range(D):
        last[na[i]-1] = i+1
        ns += s[i][na[i]-1]
        for j in range(26):
            ns -= c[j]*(i+1-last[j])
    T = 300-(298*k/40000)
    p = pow(math.e,-abs(ns-score)/T)
    if ns > score or random.random() < p:
        ans = na
        score = ns
for a in ans:
    print(a)

### FIXED CODE ###

import random
for i in range(365):
  print(random.randint(1,26))
### BUGGY CODE ###

N,M,Q = map(int,input().split())
toshi = []
for i in range(M):
  toshi.append(tuple(map(int,input().split())))
query = []
for i in range(Q):
  query.append(tuple(map(int,input().split())))
grid = []
for i in range(N+1):
  grid.append([0]*(N+1))
for i in range(M):
  grid[toshi[i][1]][toshi[i][0]] += 1
for i in range(1,N+1):
  for j in range(1,N+1):
    grid[i][j] += grid[i][j-1]
for i in range(Q):
  ans = 0
  for j in range(query[i][1]-query[i][0]+1):
    ans += (grid[query[i][0]+j][query[i][1]]-grid[query[i][0]+j][query[i][0]-1])
  print(ans)

### FIXED CODE ###

N,M,Q = map(int,input().split())
toshi = []
for i in range(M):
  toshi.append(tuple(map(int,input().split())))
query = []
for i in range(Q):
  query.append(tuple(map(int,input().split())))
grid = []
for i in range(N+1):
  grid.append([0]*(N+1))
for i in range(M):
  grid[toshi[i][1]][toshi[i][0]] += 1
for i in range(1,N+1):
  for j in range(1,N+1):
    grid[i][j] += grid[i][j-1]
for i in range(Q):
  ans = 0
  for j in range(query[i][1]-query[i][0]+1):
    ans += (grid[query[i][0]+j][query[i][1]]-grid[query[i][0]+j][query[i][0]-1])
  print(ans)
### BUGGY CODE ###

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

l1 = [1]*N
for i in range(1, N):
    l1[i] = (l1[i-1]*i)%MOD

va, vb = 0, 1
ans = 0

for i in range(N-1):
    d = x[i+1]-x[i]
    va = (i+1)*va+vb
    vb = (i+1)*vb
    ans += (d*va*pow(vb, MOD-2, MOD)*l1[N-1])
    ans %= MOD


print(ans)


### FIXED CODE ###

from fractions import gcd


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

m = 1
for i in range(1, N):
    m *= i
    m %= MOD

va, vb = 0, 1
ans = 0

for i in range(N-1):
    d = x[i+1]-x[i]
    va = ((i+1)*va+vb)%MOD
    vb = ((i+1)*vb)%MOD
    ans += (d*va*pow(vb, MOD-2, MOD)*m)
    ans %= MOD

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

import copy
N, W = map(int, input().split())

WV = [map(int,input().split()) for _ in range(N) ]


#dp[w] = max cost
costs = [-1 for _ in range(W + 1)]
costs[0] = 0

for w, v in WV:
    for index in reversed(range(W + 1)):
        if costs[index] == -1:
            continue
        if index + w > W:
            continue
        costs[index + w] = max(costs[index] + v, costs[index + w])


print(max(costs))



### FIXED CODE ###

N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]

max_weight = W + 1
max_cost = sum([v for w,v in WV])
dp = [max_weight for _ in range(max_cost + 1)]
# dp[cost] weight
dp[0] = 0

for w,v in WV:
    for index in reversed(range(len(dp))):
        if dp[index] == max_weight:
            continue

        dp[index + v] = min(dp[index + v], dp[index] + w)


for cost in reversed(range(max_cost + 1)):
    if dp[cost]<=W:
        print(cost)
        break
### BUGGY CODE ###

h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=input()
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      que.append([i,j,0])
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if seen[y][x]==-1:
    seen[y][x]=p
  else:
    continue
  ans=p
  if y-1>=0 and seen[y-1][x]==-1:
    que.append([y-1,x,p+1])
  if y+1<h and seen[y+1][x]==-1:
    que.append([y+1,x,p+1])
  if x-1>=0 and seen[y][x-1]==-1:
    que.append([y,x-1,p+1])
  if x+1<w and seen[y][x+1]==-1:
    que.append([y,x+1,p+1])
print(ans)


### FIXED CODE ###

H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i,j]=0

for i in range(0,W-1):
  np.minimum(a[:,i]+1,a[:,i+1],out=a[:,i+1])
for i in range(W-1,0,-1):
  np.minimum(a[:,i]+1,a[:,i-1],out=a[:,i-1])
for j in range(0,H-1):
  np.minimum(a[j,]+1,a[j+1,],out=a[j+1,])
for j in range(H-1,0,-1):
  np.minimum(a[j,]+1,a[j-1,],out=a[j-1,])

print(a.max())
### BUGGY CODE ###

a = int(input())
d = e = 0
for i in range(a):
    b, c = map(int, input().split())
    if i == 0:
        d = b
        e = c
    else:
        f = b
        g = c
        while True:
            if d <= f and e <= g:
                d = f
                e = g
                break
            else:
                f += b
                g += c
print(d + e)


### FIXED CODE ###

a = int(input())
b = [list(map(int, input().split()))for _ in range(a)]
c = []
for i in range(len(b)):
    c.append(b[i].copy())
    if len(c) != 1:
        while True:
            if c[i][0] < c[i-1][0] or c[i][1] < c[i-1][1]:
                c[i][0] = b[i][0] * max((c[i-1][0] + b[i][0] - 1) // b[i][0], (c[i-1][1] + b[i][1] - 1) // b[i][1])
                c[i][1] = b[i][1] * max((c[i-1][0] + b[i][0] - 1) // b[i][0], (c[i-1][1] + b[i][1] - 1) // b[i][1])
            else:
                break
print(c[len(c)-1][0] + c[len(c)-1][1])
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0

import math
import bisect
import collections
from collections import deque
c = collections.Counter(li)
li = list(set(li))
li.sort()
li = deque(li)
while len(li)>0:
    ba = li.pop()
    if c[ba]>1:
        continue
    #s_ba = math.ceil(math.sqrt(ba))+1
    #index = bisect.bisect_right(li, s_ba)
    tmp_li = li
    #print(ba,tmp_li)
    for tt in tmp_li:
        if ba%tt == 0:
            break
    else:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0
cnt_li = [0]*(10**6+1)

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()

for l in li:
    for x in range(2,10**7):
        if x*l > (10**6):
            break
        else:
            cnt_li[x*l] += 1


while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    if cnt_li[ba] == 0:
        ans += 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)

childs = [[] for _ in range(n)]
def dfs(p, v):
    val = 1
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv)
        val += ret
        childs[v].append(ret)
    if val != n:
        childs[v].append(n - val)
    return val

dfs(-1, 0)
total_pattern = pow(2, n, MOD)
total_pattern_inv = pow(total_pattern, MOD-2, MOD)
inv2 = pow(2, MOD-2, MOD)
ans = 0
for line in childs:
    pattern_ok = 0
    if len(line) == 1:
        continue
    for item in line:
        pattern_ok += pow(2, item, MOD) - 1
    pattern_ok += 1
    ans += (total_pattern * inv2 - pattern_ok) * total_pattern_inv
    ans %= MOD
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)

childs = [[] for _ in range(n)]
def dfs(p, v):
    val = 1
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv)
        val += ret
        childs[v].append(ret)
    if val != n:
        childs[v].append(n - val)
    return val

dfs(-1, 0)
total_pattern = pow(2, n, MOD)
total_pattern_inv = pow(total_pattern, MOD-2, MOD)
inv2 = pow(2, MOD-2, MOD)
pow2_table = [1]
for i in range(2 * 10**5):
    pow2_table.append(pow2_table[-1] * 2 % MOD)
ans = 0
for line in childs:
    pattern_ok = 0
    if len(line) == 1:
        continue
    for item in line:
        pattern_ok += pow2_table[item] - 1
    pattern_ok += 1
    ans += (total_pattern * inv2 - pattern_ok) * total_pattern_inv
    ans %= MOD
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
par = [-1 for _ in range(n)]

def dfs1(x, p):
	for v in adj[x]:
		if v != p:
			par[v] = x
			dfs1(v, x)
	return

dfs1(0, -1)

queries = [0 for _ in range(n)]
for _ in range(q):
	p, x = map(int, input().split())
	queries[p-1] += x

ans = [0 for _ in range(n)]

def dfs2(x, c):
	ans[x] = c + queries[x]
	for v in adj[x]:
		if v != par[x]:
			dfs2(v, ans[x])
	return

dfs2(0, 0)

print(*ans)

### FIXED CODE ###

import sys
#sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

queries = [0 for _ in range(n)]
for _ in range(q):
	p, x = map(int, input().split())
	queries[p-1] += x

ans = [0 for _ in range(n)]

st = [(0, 0, -1)]
while st:
	l = st.pop()
	ans[l[0]] = l[1] + queries[l[0]]
	for v in adj[l[0]]:
		if v != l[2]:
			st.append((v, ans[l[0]], l[0]))

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

n = int(input())
#ビット全探索を行う
import itertools
li = list(itertools.product([0, 1], repeat=n)) # ０が不親切もの、１が親切もの

#dd[i]:人iが人xをy（０なら不親切,１なら親切)だと思っていることを収納
from collections import deque, defaultdict
dd = defaultdict(lambda:deque())
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        dd[i].append((x-1, y))


from copy import deepcopy
max_sum = 0 #親切者の数の最大値
for i in li: # i には親切者のタプルが入っている
    ppp = 0
    for ggg in i:
        ppp += ggg
    if ppp <= max_sum:
        continue
    sum_ = 0
    co = deepcopy(dd)
    vv = 0
    for k in range(len(i)): #全員の証言が矛盾しないかを考える
        if i[k] == 0: # 不親切ものの場合
            continue
        else: #以下k人目の証言を考える
            sum_ += 1
            length = len(co[k])
            c = 0
            while co[k]:
                x, y = co[k].popleft()
                if i[x] != y: #証言と一致していない場合
                    break
                else:
                    c+=1
            if c == length: #k人目の証言が全てあっている場合
                vv += 1
    if vv == sum_:
        max_sum = max(max_sum, vv)

print(max_sum)
            


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    #ビット全探索を行う
    import itertools
    li = list(itertools.product([0, 1], repeat=n)) # ０が不親切もの、１が親切もの

    #dd[i][x] = y:人iが人xをy（０なら不親切,１なら親切)だと思っていることを収納
    NIL = -1
    dd = [[NIL]*n for _ in range(n)]
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = map(int, input().split())
            x = x-1
            dd[i][x] = y


    from copy import deepcopy
    max_sum = 0 #親切者の数の最大値
    for i in li: # i には親切者のタプルが入っている
        ppp = 0
        for ggg in i:
            ppp += ggg
        if ppp <= max_sum:
            continue
        sum_ = 0
        flag = True
        for k in range(len(i)): #全員の証言が矛盾しないかを考える
            if i[k] == 0: # 不親切ものの場合
                continue
            else: #以下k人目の証言を考える
                sum_ += 1
                for l in range(n):
                    if dd[k][l] != NIL and dd[k][l] != i[l]: #証言と一致していない場合
                        flag = False
                        break
        if flag:
            max_sum = max(max_sum, sum_)

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

import sys
input = sys.stdin.readline
from itertools import accumulate

def main():
  
  def merge(i, j):
    if dp1[i] >= A[j]:
      dp2[i] = max(dp2[i], A[j])
    else:
      dp2[i] = dp1[i]
      dp1[i] = A[j]
  n = int(input())
  A = tuple(map(int, input().split()))
  dp1 = [0]*(1<<n)
  dp2 = [0]*(1<<n)
  for i in range(1<<n):
    j = i
    while j>0:
      merge(i, j)
      j = (j-1)&i
    merge(i, 0)
  L = list(accumulate([a+b for a, b in zip(dp1, dp2)], max))
  print(*L[1:], sep="\n")

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from itertools import accumulate

def merge(x, y):
  D = sorted([dp[x][0], dp[x][1], dp[y][0], dp[y][1]], reverse=True)
  return (D[0], D[1])
  
n = int(input())
A = tuple(map(int, input().split()))
dp = [(a, 0) for a in A]
for j in range(n):
  for i in range(1<<n):
    if i & (1<<j):
      dp[i] = merge(i, i & ~(1<<j))
L = tuple(accumulate((sum(d) for d in dp), max))
print(*L[1:], sep="\n")
### BUGGY CODE ###


H, W, D = map(int, input().split())

coord_dict_x = [0 for i in range(90002)]
coord_dict_y = [0 for i in range(90002)]

for i in range(H):
    gyo = [int(i) for i in input().split()]
    for j in range(W):
        coord_dict_x[gyo[j]] = i
        coord_dict_y[gyo[j]] = j

Q = int(input())
exam = [[int(i) for i in input().split()] for i in range(Q)]

for i in range(Q):
    reduce_MP = 0
    num = exam[i][0]
    coord1_x = coord_dict_x[num]
    coord1_y = coord_dict_y[num]
    while num < exam[i][1]:
        num += D
        coord2_x = coord_dict_x[num]
        coord2_y = coord_dict_y[num]
        reduce_MP += abs(coord1_x - coord2_x) + abs(coord1_y - coord2_y)
        coord1_x, coord1_y = coord2_x, coord2_y
    print(reduce_MP)



### FIXED CODE ###

H, W, D = list(map(int, input().split()))

Amap = []
for i in range(H):
    Amap.append(list(map(int, input().split())))

xx = [0 for i in range(90002)]
yy = [0 for i in range(90002)]
for y in range(H):
    for x in range(W):
        xx[Amap[y][x]] = x
        yy[Amap[y][x]] = y
Q = int(input())

coord = []
for i in range(Q):
    coord.append(list(map(int, input().split())))

# magic point calculation
mp = [0 for i in range(90002)]

for i in range(D+1, 90002):
    mp[i] = mp[i-D] + abs(xx[i] -xx[i-D]) + abs(yy[i] - yy[i-D])

for i in coord:
    print(mp[i[1]] - mp[i[0]])
### BUGGY CODE ###

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
bc=[]
d=[]

for _ in range(m):
    b,c=map(int,input().split())
    bc.append((b,c))
bc=sorted(bc,key=lambda x:x[1],reverse=True)
for i in range(m):
    for _ in range(int(bc[i][0])):
    	d.append(bc[i][1])
    
right=sum(a)
left=0

for i in range(min(n,len(d))):
    if a[i]<d[i]:
        left+=d[i]
        right-=a[i]
    else:
        break
print(right+left)

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
arr=[]

for i in range(m):
    b,c=map(int,input().split())
    arr.append((b,c))

a=sorted(a)
arr=sorted(arr,key=lambda x:-x[1])

flag=0
left=0
for tup in arr:
    for i in range(left,min(left+tup[0],n)):
        if tup[1]>a[i]:
            a[i]=tup[1]
        else:
            flag=-1
            break
        if i==n-1:
            flag=-1
            break
    left+=tup[0]
    if flag==-1:
        break

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

import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

#実際に書き込む
N = ri()
S = [rs() for _ in range(N)]
answer = 0
a = 0
for b in range(N):
    bool = True
    for i in range(N):
        for j in range(i+1, N):
            y1 = (i+a)%(N)
            x1 = (j+b)%(N)
            y2 = (j+a)%(N)
            x2 = (i+b)%(N)
            
            if S[y1][x1] != S[y2][x2]:
                
                bool = False
                break
        else:
            continue
        break
    else:
        if bool:
            #print(a, b, i, j, y1, x1, y2, x2)
            answer += 1
answer *= N
print(answer)

#16



### FIXED CODE ###

import sys
import numpy as np

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip() # ignore trailing spaces

N = ri()
S = np.array([list(rs()) for _ in range(N)])

S = np.concatenate([S, S], axis=0)
answer = 0
for b in range(N):
    S2 = S[b:b+N]
    if (S2 == S2.T).all():
        answer += N

print(answer)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(1, n):
    ans.append(abs(sum(a[0:i]) - sum(a[i:n])))
print(min(ans))

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
m = sum(a[:1])
n = sum(a[1:])
ans = [abs(m-n)]
for i in range(1, N-1):
    m += a[i]
    n -= a[i]
    ans.append(abs(m-n))
print(min(ans))
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
white=0
s=[]
for y in range(H):
    line=input()
    white+=line.count('.')
    s.append(list(line))

q = deque([(0,0,1)])
q_append=q.append
q_popleft=q.popleft
while q:
    x,y,l=q_popleft()
    if s[y][x]!='.':
        continue
    if x==W-1 and y==H-1:
        print(white-l)
        break
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx, ny=(x+d[0],y+d[1])
        if 0<=nx<W and 0<=ny<H:
            q_append((nx,ny,l+1))
else:
    print(-1)

### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
white=0
s=[]
for y in range(H):
    line=input()
    white+=line.count('.')
    s.append(list(line))

q = deque([(0,0,1)])
q_append=q.append
q_popleft=q.popleft
while q:
    x,y,l=q_popleft()
    if s[y][x]!='.':
        continue
    if x==W-1 and y==H-1:
        print(white-l)
        break
    s[y][x]='*'
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx, ny=(x+d[0],y+d[1])
        if 0<=nx<W and 0<=ny<H:
            q_append((nx,ny,l+1))
else:
    print(-1)