Harryxun/stf_run huggingface dataset:
N,Q=map(int,input().split())

tree={}
tree[1]=-1
cnt=[0]*N

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

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

for k in range(1,N):
    cnt[k]+=cnt[tree[k+1]-1]

# def search(root,x):
#     leaf =[]
#     for i,j in tree.items():
#         if j ==root:
#             leaf.append(i)
        
#     if len(leaf)!=0:
#         for k in leaf:
#             search(k,x)
#             cnt[k-1]+=x

# for i in range(N-1):
#     a,b = map(int,input().split())
#     tree[b]=a
# for j in range(Q):
#     p,x=map(int,input().split())
#     if p==1:
#         cnt+=x
#     else:
#         cnt[p-1]+=x
#         search(p,x)


print(*cnt)





### FIXED CODE ###

import sys #追加
sys.setrecursionlimit(500*500)

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

cost=[0]*n
edge = [[] for _ in range(n)]

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

for _ in range(q):
    p,x=map(int,input().split())
    cost[p-1]+=x


visited=[-1]*n


def dfs(n,c):

    cost[n]+=c
    tmp=cost[n]
    visited[n]=0

    for v in edge[n]:
        if visited[v]==-1:
            dfs(v,tmp)
    

dfs(0,0)

print(*cost)
n,k= map(int,input().split())
s=input()
s[k-1]=s[k-1].lower
print(s)

### FIXED CODE ###

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

#print(s)
#print(s[0])
#print(s[2])
for i in range(k-1):
  a=a+s[i]
#print(a)
a=a+s[k-1].lower()
#print(a)
for i in range(n-k):
  a=a+s[i+k]
print(a)
import math
S=input()

hour = int(math.floor(S/3600))
min = int(math.floor((S-hour*3600)/60))
sec =  int(S - h*3600 - m*60)

print(str(hour)+":"+str(min)+":"+str(sec))

### FIXED CODE ###

import math
S=int(input())

hour = math.floor(S/3600)
min = math.floor((S-hour*3600)/60)
sec =  S - hour*3600 - min*60

print(str(hour)+":"+str(min)+":"+str(sec))
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n = int(input())
    x = list(input())
    for i in range(n):
        x[i] = int(x[i])
    for i in range(n):
        y = copy.deepcopy(x)
        y[i] = 1-y[i]
        ans = 1
        while True:
            A = 0
            B = sum(y)
            for i in range(len(y)):
                A += y[i]*pow(2,len(y)-i-1)
            k = A%B
            if k == 0:
                break
            ans += 1
            yy = []
            while k != 0:
                yy.append(k%2)
                k //= 2
            yy.reverse()
            y = yy
        print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys, math, copy
sys.setrecursionlimit(10**8)

def main():
    n = int(input())
    x = list(input())
    for i in range(n):
        x[i] = int(x[i])
    A0 = 0
    A1 = 0
    B = sum(x)
    for i in range(n):
        if B+1 != 0:
            A0 += x[i]*pow(2,n-i-1,B+1)
            A0 %= B+1
        if B-1 != 0:
            A1 += x[i]*pow(2,n-i-1,B-1)
            A1 %= B-1
    for i in range(n):
        if x[i] == 0:
            BB = B + 1
            AA = A0 + pow(2,n-i-1,BB)
        else:
            BB = B - 1
            if BB == 0:
                AA = 0
            else:
                AA = A1 - pow(2,n-i-1,BB)
        ans = 1
        if BB == 0:
            print(0)
            continue
        while AA%BB != 0:
            AA = AA%BB
            AAA = AA
            BB = 0
            while AAA != 0:
                BB += AAA%2
                AAA //= 2
            ans += 1
        print(ans)
    
if __name__ == "__main__":
    main()
import numpy as np
n,l=map(int,input().split())
a=list(map(int,input().split()))
flag=False;idx=0
for i in range(n-1):
  if a[i]+a[i+1]>=l:
    flag=True
    idx=i
