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

import sys
sys.setrecursionlimit(10**8)

N = int(input())
adj = [[] for _ in range(N+1)]
for e in range(1,N):
  a,b = map(int, input().split())
  adj[a].append((b,e))
  adj[b].append((a,e))

#print(adj)

col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,e):
  visited[v] = True
  #print(v,e,edge_color)
  col_lis = [i for i in range(1,col_num+1)]
  if e != 0:
    col_lis.remove(edge_color[e])
  for w,f in adj[v]:
    if visited[w]==False:
      #continue
    #if edge_color[e] == 0:
    #print(col_lis)
      edge_color[f] = col_lis.pop(0)
      dfs(w,f)
  return None
#print(col_num)
dfs(N-1,0)

print(col_num)
for i in range(1,N):
  print(edge_color[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

N = int(input())
adj = [[] for _ in range(N+1)]
for e in range(1,N):
  a,b = map(int, input().split())
  adj[a].append((b,e))
  adj[b].append((a,e))

#print(adj)

col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,c=-1):
  #print(v,e,edge_color)
  #col_lis = [i for i in range(1,col_num+1)]
  #if e >0:
    #col_lis.remove(edge_color[e])
  color = 1
  for w,f in adj[v]:
    if visited[w]==False:
      visited[v] = True
      if c==color: color+=1
      edge_color[f] = color
      dfs(w,color)
      color+=1

dfs(1)

print(col_num)
for i in range(1,N):
  print(edge_color[i])
### BUGGY CODE ###

N = int(input())
print(sum(range(N)))

### FIXED CODE ###

N = int(input())
ans = N * (N - 1) // 2
 
print(int(ans))
### BUGGY CODE ###

import math
X, K, L = map(int, input().split())
min_dist = math.inf
for p_num in range(K+1):
    dist = abs(X + L*p_num + (-1)*L*(K-p_num))
    if dist < min_dist:
        min_dist = dist

print(min_dist)


### FIXED CODE ###

X, K, D = map(int, input().split())

X = abs(X)

n = X // D
m = K - n

A1 = abs(X - n*D)
A2 = abs(X - (n+1)*D)

Ans = A2

if m > 1:
    if A1 <= A2:
        if m % 2 == 0:
            Ans = A1
    else:
        if m % 2 == 0:
            Ans = A1
else:
    Ans = abs(X - K*D)

print(Ans)
### BUGGY CODE ###

H=10800
D=H*8
d=[0]*D
c=0
exec("a,b=map(int,raw_input().split());c+=a;d[c%D]+=1;c+=b;"*input())
d*=2
r=range(D+H)
for i in r:d[i+1]+=d[i]
print max(d[i+H]-d[i]for i in r)

### FIXED CODE ###

H=10800
D=H*8
d=[0]*D
c=0
for i in[0]*input():a,b=map(int,raw_input().split());c+=a;d[c%D]+=1;c+=b
d*=2
r=range(D+H)
for i in r:d[i+1]+=d[i]
print max(d[i+H]-d[i-1]for i in r)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[False]*n
g=[[] for _ in [0]*n]
for _ in range(m):
    l,r,d=map(int,input().split())
    g[l-1].append((r-1,d))
    g[r-1].append((l-1,-d))
for i in range(n):
    if not(a[i]):
        a[i]=0
        q=[i]
    while q:
        j=q.pop()
        for x,e in g[j]:
            if not(a[x]):
                a[x]=a[j]+e
                q.append(x)
            elif a[x]!=a[j]+e:
                print("No")
                exit()
                
print("Yes")

### FIXED CODE ###

n,m=map(int,input().split())
a=[None]*n
g=[[] for _ in range(n)]
for _ in range(m):
    l,r,d=map(int,input().split())
    g[l-1].append((r-1,d))
    g[r-1].append((l-1,-d))
for i in range(n):
    if a[i]==None:
        a[i]=0
        q=[i]
    while q:
        j=q.pop()
        for x,e in g[j]:
            if a[x]==None:
                a[x]=a[j]+e
                q.append(x)
            elif a[x]!=a[j]+e:
                print("No")
                exit()
                
print("Yes")
### BUGGY CODE ###

from collections import deque

s = input()
d = deque(s)
n = int(input())
for _ in range(n):
    q = input().split()
    if (len(q)==1):
        d.reverse()
    else:
        a = int(q[1])
        b = q[2]
        if (a == 1):
            d.appendleft(b)
        else:
            d.append(b)
ans = list(d)
xxx = "".join(ans)
print(xxx)

### FIXED CODE ###

from collections import deque

s = input()
d = deque(s)
n = int(input())
flag = 0
for _ in range(n):
    q = input().split()
    if (len(q)==1):
        if(flag == 0):
            flag = 1
        else:
            flag = 0
    else:
        a = int(q[1])
        b = q[2]
        if (a == 1):
            if flag==0:
                d.appendleft(b)
            else:
                d.append(b)
        else:
            if flag==0:
                d.append(b)
            else:
                d.appendleft(b)

if flag==1:
    d.reverse()
ans = list(d)
xxx = "".join(ans)
print(xxx)
### BUGGY CODE ###

import sys
N, C, K = list(map(int, input().split()))
listT = [int(input()) for _ in range(N)]

listT.sort()

def func(listT,bus):
    if len(listT)==0:
        print(bus)
        sys.exit()
    elif len(listT)<C:
        for j in range(1, len(listT)):
            if listT[j]-listT[0]>K:
                bus += 1
                return func(listT[j:],bus)
        bus += 1
        print(bus)
        sys.exit()

    elif len(listT)>=C:
        for i in range(1,C):

            if listT[i]-listT[0]>K:
                bus += 1
                return func(listT[i:],bus)

        bus += 1
        return func(listT[C:],bus)

func(listT,0)


### FIXED CODE ###

import sys
N, C, K = list(map(int, input().split()))
listT = [int(input()) for _ in range(N)]

listT.sort(reverse = True)

count=0
while listT != []:
    bus =[]
    time = listT[0]
    count += 1
    while len(bus) != C and time - K <= listT[0]:
        bus.append(listT.pop(0))
        if listT ==[]:
            break

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

MOD = 10 ** 9 + 7

S = input()
N = len(S)

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

for i, s in enumerate(S):
    c = -1 if s == "?" else int(s)

    for j in range(10):
        if c != -1 and c != j:
            continue
        for r in range(13):
            dp[i + 1][(r * 10 + j) % 13] += dp[i][r]

    for r in range(13):
        dp[i + 1][r] = dp[i + 1][r] % MOD

print(dp[N][5])


### FIXED CODE ###

MOD = 10 ** 9 + 7

S = input()
N = len(S)

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

for i, s in enumerate(S):
    if s == "?":
        c = -1
    else:
        c = int(s)

    for j in range(10):
        if c != -1 and c != j:
            continue

        for r in range(13):
            dp[i + 1][(r * 10 + j) % 13] += dp[i][r]

        for r in range(13):
            dp[i + 1][r] %= MOD

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

modulo = 1000000007

import sys
sys.setrecursionlimit(100000009)


muchii = []


def recursie(x, y):
    alb = 1
    negru = 1
    for elem in muchii[x]:
        if x == y:
            continue
        result_1, result_2 = recursie(elem, x)
        alb = (alb * (result_1 + result_2)) % modulo
        negru = (negru * result_1) % modulo
    return alb, negru
    

if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    for i in range(n):
        muchii.append([])
        
    for i in range(n-1):
        # x, y = map(int, input().split())
        numbers = list(map(int, input().split(" ")))
        #print(numbers)
        
        x = numbers[0]
        y = numbers[1]
        
        muchii[x-1].append(y-1)
        muchii[y-1].append(x-1)
        
    result_1, result_2 = recursie(0, None)
    
    result = (result_1 + result_2) % modulo
    
    print(result)


### FIXED CODE ###

modulo = 1000000007

import sys
sys.setrecursionlimit(100000009)


muchii = []


def recursie(x, y):
    alb = 1
    negru = 1
    for elem in muchii[x]:
        if elem == y:
            continue
        result_1, result_2 = recursie(elem, x)
        alb = (alb * (result_1 + result_2)) % modulo
        negru = (negru * result_1) % modulo
    return alb, negru
    

if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    for i in range(n):
        muchii.append([])
        
    for i in range(n-1):
        numbers = list(map(int, input().split(" ")))
        
        x = numbers[0]
        y = numbers[1]
        
        muchii[x-1].append(y-1)
        muchii[y-1].append(x-1)
        
    result_1, result_2 = recursie(0, None)
    
    result = (result_1 + result_2) % modulo
    
    print(result)
### BUGGY CODE ###

import sys

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

Result = 0
Count_Blue = 0
if 1<=N<=10**18 and A >= 0 and B >= 0 and \
   0< A + B <= 10**18:
    for Count in range(10**100):
        Result = Result + (1 * A)
        Count_Blue += (1 * A)
        if Result > N:
            Count_Blue = Count_Blue - (Result - N)
            print(Count_Blue)
            sys.exit()
        Result = Result + (1 * B)
        if Result > N:
            print(Count_Blue)
            sys.exit()

### FIXED CODE ###

import sys

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

Count_Blue = 0
if 1<=N<=10**18 and A > 0 and B >= 0 and \
   0< A + B <= 10**18:
    Add_Blue = 1 * A
    Add_Both = Add_Blue + 1 * B

    q = N // Add_Both
    mod = N % Add_Both
    if mod < Add_Blue:
        Count_Blue = (q *Add_Blue) + mod
    else:
        Count_Blue = (q * Add_Blue) + Add_Blue
    print(Count_Blue)
elif A == 0:
    print(Count_Blue)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
Q=int(input())
B=[0]*Q
C=[0]*Q
for i in range(Q):
	B[i],C[i]=map(int,input().split())
import collections
A=collections.Counter(a)
for i in range(Q):
	if B[i] in A:
		f=A.pop(B[i])
		if C[i] in A:
			g=A[C[i]]
			h=f+g
		else:
			h=f
		A[C[i]]=h
	S=0
	keys=list(A.keys())
	values=list(A.values())
	for j in range(len(keys)):
		S=S+keys[j]*values[j]
	print(S)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
Q=int(input())
B=[0]*Q
C=[0]*Q
for i in range(Q):
	B[i],C[i]=map(int,input().split())
import collections
A=collections.Counter(a)
S=0
for j in range(N):
	S=S+a[j]
for i in range(Q):
	if B[i] in A:
		f=A.pop(B[i])
		if C[i] in A:
			g=A[C[i]]
			h=f+g
		else:
			h=f
		A[C[i]]=h
	else:
		f=0
	S=S+f*(C[i]-B[i])
	print(S)
### BUGGY CODE ###

import numpy as np
from math import factorial

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

dic = {}
after = {}

newdata = np.unique(A)
for i in range(len(newdata)):
	x = np.sum(A == newdata[i])
	if x <= 1:
		dic[newdata[i]] = 0
	else:
		dic[newdata[i]] = x * (x - 1) // 2
	if x - 1 <= 1:
		after[newdata[i]] = 0
	else:
		after[newdata[i]] = (x - 1) * (x - 2) // 2

numsum = 0
for dicv in dic.values():
	numsum += dicv 

ans = {}
for key in dic.keys():
	ans[key] = numsum - dic[key] + after[key]

for i in range(N):
	print(ans[A[i]])

### FIXED CODE ###

import numpy as np
import collections

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

dic = {}
after = {}

l = collections.Counter(A)

for key, val in l.items():
	dic[key] = val * (val - 1) // 2
	after[key] = (val - 1) * (val - 2) // 2

numsum = sum(dic.values())

ans = {}
for key in dic.keys():
	ans[key] = numsum - dic[key] + after[key]

for i in range(N):
	print(ans[A[i]])
### BUGGY CODE ###

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


def cmb(n, r):
    # combination
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    return (over[n] * under[r] * under[n - r]) % MOD


# 互いに素なx, yについて、a * x + b * y = 1の解の一つを求める。
def extGCD(x, y):
    r = [1, 0, x]
    w = [0, 1, y]
    # print(r, w)
    while w[2] != 1:
        # print(r, w)
        q = r[2] // w[2]
        w_tmp = [r[0] - q * w[0], r[1] - q * w[1], r[2] % w[2]]
        r, w = w, w_tmp

    return w[:2]


def mod_inv(a, m):
    x, _ = extGCD(a, m)
    return (x + m) % m


def g(x, y):
    return (cmb(x + y + 2, x + 1) - 1 + MOD) % MOD


r1, c1, r2, c2 = inpl()

MOD = 10**9 + 7

over = [1]
under = [1]
for i in range(r2 + c2 + 2):
    over.append(over[-1] * (i + 1) % MOD)
    under.append(under[-1] * mod_inv(i + 1, MOD) % MOD)

print((g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)) % MOD)


