Harryxun/stf_run huggingface dataset:
N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]
PX = [list(map(int, input().split())) for _ in range(Q)]
 
g = [[] for _ in range(N+1)]
for a,b in AB:
    g[a].append(b)
    g[b].append(a)
    
cnt = [0] * (N+1)
for p,x in PX:
    cnt[p] += x

# v: node, p: parent node, add: parent value
def dfs(v, p, add):
    cnt[v] += add
    for nv in g[v]:
        if nv == p:
            continue
        dfs(nv, v, cnt[v])
 
dfs(1, 0, 0)

print(' '.join(map(str, cnt[1:])))

### FIXED CODE ###

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

N, Q = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
g = [[] for _ in range(N+1)]
for a,b in AB:
    g[a].append(b)
    g[b].append(a)
 
cnt = [0] * (N+1)
for p,x in PX:
    cnt[p] += x

def dfs(v, p, add):
    cnt[v] += add
    for nv in g[v]:
        if nv == p:
            continue
        dfs(nv, v, cnt[v])

dfs(1, 0, 0)

print(' '.join(map(str, cnt[1:])))
n = int(input())
x = str(input())
X = 0
one = 0
for i in range(n):
    X+=int(x[i])*2**(n-i-1)
    if x[i]=="1":
        one+=1

l = [0, 1]
for i in range(2,n):
    if i%2==0:
        l.append(1)
    else:
        c=1
        tem = i
        while tem>1:
            tem//=2
            if tem%2==1:c+=1
        l.append(l[i%c]+1)
for i in range(n):
    if x[i]=="1":
        on=one-1
    else:
        on=one+1
    t=X^(2**(n-i-1))
    print(l[t%on]+1)


### FIXED CODE ###

n = int(input())
x = str(input())

one = x.count("1")
X = int(x, 2)

if one==1:
    for i in range(n):
        if x[i]=="1":
            print(0)
        elif i==n-1:
            print(2)
        else:
            print(1)
    
    
elif one>1:
    
    Xp = X % (one+1)
    Xm = X % (one-1)

    def f(x):
        if x==0:
            return 0
        return 1+f(x%bin(x).count("1"))

    for i in range(n):
        
        if x[i]=="0":
            c = pow(2, n-i-1, one+1)
            print(f((Xp+c)%(one+1))+1)
        else:
            c = pow(2, n-i-1, one-1)
            print(f((Xm-c)%(one-1))+1)
else:
    for i in range(n):
        print(1)
n = int(input())
s = str(input())
cnt = 0
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "B" and s[i+2] == "C":
        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = str(input())
cnt = 0
for i in range(n-2):
    if s[i] == "A" and s[i+1] == "B" and s[i+2] == "C":
        cnt += 1
print(cnt)
N,A = map(int,input().split())
a = N%500
if a<=A:
    print('YES')
else:
    print('no')

### FIXED CODE ###

N,A=int(input()),int(input())
print('Yes' if N%500<=A else 'No')
N,W = map(int,input().split())
w_in, v = map(int,input().split())
table = [[] for i in range(4)]
table[0].append(v)
for i in range(N-1):
    w, v = map(int,input().split())
    table[w-w_in].append(v)
for i in range(N):
    table[i].sort(reverse=True)
    for j in range(len(table[i])-1):
            table[i][j+1] += table[i][j]
    table[i].insert(0,0)
ans = 0
for i in range(len(table[0])):
    for j in range(len(table[1])):
        for k in range(len(table[2])):
            for l in range(len(table[3])):
                if w_in*i+(w_in+1)*j+(w_in+2)*k+(w_in+3)*l <= W:
                    ans = max(ans, table[0][i]+table[1][j]+table[2][k]+table[3][l])
print(ans)


### FIXED CODE ###

N,W = map(int,input().split())
w_in, v = map(int,input().split())
table = [[] for i in range(4)]
table[0].append(v)
for i in range(N-1):
    w, v = map(int,input().split())
    table[w-w_in].append(v)