if not Flag:
  print("Impossible")
  exit(0)
print("Possible")
for x in range(idx):
  print(x+1)
for x in reversed(range(idx+1)):
  print(x+1)

### FIXED CODE ###

import numpy as np
n,l=map(int,input().split())
a=list(map(int,input().split()))
flag=False;idx=0
for i in range(n-1):
  if a[i]+a[i+1]>=l:
    flag=True
    idx=i
if not flag:
  print("Impossible")
  exit(0)
print("Possible")
for x in range(idx):
  print(x+1)
for x in reversed(range(idx,n-1)):
  print(x+1)
import math
from functools import reduce

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

n = [int(input()) for _ in range(int(input()))]
print(lcm(*n))


### FIXED CODE ###

from functools import reduce

def gcd(x,y):
    if x % y == 0:
        return y
    return gcd(y, x % y)

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

n = [int(input()) for _ in range(int(input()))]
print(lcm(*n))
from collections import defaultdict

while 1:
    ws, hs, w, h = defaultdict(lambda:0), defaultdict(lambda:0), [], []
    n, m = map(int, raw_input().split())
    if n|m == 0: break

    for i in range(n):
        t = s = input()
        ws[s]+=1
        for pw in reversed(w):
            s+=pw
            ws[s]+=1
        w.append(t)

    for i in range(m):
        t = s = input()
        hs[s]+=1
        for pw in reversed(h):
            s+=pw
            hs[s]+=1
        h.append(t)

    ans = 0
    for w, wn in ws.iteritems():
        for h, hn in hs.iteritems():
            if w == h:
                ans += wn * hn
    print ans

### FIXED CODE ###

from collections import defaultdict

while 1:
    ws, hs, w, h = defaultdict(int), defaultdict(int), [], []
    n, m = map(int, raw_input().split())
    if n|m == 0: break

    for i in range(n):
        t = s = input()
        ws[s]+=1
        for pw in reversed(w):
            s+=pw
            ws[s]+=1
        w.append(t)

    for i in range(m):
        t = s = input()
        hs[s]+=1
        for pw in reversed(h):
            s+=pw
            hs[s]+=1
        h.append(t)

    print sum(ws[a] * hs[a] for a in ws if a in hs)
def tax8(n):
    return list(range(int((n-1)*(25/2))),int((n+1)*(25/2))))
    
def tax10(n):
    return list(range(int((n-1)*(10/1))),int((n+1)*(10/1))))

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

ans = -1

x = []
for i in range(1,a+1):
    if tax8(i) == a:
        x.extend(i)
        
y = []
for i in range(1,b+1):
    if tax10(i) == b:
        y.extend(i)
        
for i in x:
    if i in y:
        if int(i*(2/25)) == int(i*(1/10)):
            ans = i
            break
    
print(ans)

### FIXED CODE ###

def tax8(n):
    return list(range(int((n-1)*(25/2)),int((n+1)*(25/2))))
    
def tax10(n):
    return list(range(int((n-1)*(10/1)),int((n+1)*(10/1))))

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

ans = -1

x = []

x.extend(tax8(a))
        
y = []

y.extend(tax10(b))

for i in x:
    if i in y:
        if int(i*(27/25))-i == a and int(i*(11/10))-i == b:
            ans = i
            break
    
print(ans)
def main_C1():

  N = int(input())
  a = [[int(item) for item in input().split()] for i in range(N)]
  
  dp = [[0, 0, 0] for i in range(N+1)]

  for i in range(N):
    for j in range(3):
      for k in range(3):
        if j == k:
          continue
        dp[i+1][k] = max(dp[i+1][k], dp[i][j] + a[i][k])
  
  print(max(dp[-1]))

if __name__ == "__main__":
  main_C1()
  # print(list(input_gen()))


### FIXED CODE ###

N = int(input())
h = [int(i) for i in input().split()]

inf = float("inf")
cost = [inf]*N

