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

R, C, k = (int(x) for x in input().split())
RCV = [tuple(int(x) for x in input().split()) for _ in range(k)]
V = [[0] * (C + 5) for _ in range(R + 5)]
for r, c, v in RCV:
    V[r][c] = v
# dp[i][j][3]
dp = [[[0] * 4 for _ in range(C + 5)] for _ in range(R + 5)]
for i in range(1, R + 3):
    for j in range(1, C + 3):
        for k in range(4):
            # 行移動
            dp[i][j][0] = max(dp[i][j][0], max(dp[i-1][j]))
            dp[i][j][1] = max(dp[i][j][1], max(dp[i-1][j])+V[i][j])
            # 列移動
            if k > 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k - 1] + V[i][j])
            dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
print(max(dp[R][C]))


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[3][i][j]
dp = [[[0] * (C + 5) for _ in range(R + 5)] for _ in range(4)]
for i in range(R + 3):
    for j in range(C + 3):
        for k in range(4):
            # 行移動
            dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
            dp[1][i + 1][j] = max(dp[1][i + 1][j], dp[k][i][j] + V[i + 1][j])
            # 列移動
            dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
            if k < 3:
                dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], dp[k][i][j] + V[i][j + 1])
print(max(dp[k][R][C] for k in range(4)))
### BUGGY CODE ###

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

for line in range(M):
    change_count, change_number = map(int, input().split())
    in_hand.sort()
    for i in range(change_count):
        if in_hand[i] < change_number:
            in_hand[i] = change_number
        else:
            break

print(sum(in_hand))

### FIXED CODE ###

from operator import itemgetter

N, M = map(int, input().split())
in_hand = list(map(int, input().split()))
in_hand.sort()

change_list = []

for line in range(M):
    change_count, change_number = map(int, input().split())

    change_list.append([change_count, change_number])


change_list.sort(key=itemgetter(1), reverse=True)

index = 0
try:
    for change in change_list:
        for i in range(change[0]):
            if in_hand[i+index] < change[1]:
                in_hand[i+index] = change[1]
            else:
                break
        else:
            index += change[0]
            continue
        break
except:
    pass

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

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

ans = []
for i in range(n):
  
  save = s[i]
  s[i] = 'x'
  count = 0
  j = 0
  while j < n:  
    if s[j] == 'o':
      count += 1
      j += c+1
    else:
      j += 1  
      
  if count < k:
    ans.append(i+1) 
    
  s[i] = save
  
for a in ans:
  print(a)

### FIXED CODE ###

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

L = []
R = []

i = -1
j = n  

for ki in range(k):
  while i < n:
    i += 1
    if s[i] == 'o':           
      L += [i]
      i += c
      break

for ki in range(k):      
  while 0 <= j:
    j -= 1
    if s[j] == 'o':          
      R += [j]
      j -= c
      break
      
for i in range(k):
  if L[i] == R[-i-1] :
    print(L[i]+1)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

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

# dp[i][j] = 元の数列の中の連続する区間i～jに対して、最終局面に行った時のX-Yの最大値

dp = [[0] * (N + 1) for i in range(N + 1)]
  
for length in range(1, N + 1):
  for i in range(N - length + 1):
    j = i + length
    
    if (N - length) % 2 == 0: # 先手番
      dp[i][j] = max(dp[i + 1][j] + A[i], dp[i][j - 1] + A[j - 1])
      
    else: # 後手番
      dp[i][j] = min(dp[i + 1][j] - A[i], dp[i][j - 1] - A[j - 1])

print(dp[0][N]) 

### FIXED CODE ###

import sys
readline = sys.stdin.readline

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

# dp[i][j] = 元の数列の中の連続する区間i～jに対して、最終局面に行った時のX-Yの最大値

dp = [[0] * (N + 1) for i in range(N + 1)]
  
for length in range(1, N + 1):
  for i in range(N - length + 1):
    j = i + length
    
    if (N - length) % 2 == 0: # 先手番
      dp[i][j] = max(dp[i + 1][j] + A[i], dp[i][j - 1] + A[j - 1])
      
    else: # 後手番
      dp[i][j] = min(dp[i + 1][j] - A[i], dp[i][j - 1] - A[j - 1])