for i in range(4):
    table[i].sort(reverse=True)
    for j in range(len(table[i])-1):
            table[i][j+1] += table[i][j]
    table[i].insert(0,0)
ans = 0
for i in range(len(table[0])):
    for j in range(len(table[1])):
        for k in range(len(table[2])):
            for l in range(len(table[3])):
                if w_in*i+(w_in+1)*j+(w_in+2)*k+(w_in+3)*l <= W:
                    ans = max(ans, table[0][i]+table[1][j]+table[2][k]+table[3][l])
print(ans)
#文字列の入力
S = input()

#listを一文字ずつのlistに
S_list = list(S)

if(len(S_list)%2==0):
  for i in range(len(S_list)/2):
    if(S_list[i]==S_list[len(S_list)-1]):
      ans = ans + 0
    else:
      ans = ans + 1
  for i in range(len(S_list)/2 + 1):
    if(S_list[i]==S_list[len(S_list)-1]):
      ans = ans + 0
    else:
      ans = ans + 1
print(ans)

### FIXED CODE ###

#文字列の入力
S = input()

#listを一文字ずつのlistに
S_list = list(S)
ans = 0
#偶数文字の場合
if(len(S_list)%2==0):
  #文字数/2回for文
  for i in range(int(len(S_list)/2)):
    #i文字目と後ろからi文字目が一緒なら何もしない
    #print(i,len(S_list)-i-1)
    if(S_list[i]==S_list[len(S_list)-i-1]):
      ans = ans + 0
    #一緒じゃ無い場合
    else:
      ans = ans + 1
else:
  for i in range(int(len(S_list)/2)):
    #print(i,len(S_list)-i-1)
    if(S_list[i]==S_list[len(S_list)-i-1]):
      ans = ans + 0
    else:
      ans = ans + 1
print(ans)
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
from scipy.sparse import csr_matrix

n, m, p = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]

fwd = [[] for _ in range(n + 1)]
rev = [[] for _ in range(n + 1)]

for a, b, c in abc:
    fwd[a].append(b)
    rev[b].append(a)


def dfs(s, adj):
    stack = [s]
    arrived = [False] * (n + 1)
    arrived[s] = True
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if not arrived[v]:
                arrived[v] = True
                stack.append(v)

    return arrived


can_go_fwd = dfs(1, fwd)
can_go_rev = dfs(n, rev)

row = []
col = []
cost = []
for a, b, c in abc:
    if can_go_fwd[a] and can_go_rev[b]:
        row.append(a)
        col.append(b)
        cost.append(p - c)

g = csr_matrix((cost, (row, col)), shape=(n + 1, n + 1))
try:
    dist = bellman_ford(g, indices=1).astype(int)
    ans = max(0, -dist[n])
    print(ans)
except NegativeCycleError:
    print(-1)


### FIXED CODE ###

n, m, p = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]


def bellman_ford(s, g):
    # loop 0 - (n-1) : bellman ford
    # loop n - (2n-1): check g can be updated
    dist = [float("inf")] * n
    dist[s] = 0
    for i in range(2 * n):
        for a, b, c in abc:
            a -= 1
            b -= 1
            cost = -(c - p)

            if dist[b] > dist[a] + cost:
                dist[b] = dist[a] + cost
                if i >= n:
                    dist[b] = -float("inf")

    if dist[g] == -float("inf"):
        return -1

    else:
        return max(-dist[g], 0)


ans = bellman_ford(0, n - 1)
print(ans)
n=int(input())
a=list(map(int,input().split()))
num=[]
count=0

a=sorted(a)

for i in a:
  for j in num:
    if i%j==0:
      count+=1
      break
      
  num.append(i)
  
  
if a[0]==a[1]:
  count+=1
  
print(n-count)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num=[0]*(max(a)+1)
maxa=max(a)
cnt=1

for i in a:
  while 1:
    try:
      num[i*cnt]+=1
      cnt+=1
      
      
    except IndexError:
      break
  cnt=1      

count=0