### FIXED CODE ###

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


def cmb(n, r):
    # combination
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    return (over[n] * under[r] * under[n - r]) % MOD


# 互いに素なx, yについて、a * x + b * y = 1の解の一つを求める。
def extGCD(x, y):
    r = [1, 0, x]
    w = [0, 1, y]
    # print(r, w)
    while w[2] != 1:
        # print(r, w)
        q = r[2] // w[2]
        w_tmp = [r[0] - q * w[0], r[1] - q * w[1], r[2] % w[2]]
        r, w = w, w_tmp

    return w[:2]


def mod_inv(a, m):
    _, x = extGCD(m, a)
    return (x + m) % m


def g(x, y):
    return (cmb(x + y + 2, x + 1) - 1 + MOD) % MOD


r1, c1, r2, c2 = inpl()

MOD = 10**9 + 7

over = [0 for i in range(r2 + c2 + 3)]
under = [0 for i in range(r2 + c2 + 3)]
over[0] = 1
for i in range(r2 + c2 + 2):
    over[i + 1] = over[i] * (i + 1) % MOD

under[r2 + c2 + 2] = mod_inv(over[r2 + c2 + 2], MOD)
for i in range(r2 + c2 + 1, 0, -1):
    under[i] = under[i + 1] * (i + 1) % MOD