print(dp[0][N])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
l=[]
dx=0
for i in A:
    l.append(i)
    if i==max(l):
        dx+=0
    else:
        dx+=(max(l)-i)
print(dx)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
x=0
dx=0
for i in A:
    if i>x:
        x=i
    else:
        dx+=(x-i)
print(dx)
### BUGGY CODE ###


import sys

N, M = map(int, input().split())
uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
S, T = map(lambda x:int(x)-1, input().split())

roots = [[] for _ in range(N)]

for uv in uvs:
    roots[uv[0]].append(uv[1])

costs = [-10000 for _ in range(N)]

from collections import deque

todo = deque([S])
costs[S] = 0

count = 0
while len(todo)>0:
    count+=1
    if count > M :
        break
    checking = todo.popleft()
    next_targets = deque([checking])
    for i in range(3):
        purposes = set()
        while len(next_targets) > 0:
            now = next_targets.pop()
            for root in roots[now]:
                purposes.add(root)
        next_targets = deque(purposes)
    for next_target in next_targets:
        if costs[next_target] < 0:
            costs[next_target] = costs[checking]+1
            todo.append(next_target)
        if next_target == T:
            print(costs[next_target])
            sys.exit()
print(-1)

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys
import copy
def func():
    N, M = map(int, input().split())
    uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
    S, T = map(lambda x:int(x)-1, input().split())
    
    roots = [[] for _ in range(N)]
    
    for uv in uvs:
        roots[uv[0]].append(uv[1])
    
    costs = [-10000]*(N)
    
    from collections import deque
    
    todo = deque([S])
    costs[S] = 0
    todo_set = set([S])
    
    layers = [set() for _ in range(3)]
    
    while len(todo)>0:
        checking = todo.popleft()
        next_targets = deque([checking])
        for i in range(3):
            purposes = set()
            while len(next_targets) > 0:
                now = next_targets.pop()
                for root in roots[now]:
                    if root not in layers[i]:
                        layers[i].add(root)
                        purposes.add(root)
            next_targets = purposes.copy()
        for next_target in next_targets:
            if costs[next_target] < 0 and next_target not in todo_set:
                costs[next_target] = costs[checking]+1
                todo.append(next_target)
                todo_set.add(next_target)
                if next_target == T:
                    print(costs[next_target])
                    sys.exit()
    print(-1)
if __name__ == "__main__":
    func()
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def calc_depth(tree, i):
    for j in tree[i][2:]:
        tree[j][0] += 1
        calc_depth(tree, j)


n = int(stdin.readline())
tree = [0] * n
#assert 1 <= n <= 100000
for _ in range(n):
    node = [int(s) for s in stdin.readline().split()]
    tree[node[0]] = [0] + node[1:]

for i in range(n):
    calc_depth(tree, i)

fmt = 'node {}: parent = {}, depth = {}, {}, {}'.format
for i, node in enumerate(tree):
    pa = -1
    for j, n in enumerate(tree):
        if i in n[2:]:
            pa = j
            break
    if pa == -1:
        kind = 'root'
    elif not node[1]:
        kind = 'leaf'
    else:
        kind = 'internal node'
    print(fmt(i, pa, node[0], kind, node[2:]))

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin

FORMAT = ('node {0.id}: parent = {0.parent}, depth = {0.depth},'
          ' {0.kind}, {0.childs}').format


class Node(object):
    def __init__(self, node):
        self.depth = 0
        self.parent = -1
        self.id = node[0]
        self.degree = node[1]
        self.kind = 'internal node' if node[1] else 'leaf'
        self.childs = node[2:]

    def __str__(self):
        return FORMAT(self)


def calc_depth(tree, i):
    for j in tree[i].childs:
        tree[j].depth += 1
        calc_depth(tree, j)


n = int(stdin.readline())
tree = [-1] * n
#assert 1 <= n <= 100000
for _ in range(n):
    node = Node([int(s) for s in stdin.readline().split()])
    i = node.id
    node.parent = tree[i]
    for j in node.childs:
        if isinstance(tree[j], int):
            tree[j] = i
        else:
            tree[j].parent = i
    tree[i] = node