for i in range(n):
  if num[a[i]]==1:
    count+=1
    
print(count)
# -*- coding: utf-8 -*-
# 整数の入力
a = int(raw_input())
# スペース区切りの整数の入力
a, b = map(int, raw_input().split())

mylist = [a+b,a-b,a*b]
print max(mylist)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
a, b = map(int, raw_input().split())

mylist = [a+b,a-b,a*b]
print max(mylist)
S = input()
n = len(S)
prefix = [''] * (n + 1)
for i, c in enumerate(S, start=1):
    prefix[i] = prefix[i - 1] + c
res = 0
count = [0] * 2020
for i in range(1, n + 1):
    num = int(prefix[i])
    if num % 2019 == 0:
        res += 1
    temp = (num * 10 ** (n - i)) % 2019
    res += count[temp]
    count[temp] += 1
print(res)

### FIXED CODE ###

S = list(input())
n = len(S)
cur = 0
count = [0] * 2020
count[0] = 1
for i, c in enumerate(map(int, S[::-1])):
    cur = (cur + c * pow(10, i, 2019)) % 2019
    count[cur] += 1
    
print(sum(c * (c - 1) // 2 for c in count))
a=input()
cnt=0
for i in range(len(a)-1):
  if(a[i]==a[i+1]):
    cnt+=1
print(cmt)

### FIXED CODE ###

a=input()
cnt=0
for i in range(len(a)-1):
  if(a[i]!=a[i+1]):
    cnt+=1
print(cnt)
import collections

n,m = map(int,input().split())
friend = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    if a not in friend[b]:
        friend[a].append(b)
        friend[b].append(a)

q = collections.deque()
visited = [0 for i in range(n)]

ans = 0
for i in range(n):
    if visited[i] == 0:
        visited[i] = 1
        tmp = 1
        for j in friend[i]:
            if visited[j] == 0:
                visited[j] = 1
                tmp += 1
                q.append(j)
        while q:
            s = q.pop()
            for k in friend[s]:
                if visited[k] == 0:
                    visited[k] = 1
                    tmp += 1
                    q.append(k)
    ans = max(ans,tmp)

print(ans)

### FIXED CODE ###

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

mod = 10**9 + 7

sum_a = sum(a)%mod
ans = 0
for i in range(n-1):
    sum_a -= a[i]
    ans += (a[i]*sum_a)%mod

print(ans%mod)
# -*- coding: utf-8 -*-
S = str(input())
box = ["A", "G", "C", "T"]
ACGTbox = str()
for i in range(0, len(S)):
    for j in range(i, len(S)):
        if S[j] in box:
            s += S[j]
        else:
            break
    if len(s) > len(ACGTbox): 
        ACGTbox = s 
    s = str()
print(len(ACGTbox))

### FIXED CODE ###

# -*- coding: utf-8 -*-
S = str(input())
box = ["A", "G", "C", "T"]
s = str()
ACGTbox = str()
for i in range(0, len(S)):
    for j in range(i, len(S)):
        if S[j] in box:
            s += S[j]
        else:
            break
    if len(s) > len(ACGTbox):
        
        ACGTbox = s 
    s = str()
print(len(ACGTbox))
A, B = map(int, input().split())
G1 = [['#'] * 100 for i in range(100)]
G2 = [['.'] * 100 for i in range(100)]

A, B = A - 1, B - 1

h, w = 0, 0
for a in range(A):
    if w > 99:
        h += 1
    G1[h][w] = '.'
    w += 2

h, w = 1, 0
for b in range(B):
    if w > 99:
        h += 1
    G2[h][w] = '#'
    w += 2


print(100, 100)
for g in G1:
    print(''.join(g))
for g in G2:
    print(''.join(g))


### FIXED CODE ###

A, B = map(int, input().split())
white = [["#"] * 100 for i in range(50)]
black = [["."] * 100 for i in range(50)]
A, B = A-1, B-1

row = 0
line = 0
for i in range(A):
    white[line][row] = "."
    row += 2
    if row >= 100:
        row = 0
        line += 2

row = 0
line = 1
for i in range(B):
    black[line][row] = "#"
    row += 2
    if row >= 100:
        row = 0
        line += 2

ans = white + black
print(100, 100)
for a in ans:
    print("".join(a))
x,y,z=(map(int,input().split())

print(z, x, y)

### FIXED CODE ###

x,y,z=map(int,input().split())
print(z,x,y)
#print("{} {}".format(z,x,y))
import numpy as np
n,w = map(int, input().split())
high = np.array([[0]*(w+1)]*(n+1),np.int)
for i in range(1,n+1):
    weight, value = map(int, input().split())
    for j in range(w+1):
        if j < weight:
            high[i][j] = high[i-1][j]
        else:
            high[i][j] = max([high[i-1][j-weight]+value, high[i-1][j]])
print(high[n][w])

### FIXED CODE ###

n,w = map(int, input().split())
high = [0] * (w + 1)
for i in range(n):
    weight, value = map(int, input().split())
    if weight <= w:
        renewal = high[:weight]
        renewal += [max([j+value, k]) for j,k in zip(high[:w-weight+1], high[weight:])]
        high = renewal
print(high[w])
input_line = str(input())
s = []

for i in range(len(input_line)):
  if input_line == '9':
    s.append('1')
  elif input_line == '1':
    s.append('9')
  else:
    s.append(input_line[i])

for x in s:
    mojiretu += x
    
print(mojiretu)


### FIXED CODE ###

input_line = str(input())
s = []

for i in range(len(input_line)):
    if input_line[i] == '9':
        s.append('1')
    elif input_line[i] == '1':
        s.append('9')
    else:
        s.append(input_line[i])

mojiretu = ''

for x in s:
    mojiretu += x

print(int(mojiretu))
N = int(input())
A = list(map(int, input().split()))
counter = 0
for val in range(N - 1):
    for i in range(N - val - 1):
        if A[val] == A[val+i+1]:
            counter += 1
            break
    else:
        continue
    break
if counter == 0:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

S, T = input().split()
A, B = map(int, input().split())
U = input()

if U == S:
    print(A - 1, B)
else:
    print(A, B - 1)
import math
 
datas = input().split(" ")
 
a = float(datas[0])
b = float(datas[1])
c = float(datas[2])
 
if(a+b < (c-a-b)**2):
  print( "Yes" )
else:
  print( "No" )

### FIXED CODE ###

retu = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51"

retu = retu.split(",")
retuint=[]
for i in retu :
	retuint.append(int(i))

index=input()

print(retuint[int(index)-1])
a = int(input())
l = input()
dp = [0]*1110
qp = [0]*1110
ans = 0
#print('###############')
def bfs(i,x,y):
	#print(i,x)
	if y == 3:
		ans +=1
		return 0
	else:
		for j in range(i,a):
			if int(x+str(l[j])) != 1:bfs(j+1,x+str(l[j]),y+1)
			dp[int(x+str(l[j]))] = 1
bfs(0,'',0)
print(ans)

### FIXED CODE ###

a = int(input())
b = input()
ans = 0
for i in range(1000):
	T = '0'*(3-len(str(i)))
	t = T+ str(i)
	I = 0
	while I < 3:
		for j in b:
			#if t == '022':print(I,t[I],j)
			if I == 3:
				break
			if t[I] == j:I+=1
			#if t == '022':print(I,j)
		
		if I == 3: 
			#print(t)
			ans +=1
		break
print(ans)
import sys
N = int(input())
M = 5000
I = [[] for _ in range(N)]

i = 1
for a in list(map(int, input().split())):
  I[a-1].append(i)
  i += 1
X = list(map(int, input().split()))

def dfs(v,I,X):
  INF = 10**20
  DP = [INF for _ in range(X[v]+1)]
  DP[0] = 0
  for i in I[v]:
    x = X[i]
    y = dfs(i,I,X)
    if x < y:
      x,y = y,x  # x >= y
    for a in range(X[v],y-1,-1):
      DP[a] = DP[a-y] + x
      if a-x >= 0:
        DP[a] = min(DP[a], DP[a-x] + y)
    for a in range(y-1, -1, -1):
      DP[a] = INF
  ans = min(DP)
  #print(DP, v)
  if ans >= INF:
    print("IMPOSSIBLE")
    sys.exit()
  return ans

dfs(0,I,X)
print("POSSIBLE")
  
  

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**4)
N = int(input())
I = [[] for _ in range(N)]

i = 1
for a in list(map(int, input().split())):
  I[a-1].append(i)
  i += 1
X = list(map(int, input().split()))

def dfs(v,I,X):
  INF = 10**20
  DP = [INF for _ in range(X[v]+1)]
  DP[0] = 0
  for i in I[v]:
    x = X[i]
    y = dfs(i,I,X)
    if x < y:
      x,y = y,x  # x >= y
    for a in range(X[v],-1,-1):
      if a-y >= 0:
        DP[a] = DP[a-y] + x
        if a-x >= 0:
          DP[a] = min(DP[a], DP[a-x] + y)
      else:
        DP[a] = INF
        
  ans = min(DP)
  #print(DP, v)
  if ans >= INF:
    print("IMPOSSIBLE")
    sys.exit()                        
    
  del DP, INF
  return ans

dfs(0,I,X)
print("POSSIBLE")
inp=list(map(int,input().split(" ")))
N=inp[0]
T=inp[1]+0.5

a=[0]*N
b=[0]*N
for i in range(N):
    inp=list(map(int,input().split(" ")))
    a[i]=inp[0]
    b[i]=inp[1]


time=0
get =0

while(1):
    time+=1
    if(time>T or len(a)==0):
        break
    need=list(map(lambda x,y:x*time+y,a,b))
    mini=min(need)
    time+=mini
    go=[i for i, x in enumerate(need) if x == mini]#get list to minimum
    gomin=[]
    for i in range(len(go)):#make list a
        gomin.append(a[go[i]])
    go=gomin.index(max(gomin))#find a minimum index
    del a[go]
    del b[go]
    if(time>T):
        break
    get+=1

print(get)



### FIXED CODE ###

a = input()
a=a.replace("hi","")
if(len(a)==0):
    print("Yes")
else:
    print("No")
N = int(input())
A = list(map(int,input().split()))

ls = [0]*N
for i in range(N):
    ls[A[i]] += 1
s = 0
for i in range(N):
    s += ls[i]*(ls[i]-1)//2

for k in range(N):
    print(s-ls[A[k]] + 1)
    

### FIXED CODE ###

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

ls = [0]*N
for i in range(N):
    ls[A[i]-1] += 1
s = 0
for i in range(N):
    s += ls[i]*(ls[i]-1)//2
ans = [0]*N
for i in range(N):
    ans[i] = s-ls[A[i]-1] + 1

print(*ans,sep='\n')
number = int(raw_input())
my_set = set()
for i in range(number):
    input_line = raw_input()
    splitted_line = input_line.split(" ")
    my_set.add((splitted_line[0], - int(splitted_line[1]), i+1))

my_sorted = sorted(my_set)

for item in my_sorted:
    print(item[2])


### FIXED CODE ###

number = int(input())
my_set = set()
for i in range(number):
    input_line = input()
    splitted_line = input_line.split(" ")
    my_set.add((splitted_line[0], - int(splitted_line[1]), i+1))

my_sorted = sorted(my_set)

for item in my_sorted:
    print(item[2])
N,K= list(map(int, input().split()))
A= list(map(int, input().split()))
AA=sorted(A)
num=0
before=0
for i in A:
    num+=AA.index(i)
num2=0
for i in range(N-1):
    for j in range(i+1,N):
        if A[i]>A[j]:
            num2+=1
hoge=(K-1)*K//2%1000000007
hoge=hoge*num%1000000007
hoge2=num2*K%1000000007
hoge=(hoge+hoge2)%1000000007
print(hoge)


### FIXED CODE ###

M,D= list(map(int, input().split()))
ans=0
for i in range(M):
    for j in range(22,D+1):
        if str(j)[1]=='0' or str(j)[1]=='1':
            continue
        elif i+1==int(str(j)[0])*int(str(j)[1]):
            ans+=1
print(ans)
# -*- coding: utf-8 -*-

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

cNtN = [[0] * 2 for i in range(N)]
for i in range(N):
    cNtN[i][0], cNtN[i][1] = map(int, input().split())

min_c = float('inf')
for i in range(N):
    if cNtN[i][1] <= T and cNtN[i][0] < min_C:
        min_c = cNtN[i][0]

if min_c == float('inf'):
    print('TLE')
else:
    print(min_c)

### FIXED CODE ###

# -*- coding: utf-8 -*-

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

cNtN = [[0] * 2 for i in range(N)]
for i in range(N):
    cNtN[i][0], cNtN[i][1] = map(int, input().split())

for i in range(N):
    if cNtN[i][1] > T:
        cNtN[i][0] = float('inf')

min_c = float('inf')
for i in range(len(cNtN)):
    min_c = min(min_c, cNtN[i][0])

if min_c == float('inf'):
    print('TLE')
else:
    print(min_c)
# -*- coding: utf-8 -*-                                                         
tmp = input()
my_str = input()

start = 0
end = 1
max_len = 0

while (end < len(my_str)):
    if my_str[start:end] in my_str[end:]:
        if end - start > max_len:
            max_len = end - start
     	end += 1
    else:
        start += 1

print(max_len)


### FIXED CODE ###

# -*- coding: utf-8 -*-
tmp = input()
my_str = input()

start = 0
end = 1
max_len = 0

while (end < len(my_str)):
    if my_str[start:end] in my_str[end:]:
        if end - start > max_len:
            max_len = end - start
        end += 1
    else:
        start += 1

print(max_len)
import math
s = input().rstrip().split(' ')
height = int(s[0])
width = int(s[1])
area = height * width
if area % 2 == 0:
	mass = area / 2
    print(mass)
else:
	mass = math.ceil(area / 2)
    print(mass)

### FIXED CODE ###

import math
s = input().rstrip().split(' ')
height = int(s[0])
width = int(s[1])
area = height * width
if height != 1 and width != 1:
	mass = math.ceil(area / 2)
	print(mass)
else:
	print(1)
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

import numpy as np

def main():
    N = int(input())
    As = [tuple(map(int, input().split())) for _ in range(N-1)]

    m = np.zeros((N, N),dtype=int)

    for a, b in As:
        m[a-1][b-1] = m[b-1][a-1] = 1

    ans = np.zeros((N,N),dtype=int)

    from collections import deque

    max_c = 1
    l = deque([(0,0)])
    while (len(l)):
        v0, c0 = l.popleft()
        c1 = 1
        for v1 in range(N):
            if m[v0][v1]:
                m[v0][v1] = m[v1][v0] = 0
                if c1 == c0:
                    c1 += 1
                max_c = max(max_c, c1)
                ans[v0][v1] = ans[v1][v0] = c1
                l.append((v1, c1))
                c1 += 1

    print(max_c)
    for u, v in As:
        print(ans[u-1][v-1])



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc146","d",main)


### FIXED CODE ###


#%%
import sys
sys.setrecursionlimit(100000)

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

def main():
    N = int(input())

    g = [[] for _ in range(N-1)]
    for i in range(N-1):
        a, b = map(int, input().split())
        g[a-1].append((b-1, i))

    ans = [[None] for _ in range(N-1)]

    def dfs(v0, c0):
        c = 1
        for v1, e in g[v0]:
            if c==c0:
                c += 1
            ans[e] = c
            if v1 < N-1:
                dfs(v1, c)
            c += 1

    dfs(0, 0)

    print(max(ans))
    for c in ans:
        print(c)



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc146","d",main)
h,w = map(int,input().split())
aa = [list(map(int,input().split())) for _ in range(h)]
ans=[]

for hi in range(h):
  for wi in range(w-1):
    if aa[hi][wi] % 2 == 1:      
      aa[hi][wi+1] += 1
      ans.append([hi+1,wi+1,hi+1,wi+2])
      
  if hi < h-1:
    if aa[hi][wi+1] % 2 ==1:      
      aa[hi+1][wi+1] +=1
      ans.append([hi+1,wi+1,hi+2,wi+1])

print(len(ans))
for yp,xp,yn,xn in ans:
  print('{} {} {} {}'.format(yp,xp,yn,xn))      

### FIXED CODE ###

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

for hi in range(h):
  for wi in range(w-1):
    if aa[hi][wi] % 2 == 1:      
      aa[hi][wi] -= 1
      aa[hi][wi+1] += 1
      ans.append([hi+1,wi+1,hi+1,wi+2])
      
  if hi < h-1:
    if aa[hi][-1] % 2 ==1:      
      aa[hi][-1] -= 1
      aa[hi+1][-1] += 1
      ans.append([hi+1,w, hi+2, w])

print(len(ans))
for yp,xp,yn,xn in ans:
  print('{} {} {} {}'.format(yp,xp,yn,xn))
N = int(input())
l = []
ans = 0
for i in range(N):
    A = int(input())
    for j in range(A):
        l.append(list(map(int,input().split())))
for bit in range(1<<N):
    flag = True
    listH = [(bit>>i)&1 for i in range(N)]
    for i in range(N):
        if not listH[i]:
            continue
        for k in range(2):
            x = l[i][0]-1
            y = l[i][1]
            if listH[x] != y:
                flag = False
    if flag:
        ans = max(ans,sum(listH))
print(ans)

### FIXED CODE ###

N = int(input())
L = []
l = []
A = []
ans = 0
for i in range(N):
    a = int(input())
    A.append(a)
    for j in range(a):
        l.append(list(map(int,input().split())))
    L.append(l)
    l = []
for bit in range(1<<N):
    flag = True
    listH = [(bit>>i)&1 for i in range(N)]
    for j in range(N):
        if not listH[j]:
            continue
        for k in range(A[j]):
            x = L[j][k][0]-1
            y = L[j][k][1]
            if listH[x] != y:
                flag = False
    if flag:
        ans = max(ans,sum(listH))
print(ans)
import sys
A, B, K= map(int, next(sys.stdin.buffer))
x = min(A, B, K)
print(A - x, B - x)

### FIXED CODE ###

import sys
A, B, K= map(int, next(sys.stdin.buffer).split())
if K > A:
  a = 0
  b = max(0, B - (K - A))
else:
  a = A - K
  b = B

print(a, b)
[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()

C_list = [0] * N
for i in range(M):
  [B, C] = list(map(int, input().split(' ')))
  if C_list[0] > C:
    continue
  else:
    for k in range(B):
      C_list[k] = C
      if C_list[k + 1] > C:
        break
    C_list.sort()
  
C_list.sort()

ans = 0
count = 0
for i in range(N):
  if card_list[-1] > C_list[-1]:
    ans += card_list.pop()
    count += 1
  else:
    ans += C_list.pop()
    count += 1
    
  if C_list == []:
    for k in range(N - count):
      ans += card_list.pop()
    break
      
print(ans)
  
                

### FIXED CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()
compare_list = []

for i in range(M):
  (B, C) = list(map(int, input().split(' ')))
  compare_list.append((C,B))
    
compare_list.sort()

ans = 0
for i in range(N):
  if compare_list == []:
    ans += sum(card_list[i:])
    break
  if card_list[-1] > compare_list[-1][0]:
    ans += card_list.pop()
  elif compare_list[-1][1] > 0:
    ans += compare_list[-1][0]
    tmp = compare_list.pop()
    a = tmp[0]
    b = tmp[1]
    if b != 1:
      compare_list.append((a,b-1)) 
      
print(ans)