print((g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)) % MOD)
### BUGGY 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[:b] = [c if x < c else x for x in l[:b]]
  l.sort()
  count += b
  if count >= n:
    break

print(sum(l))

### 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, K=map(int, input().split())
Pn=list(map(int, input().split()))
V = [0] * N
ans = 0
for n in range(N-K+1):
    tmp = 0
    for i in range(K):
        V[n+i] = (0.5*Pn[n+i]*(Pn[n+i]+1))/Pn[n+i]
        tmp += V[n+i]
    ans = max(ans, tmp)

print(ans)

### FIXED CODE ###

N, K=map(int, input().split())
Pn=list(map(int, input().split()))
V = [0] * N
ans = [0] * K
max_v = 0
sum_v = 0
for n in range(N):
    V[n] = (0.5*Pn[n]*(Pn[n]+1))/Pn[n]
    if n < K:
        sum_v += V[n]
        max_v = sum_v
    else:
        sum_v = sum_v - V[n-K] + V[n]
        max_v = max(max_v, sum_v)
print(max_v)
### BUGGY CODE ###

h, w = map(int, input().split())
a = [list(input()) for i in range(h)]
que = []
v = [[True] * (w + 2)]
v += [[True] + [j == "#" for j in a[i]] + [True] for i in range(h)]
v.append([True] * (w + 2))
m = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if v[i][j]:
            que.append((i, j))