cost[0] = 0
for i in range(1, N):
  cost[i] = min(cost[i], cost[i-1] + abs(h[i] - h[i-1]))
  
  if i - 2 >= 0:
    cost[i] = min(cost[i], cost[i-2] + abs(h[i] - h[i-2]))

print(cost[-1])
N, M = map(int, input().split())
ans = [-1 for _ in range(N)]
if N ==1:
  ans = 0
  clis = []
  for _ in range(M):
    s, c = map(int, input().split())
    clis.append(c)
  if len(set(clis)) == 1:
    print(clis[0])
  elif len(set(clis)) == 0:
    print(0)
  else:
    print(-1)
     
else:
  for _ in range(M):
    s, c = map(int, input().split())
    if s == 1 and c == 0:
      print(-1)
      exit()
    if ans[s-1] == c or ans[s-1] == -1:
      ans[s-1] = c
    else:
      print(-1)
      exit()

ans[0] = max(1, ans[0])
answer = ''
for k in range(N):
  if ans[k] == -1:
    answer += '0'
  else:
    answer += str(ans[k])
print(answer)


### FIXED CODE ###

N, M = map(int, input().split())
ans = [-1 for _ in range(N)]
if N ==1:
  ans = 0
  clis = []
  for _ in range(M):
    s, c = map(int, input().split())
    clis.append(c)
  if len(set(clis)) == 1:
    print(clis[0])
    exit()
  elif len(set(clis)) == 0:
    print(0)
    exit()
  else:
    print(-1)
    exit()
else:
  for _ in range(M):
    s, c = map(int, input().split())
    if s == 1 and c == 0:
      print(-1)
      exit()
    if ans[s-1] == c or ans[s-1] == -1:
      ans[s-1] = c
    else:
      print(-1)
      exit()

ans[0] = max(1, ans[0])
answer = ''
for k in range(N):
  if ans[k] == -1:
    answer += '0'
  else:
    answer += str(ans[k])
print(answer)
def create_hole(A: List, b:List):

    N = len(A)
    Hole = [[0 for i in range(N)] for j in range(N)]
    for i in range(3):
        for j in range(3):
            for value in b:
                if A[i][j] == value: Hole[i][j] = 1

    return Hole


def check_bingo(H: List):

    N = len(H)
    rowsum = sum([sum(row) == N for row in H])
    colsum = sum([sum(row) == N for row in map(list, zip(*H))])
    digsum = sum([H[i][i] for i in range(N)]) == N
    tdigsum = sum([H[i][N-i-1] for i in range(N)]) == N

    return rowsum + colsum + digsum + tdigsum > 0


def resolve():

    A = [list(map(int, input().split())) for i in range(3)]
    N = int(input())
    b = [int(input()) for i in range(N)]
    print('Yes' if check_bingo(create_hole(A, b)) else 'No')
    
resolve()

### FIXED CODE ###

def create_hole(A: list, b:list):

    N = len(A)
    Hole = [[0 for i in range(N)] for j in range(N)]
    for i in range(3):
        for j in range(3):
            for value in b:
                if A[i][j] == value: Hole[i][j] = 1

    return Hole


def check_bingo(H: list):

    N = len(H)
    rowsum = sum([sum(row) == N for row in H])
    colsum = sum([sum(row) == N for row in map(list, zip(*H))])
    digsum = sum([H[i][i] for i in range(N)]) == N
    tdigsum = sum([H[i][N-i-1] for i in range(N)]) == N

    return rowsum + colsum + digsum + tdigsum > 0


def resolve():

    A = [list(map(int, input().split())) for i in range(3)]
    N = int(input())
    b = [int(input()) for i in range(N)]
    print('Yes' if check_bingo(create_hole(A, b)) else 'No')
    
resolve()
n=input();a=[];b="SHCD"
for i in range(4*13):a.append(b[i/13]+" "+str(i%13+1))
for i in range(n):a.remove(raw_input())
for i in c:print i

