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

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


# 桁数の一番大きいものが最大。そのあと数を大きい順に並べればいい
dp = [0]*(N+1)       # dp[i]: i 本のマッチで条件を満たす整数の最大桁数
cost = [ 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]  # 各数字に必要なマッチ棒の数(逆順)

for num_match in range( 2, N+1 ):
    for Aj in A:
        if num_match >= cost[Aj]:
            dp[num_match] = max( dp[num_match], dp[num_match-cost[Aj]]+1 )


# 求めた桁数 dp[N] を用いて順序を求める
ans = ""
digit = dp[N]

A.sort( reverse=True )
while N > 0:
    for Ai in A:
        if N-cost[Ai] >=0 and dp[N-cost[Ai]] == digit-1:
            ans += str(Ai)
            N -= cost[Ai]
            digit -= 1
            break

print( ans )

### FIXED CODE ###

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


# 桁数の一番大きいものが最大。そのあと数を大きい順に並べればいい
dp = [0] + [-float('inf')] * (N+1)       # dp[i]: i 本のマッチで条件を満たす整数の最大桁数
cost = [ 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]  # 各数字に必要なマッチ棒の数(逆順)

for num_match in range( 2, N+1 ):
    for Aj in A:
        if num_match >= cost[Aj]:
            dp[num_match] = max( dp[num_match], dp[num_match-cost[Aj]]+1 )


ans = ""
digit = dp[N]

A.sort( reverse=True )
while N > 0:
    for Ai in A:
        if N-cost[Ai] >=0 and dp[N-cost[Ai]] == digit-1:
            ans += str(Ai)
            N -= cost[Ai]
            digit -= 1
            break

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

from collections import deque

s = input()
d = deque()
num = 0
for i in s:
    d.append(i)
q = int(input())
for i in range(q):
        data = input().split()
        if len(data) == 1:
            d.reverse()
        else:
            f = int(data[1])
            c = data[2]
            if f == 1:
                d.appendleft(c)
            else:
                d.append(c)

s = list(d)
s = "".join(s)



print(s)

### FIXED CODE ###

from collections import deque

s = input()
d = deque()
header = 1
for i in s:
    d.append(i)
q = int(input())
for i in range(q):
        data = input().split()
        if len(data) == 1 :
            header *= -1
        else:
            f = int(data[1])
            c = data[2]
            if header == 1:
                if f == 1:
                    d.appendleft(c)
                else:
                    d.append(c)
            else:
                if f == 1:
                    d.append(c)
                else:
                    d.appendleft(c)
                
if header == -1:
    d.reverse()

s = list(d)
s = "".join(s)



print(s)
### BUGGY CODE ###

S = input()
k = []
Q = int(input())
now = 0
ans = ""
mode = 0
for i in range(Q):
    K = input().split()
    if K[0] == "1":
        S = S[::-1]
    else:
        if K[1] == "1":
            S = K[2]+S
        else:
            S = S+K[2]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
mode = 0
ans_1 = ""
ans_2 = ""
for i in range(Q):
    K = input().split()
    if K[0] == "1":
        if mode == 0:
            mode = 1
        else:
            mode = 0
    else:
        if K[1] == "1":
            if mode == 0:
                ans_1 += K[2]
            else:
                ans_2 += K[2]
        else:
            if mode == 0:
                ans_2 += K[2]
            else:
                ans_1 += K[2]
ans_1 = ans_1[::-1]
K = ans_1+S+ans_2
if mode == 1:
    print(K[::-1])
else:
    print(K)
### BUGGY CODE ###

n=int(input())
a=[int(input())for i in range(n)]
print(len(set([i for i in a if a.count(i)%2!=0])))

### FIXED CODE ###

n=int(input())
a=[int(input())for i in range(n)]
a.sort()
memo=a[0]
ans=0
cnt=0
for i in range(n):
    if a[i]==memo:
        cnt+=1
        if i==n-1:
            if cnt%2!=0:
                ans+=1
    else:
        if cnt%2!=0:
            ans+=1
        if i==n-1:
            ans+=1
        cnt=1

    memo=a[i]
print(ans)
### BUGGY CODE ###

import itertools
import math

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