ans = 0
while que:
    p = []
    ans += 1
    for x, y in que:
        if not v[x - 1][y]:
            v[x - 1][y] = True
            p.append((x - 1, y))
        if not v[x + 1][y]:
            v[x + 1][y] = True
            p.append((x + 1, y))
        if not v[x][y - 1]:
            v[x][y - 1] = True
            p.append((x, y - 1))
        if not v[x][y + 1]:
            v[x][y + 1] = True
            p.append((x, y + 1))
    que = p
print(ans - 1)

### FIXED CODE ###

h, w = map(int, input().split())
a = [list(input()) for i in range(h)]
que = []
v = [[True] * (w + 2)]
v += [[True] + [j == "#" for j in a[i]] + [True] for i in range(h)]
v.append([True] * (w + 2))
m = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if v[i][j]:
            que.append((i, j))
ans = 0
while que:
    p = []
    ans += 1
    for x, y in que:
        if not v[x - 1][y]:
            v[x - 1][y] = True
            p.append((x - 1, y))
        if not v[x + 1][y]:
            v[x + 1][y] = True
            p.append((x + 1, y))
        if not v[x][y - 1]:
            v[x][y - 1] = True
            p.append((x, y - 1))
        if not v[x][y + 1]:
            v[x][y + 1] = True
            p.append((x, y + 1))
    que = p