### FIXED CODE ###

j=input();i=52;a=[""]*i
while i:i-=1;a[i]="SHCD"[i/13]+" "+str(i%13+1)
while j:j-=1;a.remove(raw_input())
for i in a:print i
n=input().slipt()
print(int(n[2]*(n[0]-2)-(n[1]*n[0]-2)+1))

### FIXED CODE ###

n,a,b=map(int,input().split())
if n>1 and b>=a or n==1 and a==b: 
    print ((n-2)*(b-a)+1);
else:
    print ("0");
s = list(input())
ans = [sum(map(int, s)), 9*(len(s)-1) + int(s[0]-1)]
print(max(ans))

### FIXED CODE ###

s = list(input())
ans = [sum(map(int, s)), 9 * (len(s) - 1) + int(s[0]) - 1]
print(max(ans))
#B - Substring 
S = str(input())
T = str(input())
i = 0
j = 0

Slen = len(S)
Tlen = len(T)
change_min = Tlen

for i in range(Slen - Tlen):
    diff = 0
    for j in range(Tlen):
        if S[i] != T[i + j]:
            diff += 1
    change_min = min(change_min,diff)

# 出力
print(change_min)

### FIXED CODE ###

#B - Substring 
S = str(input())
T = str(input())
i = 0
j = 0

Slen = len(S)
Tlen = len(T)
change_min = Tlen

for i in range(Slen - Tlen + 1):
    diff = 0
    for j in range(Tlen):
        if T[j] != S[i + j]:
            diff += 1
    change_min = min(change_min,diff)

# 出力
print(change_min)
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort(key=lambda x:x[0])
import numpy as np
fd=np.zeros(xh[-1][0]+1,np.int64) # fd[i]:座標iにいるモンスターに与えたダメージ
ans=0
for x,h in xh:
  if h-fd[x]<=0:
    continue
  else:
    c=(h-fd[x]+a-1)//a
    fd[x:min(xh[-1][0]+1,x+2*d+1)]+=c*a
    ans+=c
print(ans)


### FIXED CODE ###