def agent(a,i,j):
  return abs(i-j)==abs(a[i-1]+a[j-1])

count=0
X=list(range(1,N+1))
for c in itertools.combinations(X,2):
   if agent(A,*c):
      count+=1
      
print(count)
      

### FIXED CODE ###

 
N=int(input())
*A,=map(int,input().split())
ref,count={},0

for i,a in enumerate(A):
  if i-a in ref:
     count += ref[i-a]
  if i+a in ref:
     ref[i+a]+=1
  else:
     ref[i+a]=1

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

a, b, c, d =map(int, input().split())
cnt = []

if a == c and b == d:
    print(max(a*c, b*d))
    exit()
else:
    for i in range(a, b+1):
        for j in range(c, d+1):
            cnt.append(i*j)
        
print(max(cnt))

### FIXED CODE ###

a, b, c, d = map(int,input().split())

if a == c and b == d:
    print(max(a*c, b*d))
    exit()
else:
    print(max(a*c, a*d,b*c,b*d))
### BUGGY CODE ###

def readinput():
    n=int(input())
    x=input()
    return n,x

def popcount(x):
    return bin(x).count('1')

def f(x):
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        return ans    

def main(n,x):
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    ans=[]
    b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                ans.append(0)
            else:
                xx=( xmodm1 + (m-1) -b%(m-1) )%(m-1)
                ans.append(f(xx)+1)
        else:
            xx=( xmodp1 + b%(m+1) )%(m+1)
            ans.append(f(xx)+1)
        b=b//2
    return ans

if __name__=='__main__':
    n,x=readinput()
    ans=main(n,x)
    for a in ans:
        print(a)



### FIXED CODE ###

def readinput():
    n=int(input())
    x=input()
    return n,x

poptbl=[0]*(2*10**5+1)
def popcount(x):
    global poptbl
    if poptbl[x]!=0:
        return poptbl[x]
    
    poptbl[x]=bin(x).count('1')
    return poptbl[x]

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    if ftbl[x]!=0:
        return ftbl[x]
    
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        ftbl[x]=ans
        return ans    

def main():
    n=int(input())
    x=input()
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    pow2mod1=[0]*n
    pow2mod2=[0]*n
    pow2mod1[0]=1
    pow2mod2[0]=1
    for i in range(1,n):
        if m!=1:
            pow2mod1[i]=pow2mod1[i-1]*2 % (m-1)
        pow2mod2[i]=pow2mod2[i-1]*2 % (m+1)

    ans=[]
    #b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                a=0
                ans.append(a)
            else:
                xx=( xmodm1 + (m-1) -pow2mod1[n-i-1] )%(m-1)
                #ans.append(f(xx)+1)
                a=f(xx)+1
                ans.append(a)
        else:
            xx=( xmodp1 + pow2mod2[n-i-1] )%(m+1)
            #ans.append(f(xx)+1)
            a=f(xx)+1
            ans.append(a)
        #b=b//2
        print(a)
    return ans

if __name__=='__main__':
    #n,x=readinput()
    ans=main()
    #for a in ans:
    #    print(a)
### BUGGY CODE ###

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

for i in range(k):
    tmp = [0] * n
    for j in range(n):
        for k in range(a[j]*2+1):
            if (j - a[j] + k) >= 0 and (j - a[j] + k) < n:
                tmp[(j - a[j] + k)] += 1
    
    if min(a) == n:
        print(' '.join(map(str, a)))
        exit()
    a = tmp


print(' '.join(map(str, a)))


# 10 5
# 20 8
# 40 10
# 80 12
# 160 15

### FIXED CODE ###

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

for i in range(k):
    s = [0] * (n + 1)
    for j in range(n):
        l = max(0, j - a[j])
        r = min(n, j + a[j]+1)
        s[l] += 1
        s[r] += -1
    m = s[0]
    for j in range(1,n+1):
        s[j] += s[j-1]
        if j < n:
            m = min(m, s[j])
    a = s[:-1]
    if m == n:
        print(' '.join(map(str, a)))
        exit()
print(' '.join(map(str, a)))
### BUGGY CODE ###

k = int(input())
c = 1
if(k%2 == 0):
    print(-1)