print(ans - 1)
### BUGGY CODE ###

h, w = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(h)]

all_lst = []
odd_lst = []
for i in range(0, h-1, 2):
    for j in range(w):
        all_lst.append((i+1, j+1))
        if lst[i][j] % 2 == 1:
            odd_lst.append((i+1,j+1))
    for j in reversed(range(w)):
        all_lst.append((i+2, j+1))
        if lst[i+1][j] % 2 == 1:
            odd_lst.append((i+2, j+1))
if h % 2 == 1:
    for j in range(w):
        all_lst.append((h, j+1))
        if lst[-1][j] % 2 == 1:
            odd_lst.append((h, j+1))

ans = []
flg = False
for i, tpl in enumerate(all_lst):
    if flg == True:
        ans.append((all_lst[i-1][0], all_lst[i-1][1], all_lst[i][0], all_lst[i][1]))
    if tpl in odd_lst:
        if flg == False:
            flg = True
        else:
            flg = False
        odd_lst = odd_lst[1:]
        
print(len(ans))
for a,b,c,d in ans:
    print(a,b,c,d)

### FIXED CODE ###

h, w = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(h)]

count = 0
ans = []
for i in range(0, h-1, 2):
    for j in range(w):
        if lst[i][j] % 2 == 1:
            count += 1
            if j == w-1:
                lst[i+1][j] += 1
                ans.append((i+1, j+1, i+2, j+1))
            else:
                lst[i][j+1] += 1
                ans.append((i+1, j+1, i+1, j+2))
    for j in reversed(range(w)):
        if lst[i+1][j] % 2 == 1:
            if j == 0 and i+1 == h-1:
                pass
            elif j == 0:
                lst[i+2][j] += 1
                ans.append((i+2, j+1, i+3, j+1))
                count += 1
            else:
                lst[i+1][j-1] += 1
                ans.append((i+2, j+1, i+2, j))
                count += 1
if h % 2 == 1:
    for j in range(w):
        if lst[-1][j] % 2 == 1:
            if j == w-1:
                pass
            else:
                lst[-1][j+1] += 1
                ans.append((h, j+1, h, j+2))
                count += 1
                
print(count)
for a,b,c,d in ans:
    print(a,b,c,d)
### BUGGY CODE ###

import numpy as np
n,k = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [(10**4)*(10**5)]*n
dp[0]=0
for i in range(n-1):
    dp[i+1] = min(dp[i+1],dp[i]+np.abs(h[i]-h[i+1]))
    for j in range(1,k+1):
        if i+j>n-1: break
        dp[i+j] = min(dp[i+j],dp[i]+np.abs(h[i]-h[i+j]))
print(dp[n-1]) 

### FIXED CODE ###

n,k = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [(10**4)*(10**5)]*n
dp[0]=0
for i in range(n-1):
    loop = min(k+1,n-i)
    for j in range(1,loop):
        dp[i+j] = min(dp[i+j],dp[i]+abs(h[i]-h[i+j])) 
print(dp[n-1])
### BUGGY CODE ###

import bisect
n = int(input())
l = sorted(list((map(int, input().split()))))
m = len(l)
cnt = 0
for i in range(m - 2):
    for j in range(i + 1, m - 1):
        cnt += bisect.bisect_left(l[j+1:], l[i]+l[j])
print(cnt)

### FIXED CODE ###

import bisect

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

cnt = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        cnt += max(0, bisect.bisect_left(l, l[i] + l[j]) - j - 1)
print(cnt)
### BUGGY CODE ###

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial
from bisect import bisect_right