n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort(key=lambda x:x[0])
from collections import deque
minusd=deque()
nowd=0
ans=0
for x,h in xh:
  while minusd and minusd[0][1]<=x:
    d_,_=minusd.popleft()
    nowd-=d_
  tmp=max(0,(h-nowd+a-1)//a)
  ans+=tmp
  nowd+=tmp*a
  minusd.append([tmp*a,x+2*d+1])
  #print(ans,nowd)
print(ans)
d,t,s=map(int,input(.split())
if d/s<=t:
	print("YES")
else:
	print("NO")

### FIXED CODE ###

d,t,s = map(int,input().split())
if t*s >= d:
    print("Yes")
else:
    print("No")
import numpy as np
N = int(input())
x = [int(i) for i in input().split() ]

each = 0
loss
ll = []

for(int i=min(x); i<max(x); i++):
  for j in range(len(x)):
    each = np.power((x[j]-i), 2)
    loss += each
  ll.append(loss)
  
print(min(each))

### FIXED CODE ###

import numpy as np
N = int(input())
x = [int(i) for i in input().split() ]

each = 0
loss = 0
ll = []

for k in range(min(x), max(x)+1):
      for j in range(len(x)):
            each = np.power((x[j]-k), 2)
            loss += each
      ll.append(loss)
      loss = 0
  
print(min(ll))
import sys
sys.setrecursionlimit(10*7)

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

dp = [float("inf")]*n

def rec(i):#全探索+メモ化
    if dp[i] != float("inf"):
        return dp[i]
    if i <= 0:
        return 0
    else:
        for l in range(1,k+1):
            if i-l < 0:continue
            dp[i] = min(dp[i],rec(i-l) + abs(h[i]-h[i-l]))
    return dp[i]

print(rec(n-1))
            

### FIXED CODE ###

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

dp = [float("inf")]*n

#初期条件
dp[0] = 0

#漸化式
for i in range(1,n):
    for l in range(1,k+1):
        if i-l < 0:continue
        dp[i] = min(dp[i],dp[i-l] + abs(h[i-l]-h[i]))

print(dp[n-1])
# -*- coding: utf-8 -*-
# 整数の入力
n=int(input())
a=input().split()
counter=0
S=a[0]
# 出力
for i in range(1,n):
  S+=a[i]
  if S<0 and S+int(a[i])<=0:
    counter+=-S-int(a[i])+1
    a[i]=-S+1
  elif S>0 and S+int(a[i])>=0:
    counter+=S+int(a[i])+1
    a[i]=-S-1
print(counter)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
n=int(input())
a=input().split()
b=a[:]
c=a[:]
# a[0]の符号をそのままにした場合の計算
counter_1=0
S=int(a[0])
for i in range(1,n):
  if S<0 and S+int(a[i])<=0:
    counter_1+=-S-int(a[i])+1
    a[i]=-S+1
  elif S>0 and S+int(a[i])>=0:
    counter_1+=S+int(a[i])+1
    a[i]=-S-1
  S+=int(a[i])
# a[0]を1に変えた場合の計算
counter_2=abs(int(b[0])-1)
b[0]=1
S=b[0]
for i in range(1,n):
  if S<0 and S+int(b[i])<=0:
    counter_2+=-S-int(b[i])+1
    b[i]=-S+1
  elif S>0 and S+int(b[i])>=0:
    counter_2+=S+int(b[i])+1
    b[i]=-S-1
  S+=int(b[i])
# a[0]を-1に変えた場合の計算
counter_3=abs(int(c[0])+1)
c[0]=-1
S=c[0]
for i in range(1,n):
  if S<0 and S+int(c[i])<=0:
    counter_3+=-S-int(c[i])+1
    c[i]=-S+1
  elif S>0 and S+int(c[i])>=0:
    counter_3+=S+int(c[i])+1
    c[i]=-S-1
  S+=int(c[i])
print(min(counter_1,counter_2,counter_3))
from collections import deque
N,M = map(int,input().split())
P = list(map(int,input().split()))
P.insert(0,0)
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
A = []
hist = [0 for _ in range(N+1)]
for i in range(1,N+1):
    if hist[i]==0:
        C = [i]
        hist[i]=1
        que = deque([i])
        while que:
            x = que.popleft()
            for y in G[x]:
                if hist[y]==0:
                    que.append(y)
                    C.append(y)
                    hist[y]=1
        C = sorted(C)
        A.append(C)
cnt = 0
for C in A:
    B = []
    for c in C:
        B.append(P[c])
    B = sorted(B)
    cur = 0
    for i in range(len(C)):
        if C[i]==B[cur]:
            cnt += 1
            cur += 1
        elif C[i]<B[cur]:
            continue
        elif C[i]>B[cur]:
            while C[i]>B[cur]:
                cur += 1
            if B[cur]==C[i]:
                cnt += 1
            else:
                continue
print(cnt)

### FIXED CODE ###

from bisect import bisect_left
def rt(i):
    while i!=G[i][0]:
        i = G[i][0]
    return i
N,M = map(int,input().split())
P = list(map(int,input().split()))
P.insert(0,0)
G = {i:[i,1] for i in range(1,N+1)}
for _ in range(M):
    x,y = map(int,input().split())
    rx = rt(x)
    ry = rt(y)
    if rx!=ry:
        if G[rx][1]>=G[ry][1]:
            G[ry][0] = rx
            G[rx][1] += G[ry][1]
        else:
            G[rx][0] = ry
            G[ry][1] += G[rx][1]
hist = [0 for _ in range(N+1)]
A = {}
for i in range(1,N+1):
    ri = rt(i)
    if hist[ri]==0:
        A[ri] = []
        hist[ri] = 1
    A[ri].append(i)
cnt = 0
for a in A:
    B = []
    for i in range(len(A[a])):
        B.append(P[A[a][i]])
    B = sorted(B)
    B.append(10**8)
    cur = 0
    for i in range(len(A[a])):
        if A[a][i]==B[cur]:
            cnt += 1
        elif A[a][i]<B[cur]:
            continue
        else:
            cur = bisect_left(B,A[a][i])
            if B[cur]==A[a][i]:
                cnt += 1
                cur += 1
print(cnt)
import sys
input = sys.stdin.readline

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

num=[i for i in range(1,101)]
for i in p:
    num[i-1]=0

num.sort()
# print(num)
min=1000
for i in num:
    if min>abs(x-i):
        min=abs(x-i)
        ans=i
print(ans)import sys
input = sys.stdin.readline

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

num=[i for i in range(1,101)]
for i in p:
    num[i-1]=0

num.sort()
# print(num)
min=1000
for i in num:
    if min>abs(x-i):
        min=abs(x-i)
        ans=i
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

# num=[i for i in range(1,101)]
# for i in p:
#     num[i-1]=-1

# num.append(0)
# num.append(101)
# num.sort()
# while True:
#     if num[0]!=-1:
#         break
#     num.pop(0)
# print(num)

# min=1000
# for i in num:
#     if min>abs(x-i):
#         min=abs(x-i)
#         ans=i
# print(ans)

i=0
while True:
    if not x-i in p :
        print(x-i)
        break
    elif not x+i in p:
        print(x+i)
        break
    i+=1

# num=[]
# for i in range(101):
#     num.append(x-i)
#     num.append(x+i)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

K = int(input())
S = input()
n = len(S)
ans = 0
for i in range(K+1):
    ans += (cmb(i+n-1, n-1, mod) * pow(25, i) * pow(26, (K-i))) % mod
print(ans%mod)

### FIXED CODE ###

# F - Strivore
import sys
MOD = 10**9+7
K = int(input())
S = input()
l = len(S)
ans = 0
 
tmp = pow(26,K,MOD)
ans = tmp
waru = pow(26,-1,MOD)
 
for i in range(1,K+1):
    tmp = (tmp*25*waru)%MOD
    tmp = (tmp*(l-1+i)*pow(i,-1,MOD))%MOD
    ans = (ans+tmp)%MOD
 
print(ans)
N = int(input())
S = []
for _ in range(N): S.append(input()))

print('AC x', S.count('AC'))
print('WA x', S.count('WA'))
print('TLE x', S.count('TLE'))
print('RE x', S.count('RE'))


### FIXED CODE ###

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

print('AC x', S.count('AC'))
print('WA x', S.count('WA'))
print('TLE x', S.count('TLE'))
print('RE x', S.count('RE'))
a,b=map(int,input().split())
if a>9:
  print(b)
else:
  print(b+(100＊(10-a))

### FIXED CODE ###

a,b=map(int,input().split())
if a>9:
  print(b)
else:
  print(b+(100*(10-a)))
import math
def solve(K, N, A, length):
    s = 0
    for i in range(N):
        if A[i] > length:
            s += int(A[i] / length)
    return K >= s

# 一本ならナイーブには1/2を繰り返すのが最小になりそうだけど5とかだと1/2, (1/2, 1/2)で次4回切らないと中途半端に長いのが残ってしまう
# 複数本なら一番長いのを常に半分に切れば良さそう？
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
A.sort()
ok = A[-1]
ng = A[0]
while abs(ok - ng) > 1:
    mid = (ok + ng) / 2
    if solve(K, N, A, mid):
        ok = mid
    else:
        ng = mid

print(math.ceil(mid))

### FIXED CODE ###

import math
def is_ok(K, N, A, length):
    s = 0
    for i in range(N):
        if A[i] > length:
            s += math.ceil(A[i] / length)-1
    return K >= s


N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
if K == 0:
    print(max(A))
    exit()
ok = max(A)
ng = 0
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if is_ok(K, N, A, mid):
        ok = mid
    else:
        ng = mid

print(math.ceil(ok))
a, b ,c = map(int, raw_input().split())
     
if (a < b < c):
 print a b c
elif (a < c < b):
 print a c b
elif (b < a < c):
 print b a c
elif (b < c < a):
 print b c a
elif (c < a < b):
 print c a b
elif (c < b < a):
 print c b a

### FIXED CODE ###

n = map(int,raw_input().split())
n.sort()
print n[0], n[1] , n[2]
s = input()
oddone = ''
evenone = ''

for i in range(len(s)):
    if i % 2 == 1:
        oddone += '1'
        evenone += '0'
    else:
        oddone += '0'
        evenone += '1'

def diffCount(s1, s2):
    count = 0
    if len(s1) != len(s2):
        print('error')
        return

    for i in range(len(s1)):
        if s1[i] != s2[i]:
            count += 1

    return count

print(min(diffCount(s, oddone), diffCount(s, evenone)))



### FIXED CODE ###

s = input()
oddone = ''
evenone = ''

for i in range(len(s)):
    if i % 2 == 1:
        oddone += '1'
        evenone += '0'
    else:
        oddone += '0'
        evenone += '1'

def diffCount(s1, s2):
    count = 0
    if len(s1) != len(s2):
        print('error')
        return

    for i in range(len(s1)):
        if s1[i] != s2[i]:
            count += 1

    return count

print(min(diffCount(s, oddone), diffCount(s, evenone)))
N, M = map(int,input().split())
tree = {}

for i in range(M):
    a, b, c = map(int, input().split())
    v= tree.get(a,[])
    v.append([b, c])
    tree[a] = v

def has_loop(tree):
    pass

m = []
def cost(v, c, visited):
    if v in visited:
        print('inf')
        exit()
    b = tree.get(v, None)
    if b is None:
        return 
    elif len(b) == 1 and tree.get(b[0][0],None) == None:
        j = c+b[0][1]
        m.append(j)
    else:
        for b, c2 in b: 
            cost(b, c+c2, visited + [v])

if has_loop(tree):
    print('inf')
    exit()

cost(1, 0, [])
print(max(m))


### FIXED CODE ###

A,B,C = map(int,input().split())
if A <= C and C <= B:
  print('Yes')
else:
  print('No')
x, y = map(int, input().split())
list1 = [1, 3, 5, 7, 8, 10, 12]
list2 = [4, 6, 9, 11]
list3 = [2]
if (x in list1 and y in list1)　or (x in list2 and y in list2) or (x in list3 and y in list3):
  print('Yes')
else:
  print('No')
  

### FIXED CODE ###

x, y = map(int, input().split())
list1 = [1, 3, 5, 7, 8, 10, 12]
list2 = [4, 6, 9, 11]
list3 = [2]
A = x in list1 and y in list1
B = x in list2 and y in list2
C = x in list3 and y in list3
if A == True or B == True or C == True:
  print('Yes')
else:
  print('No')
input()
a = [int(x) for x in iput().split()]
if(len(set(a)) < len(a)):
  print('YES')
else:
  print('NO')

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
if(n > len(set(a))):	print('NO')
else:	print('YES')
n, m  = map(int, input().split())
arr = []
for i in range(n):
    a, b = map(int, input().split())
    arr.append([a, b])
a.sort()
ans = 0
idx = 0
while True:
    if m <= 0:
        break
    ans += arr[idx][0] * min(arr[idx][1], m)
    m -= min(arr[idx][1], m)
    idx += 1
print(ans)


### FIXED CODE ###

n, m  = map(int, input().split())
arr = []
for i in range(n):
    a, b = map(int, input().split())
    arr.append([a, b])
arr.sort()
ans = 0
idx = 0
while True:
    if m <= 0:
        break
    ans += arr[idx][0] * min(arr[idx][1], m)
    m -= min(arr[idx][1], m)
    idx += 1
print(ans)