else:
    for i in range(1,k):
      a = 7*((10**i - 1)//9)
      if(a%k == 0):
        break
      else:
        c += 1
    print(c)

### FIXED CODE ###

k = int(input())
n = 7
c = 1
if(k%2 == 0):
  print(-1)
else:
  while(True):
    if(n%k == 0):
      break
    if(c > k):
      c = -1
      break
    r = n%k
    n = 10*r+7
    c += 1
  print(c)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
l, r = -1, 10 ** 12


def func(x):
    k = 0  # 修行回数初期化
    for a, f in zip(A, F): # O(N)
        if a <= x // f:  # (Ai-Ki)*Fi<=x Ki=0なら次 (a*f<=xの変形)
            continue
        k += a - x // f
        # else (Ai-Ki)*Fi<=x を満たすようにKiを設定。つまり修行回数にKiを加算。
    if k <= K:
        return 1
    return 0


while (r - l > 1): # O(logx)
    mid = (l + r) // 2
    if func(mid):
        r = mid
    else:
        l = mid


print(r)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
l, r = -1, 10 ** 12


def func(x):  # a, x, kは全て整数ということに注意(//またはint())
    k = 0  # 修行回数初期化
    for a, f in zip(A, F):  # O(N)
        e = x // f
        if a <= e:  # (Ai-Ki)*Fi<=x Ki=0なら次 (a*f<=xの変形)
            continue
        k += a - e
        # else (Ai-Ki)*Fi<=x を満たすようにKiを設定。つまり修行回数にKiを加算。
    if k <= K:
        return 1
    return 0


while (r - l > 1):  # O(logx)
    mid = (l + r) // 2
    if func(mid):
        r = mid
    else:
        l = mid


print(r)
### BUGGY CODE ###

s = input()
num = int(input())
for i in range(num):
    a = input().split(" ")
    a[0] = int(a[0])
    if(a[0] == 1):
        s = s[::-1]
    elif(a[0] == 2):
        a[1] = int(a[1])
        if(a[1] == 1):
            s = a[2] + s
        elif(a[1] == 2):
            s = s + a[2]

print(s)



### FIXED CODE ###

s = input()
b = ""
f = ""
change_flag = 1
for i in range(int(input())):
    a = input().split(" ")
    if(a[0] == "1"):
        change_flag *= -1
    else:
        if((a[1] == "1" and change_flag == 1) or (a[1] == "2" and change_flag == -1)):
            b = a[2] + b
        else:
            f = f + a[2]

if(change_flag == -1):
    print(f[::-1]+s[::-1]+b[::-1])
else:
    print(b+s+f)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
q = int(input())
bcs = []
for i in range(q):
    bcs.append(list(map(int,input().split())))
for bc in bcs:
    a = [bc[1] if i == bc[0] else i for i in a]
    print(sum(a))

### FIXED CODE ###

n0 = int(1e5)+1
x = [0]*n0

n = int(input())
a0 = list(map(int,input().split()))
q = int(input())
bcs = []
for i in range(q):
    bcs.append(list(map(int,input().split())))

for a in a0:
    x[a] += 1
sum0 = sum(a0)

for bc in bcs:
    sum0 = sum0 + bc[1]*x[bc[0]] - bc[0]*x[bc[0]]
    x[bc[1]] += x[bc[0]]
    x[bc[0]] = 0
    print(sum0)
### BUGGY CODE ###

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

cnt = 0

for day in range(1,M+1):
    B = [x[1] for x in A if x[0]<=day]
    if B:
        ind = B.index(max(B))
        cnt += B[ind]
        A[ind][1] = 0

print(cnt)

### FIXED CODE ###

from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*10**5
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=[b]
for i in v[:M]:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)
### BUGGY CODE ###

import itertools


X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = [a + b for (a, b) in list(itertools.product(A, B))]
AB.sort(reverse=True)
ans = [ab + c for (ab, c) in list(itertools.product(AB[:min(3000, X*Y*Z)], C))]
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

### FIXED CODE ###

#abc123d
 
x,y,z,k=map(int,raw_input().split())
a=sorted(map(int,raw_input().split()),reverse=True)
b=sorted(map(int,raw_input().split()),reverse=True)
c=sorted(map(int,raw_input().split()),reverse=True)
 