sys.setrecursionlimit(10**7)
N = int(input())
P = list(map(int, input().split()))

rP = list(reversed(P))

cnt = 0
for i, rp in enumerate(rP):
    for val in rP[i+1:]:
        if rp > val:
            break
    else:
        cnt += 1

print(cnt)


### FIXED CODE ###

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial
from bisect import bisect_right

sys.setrecursionlimit(10**7)
N = int(input())
P = list(map(int, input().split()))

cnt = 0
minv = P[0]
for p in P:
    minv = min(minv, p)
    if p == minv:
        cnt += 1

print(cnt)
### BUGGY CODE ###

import numpy as np
P = 998244353

# N = 10
# S = 10
# AS = list(map(int, "3 1 4 1 5 9 2 6 5 3".split()))
N, S = map(int, input().split())
AS = list(map(int, input().split()))
DP = np.zeros((S + 1, N + 1), dtype=np.int64)
DP[0, 0] = 1
# print(DP)

for i in range(N):
    for j in range(S + 1):
        v = DP[j, i] * 2
        if AS[i] <= j:
            v += DP[j - AS[i], i]
        DP[j, i + 1] = v % P

# print(DP)
print(DP[S, N])


### FIXED CODE ###

import sys
import numpy as np
P = 998244353


def main(N, S, AS):
    DP = np.zeros((S + 1, N + 1), dtype=np.int64)
    DP[0, 0] = 1
    # print(DP)

    for i in range(N):
        for j in range(S + 1):
            v = DP[j, i] * 2
            if AS[i] <= j:
                v += DP[j - AS[i], i]
            DP[j, i + 1] = v % P

    # print(DP)
    print(DP[S, N])


if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'void(i8,i8,i8[:])')(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
    exit()
else:
    # read parameter
    N, S = map(int, input().split())
    AS = np.array(list(map(int, input().split())))
    from my_module import main
    main(N, S, AS)
### BUGGY CODE ###

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

for i in range(m):
    b, c = map(int, input().split())
    a = sorted(a + [c] * b, reverse=True)[:n]

print(sum(a))

### FIXED CODE ###

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

bc = [tuple(map(int, input().split())) for _ in range(m)]
a.sort()
bc.sort(key=lambda x:x[1], reverse=True)

idx = 0
res = 0
flag = False
for b,c in bc:
    for _ in range(b):
        if idx < n and a[idx] < c:
            res += c
            idx += 1
        else:
            flag = True
    if flag:
        break

if idx < n:
    res += sum(a[idx:])

print(res)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find_root(self, x):
        if self.p[x] != x:
            self.p[x] = self.find_root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def get_size(self, x):
        return self.size[self.find_root(x)]


n, K, L = map(int, input().split())
pq = [tuple(int(x)-1 for x in input().split()) for _ in range(K)]
rs = [tuple(int(x)-1 for x in input().split()) for _ in range(L)]

uk = UnionFind(n)
for p, q in pq:
    uk.unite(p, q)

ul = UnionFind(n)
for p, q in rs:
    ul.unite(p, q)

res = [tuple([uk.find_root(i), ul.find_root(i)]) for i in range(n)]

ans = ['' for _ in range(n)]
for i in range(n):
    ans[i] = str(res.count(res[i]))

print(' '.join(ans))



### FIXED CODE ###

from collections import Counter

class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find_root(self, x):
        if self.p[x] != x:
            self.p[x] = self.find_root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def get_size(self, x):
        return self.size[self.find_root(x)]


n, K, L = map(int, input().split())
pq = [tuple(int(x)-1 for x in input().split()) for _ in range(K)]
rs = [tuple(int(x)-1 for x in input().split()) for _ in range(L)]

uk = UnionFind(n)
for p, q in pq:
    uk.unite(p, q)

ul = UnionFind(n)
for p, q in rs:
    ul.unite(p, q)

res = [uk.find_root(i) * 1000000 +  ul.find_root(i) for i in range(n)]
c = Counter(res)
ans = [0] * n

for i in range(n):
    ans[i] = c[res[i]]

print(*ans, sep=' ')