for i in range(n):
    calc_depth(tree, i)

for i, node in enumerate(tree):
    if node.parent == -1:
        node.kind = 'root'
    print(node)
### BUGGY CODE ###

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

p = []
m = []
for i in range(n):
    a[i] -= i+1
    if a[i] > 0:
        p += [a[i]]
    elif a[i] < 0:
        m += [a[i]]

if sum(p) == abs(sum(m)):
    print(sum([abs(i) for i in a]))
    exit()

pre = sum([abs(i) for i in a])
if sum(p) > abs(sum(m)):
    while True:
        for i in range(n):
            a[i] -= 1
        total = sum([abs(i) for i in a])
        
        if total >= pre:
            print(pre)
            exit()
        pre = total
else:
    while True:
        for i in range(n):
            a[i] += 1
        total = sum([abs(i) for i in a])
        
        if total >= pre:
            print(pre)
            exit()
        pre = total

### FIXED CODE ###

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

for i in range(n):
    a[i] -= i+1
a.sort()

ans = 0
for i in range(n):
    ans += abs(a[i] - a[n//2])
print(ans)
### BUGGY CODE ###

import sys
from functools import lru_cache

sys.setrecursionlimit(10**6)

n = int(input())
graph = [list() for _ in range(n**2)]

id_index = [[i+j*n for i in range(n)] for j in range(n)]
index_list = []

max_length = 0

def toId(p, o):
    if p > o:
        index = id_index[o][p]
        index_list.append(index)
        return index
    else: return id_index[p][o]

@lru_cache(maxsize=None)
def dfs(id, length):
    global max_length
    next_list = graph[id]

    if length > len(index_list):
        print(-1)
        sys.exit()

    if len(next_list) == 0:
        max_length = max(length, max_length)
        return
    
    for next in next_list:
        dfs(next, length+1)

for p in range(n):
    a = [toId(p, int(x)-1) for x in input().split()]
    for i in range(n-2):
        graph[a[i]].append(a[i+1])

for id in index_list:
    dfs(id, 1)

print(max_length)

### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
graph = [list() for _ in range(n**2)]

id_index = [[i+j*n for i in range(n)] for j in range(n)]
index_list = []

def toId(p, o):
    if p > o:
        index = id_index[o][p]
        index_list.append(index)
        return index
    else: return id_index[p][o]

v_len = [-1 for _ in range(n)] * n
finished = [False for _ in range(n)] * n

def dfs(id):
    next_list = graph[id]

    if v_len[id] != -1:
        if not finished[id]:
            print(-1)
            sys.exit()
        return v_len[id]

    v_len[id] = 1

    for next in next_list:
        v_len[id] = max(v_len[id], dfs(next)+1)

    finished[id] = True
    return v_len[id]

for p in range(n):
    a = [toId(p, int(x)-1) for x in input().split()]
    for i in range(n-2):
        graph[a[i]].append(a[i+1])
    
ans = 0

for id in index_list:
    ans = max(dfs(id), ans)

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

N,X,Y = map(int, input().split())
ans = [0]*(N-1)
for i in range(1,N):
  for j in range(1,N+1-i):
    a, b = j,j+i
    c = min([abs(a-b), abs(X-a)+abs(Y-b)+1, abs(Y-a)+abs(X-b)+1])
    ans[c-1] += 1
print("\n".join([str(i) for i in ans]))

### FIXED CODE ###

from itertools import combinations
N,X,Y = map(int, input().split())
ans = [0]*(N-1)
for a,b in combinations(range(N),2):
  c = min([abs(a-b), abs(X-1-a)+abs(Y-1-b)+1, abs(Y-1-a)+abs(X-1-b)+1])
  ans[c-1] += 1
for i in ans: print(i)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
keisu = [0]*n

for i in range(n):
    for j in range(i+1,n):
        keisu[j] += a[i]


for i in range(n):
    ans += a[i] * keisu[i]

        
        

print(ans%(1000000000+7))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
keisu = [0]*n
t = 0

for i in range(n):
    
    keisu[i] += t
    t += a[i]


for i in range(n):
    ans += a[i] * keisu[i]

        
        

print(ans%(1000000000+7))
### BUGGY CODE ###

import heapq
from collections import defaultdict

N,m,s,t=map(int,input().split())

V=defaultdict(set)
V2=defaultdict(set)
for i in range(m):
  a,b,c,d=map(int,input().split())
  V[a-1].add((b-1,c))
  V[b-1].add((a-1,c))
  V2[a-1].add((b-1,d))
  V2[b-1].add((a-1,d))

def dijkstra(n,v,dedic):
  d=[float('inf')]*n
  d[v]=0
  
  hq=[(0,v)]
  
  while hq:
    u = heapq.heappop(hq)[1]
    for nv,c in dedic[u]:
      if d[nv]>d[u]+c:
        d[nv]=d[u]+c
        heapq.heappush(hq,(d[u]+c,nv))
        
  return d

ans=dijkstra(N,s-1,V)
ans2=dijkstra(N,t-1,V2)

ans3=[(ans[x]+ans2[x]) for x in range(N)]

for i in range(N):
  print(10**15-min(ans3[i:]))

### FIXED CODE ###

import heapq
from collections import defaultdict

N,m,s,t=map(int,input().split())

V=defaultdict(set)
V2=defaultdict(set)
for i in range(m):
  a,b,c,d=map(int,input().split())
  V[a-1].add((b-1,c))
  V[b-1].add((a-1,c))
  V2[a-1].add((b-1,d))
  V2[b-1].add((a-1,d))

def dijkstra(n,v,dedic):
  d=[float('inf')]*n
  d[v]=0
  
  hq=[(0,v)]
  
  while hq:
    u = heapq.heappop(hq)[1]
    for nv,c in dedic[u]:
      if d[nv]>d[u]+c:
        d[nv]=d[u]+c
        heapq.heappush(hq,(d[u]+c,nv))
        
  return d

ans=dijkstra(N,s-1,V)
ans2=dijkstra(N,t-1,V2)
ans3=[10**15 for i in range(N)]
ans3[N-1]=ans[N-1]+ans2[N-1]
for i in range(N-2,-1,-1):
  ans3[i]=min(ans3[i],ans3[i+1],ans[i]+ans2[i])

for i in range(N):
  print(10**15-ans3[i])
### BUGGY CODE ###

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

cnt=[0]*100
p=10**9+7
for m in a:
    b=bin(m)
    l=len(b)-2
    #print(b)
    for i in range(l):
        cnt[i]+=int(b[-i-1])
    #kei=m
    #for i in range(100):
    #    cnt[i]+=kei%2
    #    kei//=2
    #    if(kei==0):
    #        break

#print(cnt)

lis=[]
jou=1
for i in range(100):
    lis.append(jou)
    jou*=2
    jou%=p

ans=0

for i in range(100):
    ans+=(lis[i]%p)*(cnt[i]%p)*((n-cnt[i])%p)
    ans%=p

print(ans)

### FIXED CODE ###

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

cnt=[0]*60
p=10**9+7
for m in a:
    #b=bin(m)
    #l=len(b)-2
    #print(b)
    for i in range(60):
        if((m>>i) & 1):
            cnt[i]+=1
    #for i in range(l):
    #    cnt[i]+=int(b[-i-1])
    #kei=m
    #for i in range(100):
    #    cnt[i]+=kei%2
    #    kei//=2
    #    if(kei==0):
    #        break

#print(cnt)

lis=[]
jou=1
for i in range(60):
    lis.append(jou)
    jou*=2
    jou%=p

ans=0

for i in range(60):
    ans+=(lis[i]%p)*(cnt[i]%p)*((n-cnt[i])%p)
    ans%=p

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

n = int(input())
l = list(map(int, input().split()))
check = True
for i in range(n):
    if l.count(l[i]) > 1:
        check = False
        break
if check:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

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

import itertools
N = int(input())
L = list(map(int, input().split()))
S = 0
for c in itertools.combinations(L, 2):
  S += (c[0] * c[1]) % (10 ** 9+7)
print(S % (10 ** 9+7))

### FIXED CODE ###

k = 10 ** 9 + 7
N = int(input())
L = list(map(int, input().split()))
S = sum(L) ** 2
for i in L:
  S -= i ** 2

print( (S // 2) % k)
### BUGGY CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


H,W = map(int, input().split())
Sn = [["#" for j in range(W+2)] for i in range(H+2)]
num_w = 0
for i in range(H):
  h = list(str(input()))
  Sn[i+1] = ["#"] + h + ["#"]
  num_w += h.count(".")

Cn = [[sys.maxsize for j in range(W+2)] for i in range(H+2)]
Cn[1][1] = 0
while(Cn[H][W] == sys.maxsize):
  for i in range(H):
    for j in range(W):
      if Sn[i+1][j+1] == "#":
        continue
      else:
        Cn[i+1][j+1] = min(Cn[i+1][j+1],Cn[i+2][j+1]+1,Cn[i+1][j+2]+1,Cn[i][j+1]+1,Cn[i+1][j]+1)

print(num_w - Cn[H][W] - 1)







### FIXED CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


H,W = map(int, input().split())
num_w = -1
srch = []
for i in range(H):
  h = list(str(sys.stdin.readline().rstrip()))
  for j in range(W):
    if h[j] == ".":
      srch.append([i+1,j+1])
      num_w += 1

Cn = [[sys.maxsize for j in range(W+2)] for i in range(H+2)]
Cn[1][1] = 0
for _ in range(num_w):
  for i,j in srch[1:]:
    Cn[i][j] = min(Cn[i-1][j],Cn[i][j-1],Cn[i+1][j],Cn[i][j+1])+1

if Cn[H][W] < sys.maxsize:
  print(num_w - Cn[H][W])
else:
  print(-1)
### BUGGY CODE ###

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

s = set()
for i in range(n):
    pow, cur = 0, a[i]
    while cur % 2 == 0:
        cur //= 2
        pow += 1
    s.add(pow)
if (len(s) > 1):
    print(0)
else:
    l = a[0] // 2
    for i in range(1, n):
        l = lcm(l, a[i] // 2)
    res, cur = 0, l
    while cur <= m:
        res += 1
        cur += 2 * l
    print(res)

### FIXED CODE ###

from fractions import gcd
n, m = map(int, input().split())
a = [int(i) // 2 for i in input().split()]

def pow2(n):
    cur, res = n, 0
    while cur:
        if cur % 2 == 0:
            cur //= 2
            res += 1
        else:
            return res

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

b = [pow2(i) for i in a]
if (min(b) != max(b)):
    print(0)
    exit(0)
l = 1
for i in range(n):
    l = lcm(l, a[i])
print(m // l - m // (2 * l))
### BUGGY CODE ###

n=int(input())
A=list(int(i) for i in input().split())
dp=[[[0,0] for i in range(n)] for j in range(n)]
for i in range(n-1,-1,-1):
    for j in range(n):
        if i<=j:
            if i==j:
                dp[i][j][0]=A[i]
                dp[i][j][1]=-A[i]
            else:
                dp[i][j][0]=max(A[i]+dp[i+1][j][1],A[j]+dp[i][j-1][1])
                dp[i][j][1]=min(-A[i]+dp[i+1][j][0],-A[j]+dp[i][j-1][0])
print(dp[0][-1][0])


### FIXED CODE ###

#dp=[[ for i in range(3000)] for j in range(3000)]
n=int(input())
A=list(int(i) for i in input().split())
dp=[[0 for i in range(n)] for j in range(n)]
for i in range(n-1,-1,-1):
    for j in range(i,n):
        if i==j:
            dp[i][j]=A[i]
        else:
            dp[i][j]=max(A[i]-dp[i+1][j],A[j]-dp[i][j-1])
print(dp[0][-1])
### BUGGY CODE ###

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

maxx = max(xlist[-1], a)
# dp[j][k][s]: x_1...x_jまでのなかからk枚選んで合計をsにする総数
dp = [[[0 for _ in range(maxx * n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]

dp[0][0][0] = 1  # 0枚選んで合計を0にするのは1通り
for j in range(n + 1):
  for k in range(n + 1):
    for s in range(maxx * n + 1):
      if j >= 1:  # x_0は選ばないのと同じなので0のまま更新しない
        if s < xlist[j-1]:
          dp[j][k][s] = dp[j-1][k][s]
        elif k >= 1 and s >= xlist[j-1]:
          dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-xlist[j-1]]

print(sum(dp[n][k][k*a] for k in range(1, n + 1)))

### FIXED CODE ###

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

maxx = max(x)
maxx = max(maxx, a)
# dp[j][k][s] : j枚目までからk枚選んで合計をsにする場合の数
dp = [[[0 for _ in range(maxx * n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for j in range(n + 1):
    for k in range(j + 1):
        for s in range(maxx * k + 1):
            if j >= 1 and s < x[j - 1]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif j >= 1 and k >= 1 and s >= x[j - 1]:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j - 1]]

ans = 0
for k in range(1, n + 1):
    ans += dp[n][k][k*a]
print(ans)
### BUGGY CODE ###

import sys
import heapq

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

    H = []

    for i in range(M):
        b, c = map(int, input().split())
        A += [c] * b
        
    for a in A:
        heapq.heappush(H, -a)

    ans = 0
    for i in range(N):
        ans -= heapq.heappop(H)

    print(ans)



if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, M = map(int, input().split())
    A = []
    for i in list(map(int, input().split())):
        A.append((i, 1))
    for i in range(M):
        b, c = map(int, input().split())
        A.append((c, b))

    A = sorted(A)
    # print(A)
    cnt = 1
    ans = 0
    while cnt <= N:
        b, c = A.pop()
        ans += b
        if c > 1:
            c -= 1
            A.append((b, c))
        cnt += 1
    print(ans)


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

n, m = map(int, input().split())
A = list(map(int, input().split()))
#A.sort()

B = [0]*n
for i in range(m):
    b, c = map(int, input().split())
    B += [c]*b

B.sort(reverse=True)
B = B[0:n]

import heapq
heapq.heapify(B)

for a in A:
    x = heapq.heappop(B)
    if a >= x:
        heapq.heappush(B, a)
    else:
        heapq.heappush(B, x)
print(sum(B))

### FIXED CODE ###

n, m = map(int, input().split())
l = list(map(int, input().split()))
l.sort()

bc = [list(map(int, input().split())) for i in range(m)]
bc = sorted(bc, key=lambda x: x[1], reverse=True)
count = 0

for i in range(m):
  b, c = bc[i][0], bc[i][1]
  l += [c]*b
  count += b
  if count >= n:
    break

l.sort(reverse=True)
print(sum(l[:n]))
### BUGGY CODE ###

n, m = list(map(int, input().split()))
edge = [[] for k in range(n)]
for k in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

start = 0

from collections import deque
que = deque([start])
done = {start}
depth = [1e9]  * n
depth[start] = 0
parents = [-1] * n
while True:
    if len(que) == 0:
        break
    now = que.popleft()
    dep = depth[now]
    for node in edge[now]:
        if node not in done:
            que.append(node)
            if dep < depth[node]:
                depth[node] = dep + 1
                parents[node] = now
    done.add(now)
#     print(now)
if max(depth) == 1e9:
    print("No")
else:
    print("Yes")
    for k in range(1, n):
        print(parents[k] + 1)

### FIXED CODE ###

n, m = list(map(int, input().split()))
edge = [[] for k in range(n)]
for k in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

start = 0

from collections import deque
que = deque([start])
done = {start}
depth = [1e9]  * n
depth[start] = 0
parents = [-1] * n
while True:
    if len(que) == 0:
        break
    now = que.popleft()
    dep = depth[now]
    
    for node in edge[now]:
        if node not in done:
#             if dep < depth[node]:
            depth[node] = dep + 1
            parents[node] = now
            que.append(node)
        done.add(node)
#     done.add(now)
#     print(now)
if max(depth) == 1e9:
    print("No")
else:
    print("Yes")
    for k in range(1, n):
        print(parents[k] + 1)