ab=sorted([i+j for i in a for j in b],reverse=True)
res=sorted([ij+l for ij in ab[:k] for l in c],reverse=True)
for i in res[:k]:
	print i
### BUGGY CODE ###

def aaa(n,m):
    count1 = 1
    count2 = 1
    if n % 2 == 1:
        count1 = count1 + n//2
        count2 = count2 + n//2 + 1
    else:
        count1 = count1 + n//2
        count2 = count2 + n//2
    if m % 2 == 1:
        count1 = count1 + m//2 + 1
        count2 = count2 + m//2
    else:
        count1 = count1 + m//2
        count2 = count2 + m//2
    l3 = [count1,count2]
    return l3
s = list(input())
j = 0
a = 0
b = 0
l = []
l4 = []
for i in range(len(s)-1):
    if s[i] == "R" and j == 0 and s[i+1] == "R":
        a = a + 1
        l.append(0)
    elif s[i] == "R" and j == 1 and s[i+1] == "R":
        l = l + aaa(a,b) + l4
        a = 1
        b = 0
        j = 0
        l4 = []
        l.append(0)
    elif s[i] == "R" and j == 1 and s[i+1] == "L":
        l = l + aaa(a,b) + l4
        a = 0
        b = 0
        j = 0
        l4 = []
    elif s[i] == "L" and j == 0:
        j = 1
    elif s[i] == "L" and j == 1:
        b = b + 1
        l4.append(0)
if j == 1:
    b = b + 1
    l4.append(0)
l = l + aaa(a,b) + l4
for x in l:
    print(x,end=" ")

### FIXED CODE ###

def aaa(n,m):
    count1 = 1
    count2 = 1
    if n % 2 == 1:
        count1 = count1 + n//2
        count2 = count2 + n//2 + 1
    else:
        count1 = count1 + n//2
        count2 = count2 + n//2
    if m % 2 == 1:
        count1 = count1 + m//2 + 1
        count2 = count2 + m//2
    else:
        count1 = count1 + m//2
        count2 = count2 + m//2
    l3 = [count1,count2]
    return l3
s = list(input())
n = len(s)
j = 0
a = 0
b = 0
l = [0]*n
for i in range(len(s)):
    if s[i] == "R" and j == 0:
        a = a + 1
    elif s[i] == "R" and j == 1:
        l[c-1] = aaa(a-1,b)[0]
        l[c] = aaa(a-1,b)[1]
        a = 1
        b = 0
        j = 0
    elif s[i] == "L" and j == 0:
        j = 1
        c = i
    elif s[i] == "L" and j == 1:
        b = b + 1
l[c-1] = aaa(a-1,b)[0]
l[c] = aaa(a-1,b)[1]
for x in l:
    print(x,end=" ")
### BUGGY CODE ###

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

dic = {}
for i in a:
    dic.update({i:a.count(i)})
#print(dic)
k = list(dic.keys())

ans = 0
for i in k:
    if i > dic[i]:
        ans += dic[i]
    elif i < dic[i]:
        ans += dic[i] - i
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
#print(c)
ans = 0
for n,c in c.items():
    if c < n:
        ans += c
    elif n < c:
        ans += c - n
print(ans)
### BUGGY CODE ###

# 2019/08/16

s=list(input())
t=list(input())

c1={}
c2={}
for ss,tt in zip(s,t):
    c1[ss]=c1.get(ss,'')+tt
    c2[tt]=c2.get(tt,'')+ss
    
    if len(c1[ss])<2 and len(c2[tt])<2:continue
    if c1[ss].count(tt)==len(c1[ss]) and c2[tt].count(ss)==len(c2[tt]):continue
    else:
        print('No')
        exit()

print('Yes')


### FIXED CODE ###

# 2019/08/16

s=list(input())
t=list(input())

c1={}
c2={}
for ss,tt in zip(s,t):
    if c1.get(ss) is None:
        c1[ss]=tt
    if c2.get(tt) is None:
        c2[tt]=ss
    if c1[ss]==tt and c2[tt]==ss:continue
    else:
        print('No')
        exit()

print('Yes')
### BUGGY CODE ###

