Harryxun/stf_run huggingface dataset:
D, G = map(int, input().split())
PC = [0]+[list(map(int,input().split())) for _ in range(D)]
print(1e9)

def dfs(d, g):
    if(d == 0):
        return 1e9

    c = min(g//(100*d), PC[d][0])
    s = 100*d*c
    if c == PC[d][0]:
        s += PC[d][1]
    if s<g:
        c += f(d-1, g-s)
    return min(c, f(d-1,g))

print(dfs(D, G))

### FIXED CODE ###

D, G = map(int, input().split())
PC = [0]+[list(map(int,input().split())) for _ in range(D)]

def dfs(d, g):
    if(d == 0):
        return 1e9

    c = min(g//(100*d), PC[d][0])
    s = 100*d*c
    if c == PC[d][0]:
        s += PC[d][1]
    if s<g:
        c += dfs(d-1, g-s)
    return min(c, dfs(d-1,g))

print(dfs(D, G))
def main():
    n = int(input())

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

    for cx in range(0, 101):
        for cy in range(0, 101):
            H = -1
            for i, xyh in enumerate(l):
                x,y,h = xyh
                if H == -1 and h < 0:
                    continue
                if H == -1:
                    H = h + abs(x-cx) + abs(y-cy)
                    continue
                if H < 1 or H != int(H) or (h > 0 and h != H - abs(x-cx) - abs(y-cy) or (h = 0 and h > H - abs(x-cx) - abs(y-cy))):
                    break
                if i == len(l) - 1:
                    print(cx,cy,H)
                    return

if __name__ == "__main__":
    main()

### FIXED CODE ###

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

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

    l.sort(key = lambda x:-x[2])

    for cx in range(0, 101):
        for cy in range(0, 101):
            for i, xyh in enumerate(l):
                x,y,h = xyh
                if i == 0:
                    H = h + abs(x-cx) + abs(y-cy)
                    if H < 1 or H != int(H):
                        break
                    continue
                if h != max((H - abs(x-cx) - abs(y-cy)), 0):
                    break
                if i == n-1:
                    print(cx,cy,H)
                    return

if __name__ == "__main__":
    main()
N, M = map(int, input().split())
seitou = [0 for _ in range(N)]
penalty = [0 for _ in range(M)]

for i in range(M):
	S = list(input().split())
	# print(S)
	num = int(S[0])
	res = S[1]
	if res == "AC":
		seitou[num - 1] = 1
	else:
		if seitou[num - 1] == 0:
			penalty[num - 1] += 1
			
# print(*seitou)
# print(*penalty)
print(sum(seitou), end=" ")
print(sum(penalty))

### FIXED CODE ###

N, M = map(int, input().split())
seitou = [0 for _ in range(N)]
penalty = [0 for _ in range(N)]

for i in range(M):
	S = list(input().split())
	# print(S)
	num = int(S[0])
	res = S[1]
	if res == "AC":
		seitou[num - 1] = 1
	else:
		if seitou[num - 1] == 0:
			penalty[num - 1] += 1
			
# print(*seitou)
# print(*penalty)
print(sum(seitou), end=" ")

ans = 0

for i in range(N):
	if seitou[i] == 1:
		ans += penalty[i]
print(ans)
s = input()
a = set()
for i in len(s):
  a.add(s[i])
if len(a) == 2:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

s = input()
a = set()
for i in range(len(s)):
  a.add(s[i])
if len(a) == 2:
  print('Yes')
else:
  print('No')
n,k = map(int,input().split())
s = input()
x = len(s)
lst = [0]
ans = 0
for i in range(1,x):
    if s[i-1] != s[i]:
        lst.append(i)
lst.append(x)
if s[0] == "1" and s[x-1] == "0":
    s.reverse()
if s[0] == "0" and s[x-1] == "1":
    if 2*k >= len(lst):
        ans = x
    else:
        i = 1
        while i+2*k+1 <= len(lst)-1:
            ans = max(ans,lst[i+2*k+1]-lst[i])
            i += 2
        ans = max(ans,lst[2*k])
if s[0] == "0" and s[x-1] == "0":
    if 2*k >= len(lst):
        ans = x
    else:
        i = 1
        while i+2*k+1 <= len(lst)-1:
            ans = max(ans,lst[i+2*k+1]-lst[i])
            i += 2
        ans = max(ans,lst[2*k])
        ans = max(ans,x-lst[len(lst)-2*k-1])
if s[0] == "1" and s[x-1] == "1":
    if 2*k+1 >= len(lst):
        ans = x
    else:
        i = 0
        while i+2*k+1 <= len(lst)-1:
            ans = max(ans,lst[i+2*k+1]-lst[i])
            i += 2
print(ans)       

### FIXED CODE ###

n,k = map(int,input().split())
s = input()
x = len(s)
lst = [0]
ans = 0
if s[0] == "1" and s[x-1] == "0":
    s = s[::-1]
for i in range(1,x):
    if s[i-1] != s[i]:
        lst.append(i)
lst.append(x)
if s[0] == "0" and s[x-1] == "1":
    if 2*k >= len(lst):
        ans = x
    else:
        i = 1
        while i+2*k+1 <= len(lst)-1:
            ans = max(ans,lst[i+2*k+1]-lst[i])
            i += 2
        ans = max(ans,lst[2*k])
if s[0] == "0" and s[x-1] == "0":
    if 2*k >= len(lst):
        ans = x
    else:
        i = 1
        while i+2*k+1 <= len(lst)-1:
            ans = max(ans,lst[i+2*k+1]-lst[i])
            i += 2
        ans = max(ans,lst[2*k])
        ans = max(ans,x-lst[len(lst)-2*k-1])
if s[0] == "1" and s[x-1] == "1":
    if 2*k+1 >= len(lst):
        ans = x
    else:
        i = 0
        while i+2*k+1 <= len(lst)-1:
            ans = max(ans,lst[i+2*k+1]-lst[i])
            i += 2
print(ans)
"""
解説を参考に作成 その3
"""


def solve():
    N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    A.sort()
    CB = [list(reversed([int(i) for i in input().split()])) for _ in range(M)]
    CB = list(sorted(CB, reverse=True))

    count = 0
    flag = False
    for cb in CB:
        for b in range(cb[1]):
            if A[count] < cb[0]:
                A[count] = cb[0]
            else:
                flag = True
                break
            count += 1
        if flag:
            break
    print(sum(A))


if __name__ == '__main__':
    solve()


### FIXED CODE ###

"""
解説を参考に作成 その3
"""


def solve():
    N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    A.sort()
    CB = [list(reversed([int(i) for i in input().split()])) for _ in range(M)]
    CB = list(sorted(CB, reverse=True))

    count = 0
    flag = False
    for cb in CB:
        for b in range(cb[1]):
            if A[count] < cb[0]:
                A[count] = cb[0]
            else:
                flag = True
                break
            count += 1
            if count >= N:
                flag = True
                break

        if flag:
            break
    print(sum(A))


if __name__ == '__main__':
    solve()
import sys
S = input()
K = int(input())

if len(set(S)) == 1:
    print((len(S) * K) // 2)
    sys.exit()

if S[-1] == S[0]:
    letter = S[0]
    i = 1
    left_count = 1
    while letter == S[i]:
        left_count += 1
        i += 1
    right_count = 1
    i = len(S) - 2
    while letter == S[i]:
        right_count += 1
        i -= 1

    if left_count % 2 == 1 and right_count % 2 == 1:
        ans = K - 1
    else:
        ans = 0

tmp_count = 1
tmp_ans = 0
for s in range(1, len(S)):
    tmp = S[s]
    if tmp == S[s - 1]:
        tmp_count += 1
        if s == len(S) - 1:
            tmp_ans += tmp_count // 2
    else:
        tmp_ans += tmp_count // 2
        tmp_count = 1
print(tmp_ans * K + ans)

### FIXED CODE ###

import sys
S = input()
K = int(input())

if len(set(S)) == 1:
    print((len(S) * K) // 2)
    sys.exit()

if S[-1] == S[0]:
    letter = S[0]
    i = 1
    left_count = 1
    while letter == S[i]:
        left_count += 1
        i += 1
    right_count = 1
    i = len(S) - 2
    while letter == S[i]:
        right_count += 1
        i -= 1

    if left_count % 2 == 1 and right_count % 2 == 1:
        ans = K - 1
    else:
        ans = 0

else:
    ans = 0
tmp_count = 1
tmp_ans = 0
for s in range(1, len(S)):
    tmp = S[s]
    if tmp == S[s - 1]:
        tmp_count += 1
        if s == len(S) - 1:
            tmp_ans += tmp_count // 2
    else:
        tmp_ans += tmp_count // 2
        tmp_count = 1
print(tmp_ans * K + ans)
# -*- coding: utf-8 -*-
import sys

n, q = map(int, input().split())

counts = [0] * (n+1)
adjs = {a: [] for a in range(1,n+1)}

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

costs = [[int(x) for x in input().split()] for i in range(q)]

for cost in costs:
    counts[cost[0]] += cost[1]

def visit(v: int, parent: int):
    counts[v] += counts[parent]
    for child in adjs[v]:
        if child == parent:
            continue
        visit(child, v)

visit(1, 0)

print(' '.join(list(map(lambda x: str(x), counts[1:]))))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

n, q = map(int, input().split())

counts = [0] * (n+1)
adjs = {a: [] for a in range(1,n+1)}

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

costs = [[int(x) for x in input().split()] for i in range(q)]

for cost in costs:
    counts[cost[0]] += cost[1]

visited = set()
queue = deque()
queue.append(1)

while len(queue) > 0:
    a = queue.popleft()
    visited.add(a)
    for b in adjs[a]:
        if b in visited:
            continue
        counts[b] += counts[a]
        queue.append(b)

for c in counts[1:]:
    print(c, end=" ")
print()
ans=0
n=int(input())
for _ in range(n):
    x,u=input().split()
    if x=='JPY':
        ans+=int(u)
    else:
        ans+=(int(u)*380000)
print(ans)

### FIXED CODE ###

ans=0
n=int(input())
for _ in range(n):
    x,u=input().split()
    if u=='JPY':
        ans+=int(x)
    else:
        ans+=(float(x)*380000.0)
print(ans)
import math

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

c=int((a*b)/math.gcd(a,b))
print(c)

### FIXED CODE ###

import math

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

c=0

while(1):
  c+=a
  if c%b==0:
    print(c)
    break
n,a,b=map(int,input().split())
ans=0

se=n//(a+b)
n%=a+b
ans+=se*a + min(a,n)
prnit(ans)

### FIXED CODE ###

n,a,b=map(int,input().split())
ans=0

se=n//(a+b)
n%=a+b
ans+=se*a + min(a,n)
print(ans)
n,c = map(int,input().split())
table = [0]*(10**5)
chan = [[] for _ in range(c+1)]

for _ in range(n):
    s,t,c = map(int,input().split())
    chan[c].append([s,t])

times = []
for i in range(c+2):
    arr = chan[i]
    if chan[i]==[] : continue
    for i in range(len(arr)):
        if i == len(arr)-1 : break
        if arr[i][1] == arr[i+1][0]:
            arr[i+1] = [arr[i][0], arr[i+1][1]]
            arr[i] = [1,0]
    times += arr

for ele in times:
    table[ele[0]] += 1
    table[ele[1]+1] -= 1

for i in range(len(table)):
    if i==1 : continue
    table[i] += table[i-1]



print(times)
print(max(table))



### FIXED CODE ###

import numpy as np

n,c = map(int,input().split())
table = np.zeros(10**5+2, dtype=np.int32)
chs = [[] for _ in range(c+1)]

for _ in range(n):
    s,t,c = map(int,input().split())
    chs[c].append([s,t])

# 同チャンネル内の連続番組を合体
times = []
for ch in chs:
    if not ch: continue
    ch.sort()
    for i in range(len(ch)):
        if i == 0: continue
        if ch[i-1][1] == ch[i][0]:
            ch[i] = [ch[i-1][0], ch[i][1]]
            ch[i-1] = []
    for arr in ch:
        if not arr: continue
        times.append(arr)

# いもす法
for arr in times:
    table[arr[0]] += 1
    table[arr[1]+1] -= 1

# 累積和の最大値
ans = table.cumsum().max()

print(ans)
x, a, b = map(int, input().split())
xa = abs(x-a)
xb = abs(x-b)
if xa < xb:
  print(A)
else:
  print(B)

### FIXED CODE ###

x, a, b = map(int, input().split())
xa = abs(x-a)
xb = abs(x-b)
if xa < xb:
  print("A")
elif xa > xb:
  print("B")
a,b = map(int,input().split())
d = []
j = 1
if a>=b:
  x = a
else:
  x = b
for i in range (1,x):
  if a%i==0 and b%i==0:
    d+=[i]
while j<len(d):
  k=j+1
  while k<len(d) and d[k]<math.sqrt(d[len(d)-1]):
    if d[k]%d[j]==0:
      d.pop(k)
      k-=1
    else:
      k+=1
  j+=1
print(len(d))

### FIXED CODE ###

a,b = map(int,input().split())
f = [1]
while(b!=0):
  a,b=b,a%b
while a%2==0:
  f.append(2)
  a//=2
p = 3
while p*p<=a:
  if a%p==0:
    f.append(p)
    a//=p
  else:
    p+=2
if a!=1:
  f.append(a)
print(len(set(f)))
A,B = map(int,input().split())

ans = 0
C = min(A,B)
X = [True]*(C+1)
X[0] = X[1] = False
for i in range(2,C+1):
    if i*i>C:break
    if X[i]:
        X[i::i] = [False]*(C//i)
        if A%i==0 and B%i==0:
            ans+=1
print(ans+1)

### FIXED CODE ###

import math,sys
sys.setrecursionlimit(1000000)
def mygcd(x,y):
    if x<y:x,y=y,x
    if y==0:return x
    return mygcd(y,x%y)
def is_prime(n):
    if n==1:return True
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:return False
    return True
A,B = map(int,input().split())
gcd = mygcd(A,B)
C = []
for i in range(1,gcd+1):
    if i*i>gcd:break
    if gcd%i==0:
        C.append(i)
        if i!=gcd//i:
            C.append(gcd//i)
cnt = 0
for c in C:
    if is_prime(c):cnt+=1
print(cnt)
import sys
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
cnt = [[0 for _ in range(20)] for _ in range(20)]
ans = 0
for _ in range(n):
	a = input()
	x, y = 0, 0
	if "." in a:
		i = len(a)-1
		while a[i] != ".":
			i -= 1
			x, y = x-1, y-1
		b = int(a[:i] + a[i+1:])
	else:
		b = int(a)
	#print(b)
	while b%2 == 0 and x < 19:
		x += 1
		b //= 2
	while b%5 == 0 and y < 19:
		y += 1
		b //= 5
	print(x, y)
	x, y = x+9, y+9
	for i in range(18-x, 20):
		for j in range(18-y, 20):
			ans += cnt[i][j]
	cnt[x][y] += 1
print(ans)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
cnt = [[0 for _ in range(20)] for _ in range(20)]
ans = 0
for _ in range(n):
	a = input()
	x, y = 0, 0
	if "." in a:
		i = len(a)-1
		while a[i] != ".":
			i -= 1
			x, y = x-1, y-1
		b = int(a[:i] + a[i+1:])
	else:
		b = int(a)
	#print(b)
	while b%2 == 0 and x < 9:
		x += 1
		b //= 2
	while b%5 == 0 and y < 9:
		y += 1
		b //= 5
	#print(x, y)
	x, y = x+9, y+9
	for i in range(18-x, 20):
		for j in range(18-y, 20):
			ans += cnt[i][j]
	cnt[x][y] += 1
print(ans)
# %%
n = int(input())
x = input()

num_of_1 = x.count("1")

first = int(x, 2)

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

if num_of_1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        elif i == n-1:
            print(2)
        else:
            print(1)
    exit()

first_one, first_zero = first % (num_of_1 - 1), first % (num_of_1 + 1)

for i in range(n):
    if x[i] == "0":
        print(1 + f((first_zero + pow(2, n-i-1, num_of_1 + 1)) % num_of_1 + 1))
    else:
        print(1 + f((first_one - pow(2, n-i-1, num_of_1 - 1)) % num_of_1 - 1))


### FIXED CODE ###

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

num_of_1 = x.count("1")

first = int(x, 2)

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

if num_of_1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        elif i == n-1:
            print(2)
        else:
            print(1)
    exit()

first_one, first_zero = first % (num_of_1 - 1), first % (num_of_1 + 1)

for i in range(n):
    if x[i] == "0":
        print(1 + f((first_zero + pow(2, n-i-1, num_of_1 + 1)) % (num_of_1 + 1)))
    else:
        print(1 + f((first_one - pow(2, n-i-1, num_of_1 - 1)) % (num_of_1 - 1)))
N = int(input())

d = map(int, input().split())

total = 0
for i in range(N):
    for j in range(i+1, N):
        total += d[i] * d[j]

print(total)

### FIXED CODE ###

N = int(input())

d = list(map(int, input().split()))

total = 0
for i in range(N):
    for j in range(i+1, N):
        total += d[i] * d[j]

print(total)
import heapq
N, M = map(int,input().split())
L = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int,input().split())
    L[A-1].append(B)
Q = []
ans = 0
for i in range(M):
    Q += L[i]
    try:
        ans += heapq.heappop(Q)
    except:
        pass
print(ans)

### FIXED CODE ###

import heapq
N, M = map(int,input().split())
L = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int,input().split())
    try:
        L[A-1].append(-B)
    except:
        pass
Q = []
ans = 0
for i in range(M):
    for j in L[i]:
        heapq.heappush(Q, j)
    try:
        ans -= heapq.heappop(Q)
    except:
        pass
print(ans)
n = int(input())
a = list(map(int, input().split()))

ans = [0 for i in range(max(a))]

for i in a:
  ans[i-1]+=1
  if i <max(a):
    ans[i]+=1
  if i-2 >= 0:
    ans[i-2]+=1
print(max(ans))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0 for i in range(max(a)+3)]

for i in a:
  ans[i]+=1
  ans[i+1]+=1
  ans[i-1]+=1
    
print(max(ans))
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import queue

def main():
    mod=10**9+7
    N=I()
    adj=[[] for _ in range(N)]
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
    bit=[-1]*N#未確認,F,S    
    bit[0]=0
    bit[-1]=1
    pL=[0]*N
    dS=0
    
    q=queue.Queue()
    q.put([0,0,0])#v.pare,depth
    
    #深さを調べる
    while not q.empty():
        v,p,d=q.get()
        pL[v]=p
        if v==N-1:
            dS=d
            break
        for i in range(len(adj[v])):
            nv=adj[v][i]
            if nv!=p:
                q.put((nv,v,d+1))
    
    #主要なところを塗る            
    v=N-1            
    for _ in range((dS-1)//2):
        v=pL[v]
        bit[v]=1
        
        
    q.put([0,0])#v.pare
    while not q.empty():
        v,p=q.get()
        if bit[v]==-1:
            bit[v]=bit[p]

        for i in range(len(adj[v])):
            nv=adj[v][i]
            if nv!=p:
                q.put((nv,v))
        
        
                    
    s=sum(bit)#sunukeが塗れる
    if s>=N-s:
        print("Snuke")
    else:
        print("Fennec")
     
        
    
    

main()


### FIXED CODE ###

#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import queue

def main():
    mod=10**9+7
    N=I()
    adj=[[] for _ in range(N)]
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
    bit=[-1]*N#未確認,F,S    
    bit[0]=0
    bit[-1]=1
    pL=[0]*N
    dS=0
    
    q=queue.Queue()
    q.put((0,0,0))#v.pare,depth
    
    #深さを調べる
    while not q.empty():
        v,p,d=q.get()
        pL[v]=p
        if v==N-1:
            dS=d
            break
        for i in range(len(adj[v])):
            nv=adj[v][i]
            if nv!=p:
                q.put((nv,v,d+1))
    
    #主要なところを塗る            
    v=N-1            
    for _ in range((dS-1)//2):
        v=pL[v]
        bit[v]=1
        
    q2=queue.Queue()
    q2.put((0,0))#v.pare
    while not q2.empty():
        v,p=q2.get()
        if bit[v]==-1:
            bit[v]=bit[p]

        for i in range(len(adj[v])):
            nv=adj[v][i]
            if nv!=p:
                q2.put((nv,v))
        
        
                    
    s=sum(bit)#sunukeが塗れる
    if s>=N-s:
        print("Snuke")
    else:
        print("Fennec")
     
        
    
    

main()
def solve(field):
  for i in range(1, h + 1):
    for j in range(1, w + 1):
      if field[i][j] == '#':
        continue
        if field[i-1][j] == field[i][j-1] == field[i][j+1] == field[i+1][j] == '.':
        '''上下左右に黒がない場合、黒色にできない（隣も塗らざるを得ないから）。
        また黒色にできないのはその場合に限る（1つ以上あれば――ダブってても白には戻らないため――べたべた塗ればよい）'''
          return False
        return True

h, w = list(map(int, input().split()))
field = ['.' + input() + '.' for _ in range(1, h + 1)]
#左右の端についてもsolve(field)を適用するため、入力に左右を付け加える
field = ['.'*(w+2)] + field + ['.'*(w+2)]
'''上下の端についても同様の処理。fieldは例えば['.....', '..#..', '.###.', '..#..', '.....']となる。
これのi番目のリストのj項が、field[i][j]によって指示される。'''
print('Yes' if solve(field) else 'No')#solve(field)だけで、Trueが返ってくるということを意味する。


### FIXED CODE ###

def solve(field):
  for i in range(1, h + 1):
    for j in range(1, w + 1):
      if field[i][j] == '.':
        continue
        #それ以後の処理がスキップされ、次のループに。つまり#の場合のみ次に進める。
      if field[i-1][j] == field[i][j-1] == field[i][j+1] == field[i+1][j] == '.':
      #上下左右に黒がない場合（全部白の場合）、黒色にできない（隣も塗らざるを得ないから）。
      #また黒色にできないのはその場合に限る（1つ以上あれば――ダブってても白には戻らないため――べたべた塗ればよい）
        return False
  return True
#インデント注意。任意の#のfieldに対してFalse返らなかったらTrueということなので、最初の条件節を出る（同じインデントかそれより前）。
h, w = list(map(int, input().split()))
field = ['.' + input() + '.' for _ in range(h)]
#左右の端についてもsolve(field)を適用するため、入力に左右を付け加える
field = ['.'*(w+2)] + field + ['.'*(w+2)]
#上下の端についても同様の処理。fieldは例えば['.....', '..#..', '.###.', '..#..', '.....']となる。
#これのi番目のリストのj項が、field[i][j]によって指示される。

print('Yes' if solve(field) else 'No')
#solve(field)だけで、Trueが返ってくるということを意味する。
N = int(input())

ans =  N(N-1)/2

print(int(ans))


### FIXED CODE ###

N = int(input())

ans =  (N*(N-1)) // 2
print(int(ans))
#coding: utf-8

N = input()
N_list = list(N)

if N_list[0] == N_list[1] == N_list[2]:
	print("Yes")
elif N_list[1] == N_list[2] == N_list[3]:
	print("Yes")
elif N_list[2] == N_list[3] == N_list[4]:
	print("Yes")
else :
	print("No")

### FIXED CODE ###

#coding: utf-8

N_list = list(input())

if N_list[0] == N_list[1] == N_list[2]:
	print("Yes")
elif N_list[1] == N_list[2] == N_list[3]:
	print("Yes")
else:
	print("No")
N, K = map(int, input().split())
ans = ((K-1)**(M-1))*K
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
ans = ((K-1)**(N-1))*K
print(ans)
N, Q = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a] += [b]
  graph[b] += [a]


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

def dfs(u, pre, c):
  for v in graph[u]:
    if v != pre:
      cnt[v] += cnt[u]
      dfs(v, u, cnt[v])

dfs(0, -1, cnt[0])
print(*cnt)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.buffer.readline
def dfs(G,v,p):
    for nv in G[v]:
        if(nv==p):
            continue
        point[nv]+=point[v]
        dfs(G,nv,v)

N,Q=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
point=[0]*N
for i in range(Q):
    p,x=map(int,input().split())
    point[p-1]+=x
dfs(G,0,-1)
print(*point)