N = int(input())

S = []
for i in range(N):
    S.append(input())

m = 0
ans = []
for i in range(N):
    if m < S.count(S[i]):
        ans = []
        ans.append(S[i])
        m = S.count(S[i])
    if m == S.count(S[i]):
        ans.append(S[i])

a = sorted(set(ans))

for i in a:
    print(i)


### FIXED CODE ###

N = int(input())

S = {}
for i in range(N):
    s = input()
    if s not in S.keys():
        S[s] = 0
    S[s] += 1

m = 0
ans = []
for s, c in S.items():
    if c > m:
        ans = []
        ans.append(s)
        m = c
    elif c == m:
        ans.append(s)


for i in sorted(ans):
    print(i)
### BUGGY CODE ###

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

tmp = []
ans = 0
for i in range(n):
    tmp.append(pl[i]*(pl[i]+1)/2/pl[i])
    if i >= k-1:
        if sum(tmp[i-k+1:i+1]) > ans:
            ans = sum(tmp[i-k+1:i+1])
print(ans)

### FIXED CODE ###

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

dp = [0] * (n + 1)

for i in range(n):
    dp[i+1] = dp[i] + (pl[i] + 1)/2

ans = 0
for i in range(k, n+1):
    ans = max(ans, dp[i] - dp[i-k])

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

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

out=sum(A)
for i in range(M):
    saidai = max(A)
    out-=saidai
    out+=saidai//2
    A[A.index(saidai)] = saidai//2
    # print('dam,out:',saidai,out)

print(out)


### FIXED CODE ###

[N,M] = list(map(int,input().split()))
A = list(map(int,input().split()))
out=sum(A)
import heapq
a = list(map(lambda x: x*(-1), A))  # 各要素を-1倍 最大値取り出すため
heapq.heapify(a)
# print(a)

for i in range(M):
    # saidai = max(A)
    saidai = heapq.heappop(a)*(-1)
    out-=saidai
    out+=saidai//2
    # A[A.index(saidai)] = saidai//2
    heapq.heappush(a, (saidai//2)*(-1))
    # print('dam,out,a:',saidai,out,a)

print(out)
### BUGGY CODE ###

N,A,B= input().split()
ans=0
for i in range(int(N)):
    if i%(int(A)+int(B))<int(A):
        ans+=1
print(ans)


### FIXED CODE ###

N, A, B = [int(x) for x in input().strip().split()]
p = N // (A + B) * A
q = N % (A + B)
if q > A:
    q = A
print(p + q)
### BUGGY CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    h,w=map(int,input().split())
    a=[list(map(int,input().split())) for i in range(h)]
    b=[list(map(int,input().split())) for i in range(h)]

    lst=[[0]*w for i in range(h)]

    lst[0][0]={abs(a[0][0]-b[0][0]):1}
    # print(lst)
    d=deque([(0,0)])
    while d:
        now=d.popleft()
        tmp=lst[now[0]][now[1]].keys()
        if now[0]+1<h:
            ab=abs(a[now[0]+1][now[1]]-b[now[0]+1][now[1]])
            if lst[now[0]+1][now[1]]==0:
                d.append((now[0]+1,now[1]))
                lst[now[0]+1][now[1]]={}

            for i in tmp:
                lst[now[0]+1][now[1]][i+ab]=1
                lst[now[0]+1][now[1]][abs(i-ab)]=1

        # print(lst)
        if now[1]+1<w:
            ab=abs(a[now[0]][now[1]+1]-b[now[0]][now[1]+1])
            if lst[now[0]][now[1]+1]==0:
                d.append((now[0],now[1]+1))
                lst[now[0]][now[1]+1]={}

            for i in tmp:
                lst[now[0]][now[1]+1][i+ab]=1
                lst[now[0]][now[1]+1][abs(i-ab)]=1
        # print(d)
        # print(lst)
    anslst=list(lst[-1][-1].keys())
    anslst.sort(key=lambda x: abs(x))
    print(abs(anslst[0]))

main()

### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline

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

kouho = [[0] * (w) for _ in range(h)]
delta = abs(AA[0][0] - BB[0][0])
kouho[0][0] |= 1 << delta
for y in range(h):
    for x in range(w):
        nx = x + 1
        ny = y
        if nx < w:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp

        nx = x
        ny = y + 1
        if ny < h:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp
# print(kouho)
for i in range(81):
    if (kouho[h - 1][w - 1] >> i) % 2:
        print(i)
        exit()
### BUGGY CODE ###

N,Q=map(int,input().split())
tree={}
for i in range(N-1):
  a,b=map(int,input().split())
  if (a-1) in tree:
    tree[a-1].append(b-1)
  else:
    tree[a-1]=[b-1]
  if (b-1) in tree:
    tree[b-1].append(a-1)
  else:
    tree[b-1]=[a-1]

point={}

for i in range(Q):
  p,x=map(int,input().split())
  if (p-1) in point:
    point[p-1]+=x
  else:
    point[p-1]=x

ans=[0]*N
stack=[]
stack.append([0,0,-1])
while len(stack)>0:
  nodes=stack.pop()
  node=nodes[0]
  sump=nodes[1]
  parent=nodes[2]
  if node in point:
    sump=sump+point[node]
  ans[node]=sump
  if node in tree:
      childs=tree[node]
      for child in childs:
        if child==parent:
          continue
        stack.append([child,sump,node])

print(*ans)

### FIXED CODE ###

N,Q=map(int,input().split())
tree={}
for i in range(N-1):
  a,b=map(int,input().split())
  if (a-1) in tree:
    tree[a-1].append(b-1)
  else:
    tree[a-1]=[b-1]
  if (b-1) in tree:
    tree[b-1].append(a-1)
  else:
    tree[b-1]=[a-1]

point=[0]*N

for i in range(Q):
  p,x=map(int,input().split())
  point[p-1]+=x

ans=[0]*N
stack=[]
stack.append([0,0,-1])
while len(stack)>0:
  nodes=stack.pop()
  node=nodes[0]
  sump=nodes[1]
  parent=nodes[2]
  sump=sump+point[node]
  ans[node]=sump
  if node in tree:
      childs=tree[node]
      for child in childs:
        if child!=parent:
          stack.append([child,sump,node])

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

from collections import defaultdict
h, w, m = map(int, input().split())
targets = defaultdict(int)
targets_count_yoko = defaultdict(int)
targets_count_tate = defaultdict(int)
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    targets_count_yoko[x] += 1
    targets_count_tate[y] += 1
    targets[(y, x)] = -1

max_row = max(targets_count_yoko.values())
max_line = max(targets_count_tate.values())
y_idx = []
x_idx = []
max_count_x = 0
max_count_y = 0
for i in range(w):
    if targets_count_yoko[i] == max_row:
        x_idx.append(i)
        max_count_x += 1
for i in range(h):
    if targets_count_tate[i] == max_line:
        y_idx.append(i)
        max_count_y += 1


ans = max_line + max_row
kumi = max_count_x*max_count_y
for key_y, key_x in targets.keys():
    if key_y in y_idx and key_x in x_idx:
        kumi -= 1
    if kumi == 0:
        break

if kumi == 0:
    print(ans-1)
else:
    print(ans)



### FIXED CODE ###

from collections import defaultdict
h, w, m = map(int, input().split())
targets = defaultdict(int)
targets_count_yoko = defaultdict(int)
targets_count_tate = defaultdict(int)
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    targets_count_yoko[x] += 1
    targets_count_tate[y] += 1
    targets[(y, x)] = -1

max_row = max(targets_count_yoko.values())
max_line = max(targets_count_tate.values())
y_idx = defaultdict(bool)
x_idx = defaultdict(bool)
max_count_x = 0
max_count_y = 0
for i in range(w):
    if targets_count_yoko[i] == max_row:
        x_idx[i] = True
        max_count_x += 1
for i in range(h):
    if targets_count_tate[i] == max_line:
        y_idx[i] = True
        max_count_y += 1


ans = max_line + max_row
kumi = max_count_x*max_count_y
for key_y, key_x in targets.keys():
    if y_idx[key_y] and x_idx[key_x]:
        kumi -= 1
    if kumi == 0:
        break

if kumi == 0:
    print(ans-1)
else:
    print(ans)