Harryxun/stf_run huggingface dataset:
# https://atcoder.jp/contests/abc138/tasks/abc138_d

import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, q = input_int_list()
    cnt = [0] * (n + 1)  # 1-indexed
    tree = defaultdict(list)

    for _ in range(n - 1):
        a, b = input_int_list()
        tree[a].append(b)

    def tree_walk(root, x):
        cnt[root] += x
        for node in tree[root]:
            tree_walk(node, x)

    for _ in range(q):
        p, x = input_int_list()
        tree_walk(p, x)

    print(*cnt[1:])
    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import defaultdict
import sys
sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, q = input_int_list()
    cnt = [0] * (n + 1)  # 1-indexed
    tree = defaultdict(list)

    for _ in range(n - 1):
        a, b = input_int_list()
        tree[a].append(b)
        tree[b].append(a)

    # 遅延評価をする O(q)
    for _ in range(q):
        p, x = input_int_list()
        cnt[p] += x

    # 遅延評価（DFS）O(n)
    stack = [(1, 0)]
    visited = set([1])
    while stack:
        e, add = stack.pop()
        cnt[e] += add
        for node in tree[e]:
            if node not in visited:
                visited.add(node)
                stack.append((node, cnt[e]))

    print(" ".join([str(i) for i in cnt[1:]]))
    return


if __name__ == "__main__":
    main()
import numpy as np



def ii():
    return int(input())




def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l



N = ii()

P = lvi(N)

'''
P = []
for _ in range(N):
    p = ii()
    P.append(p -1)

print(P)
'''

#fill( Q, Q + N, 0)
Q = [0 for i in range(N)]


#print( 'Q', Q)

for i in range(1, N):
    Q[P[i - 1]] = i


maxcnt = 1
cnt = 1

print( 'Q', Q)

for i in range(1, N):
    if Q[i] > Q[i - 1]:
        cnt += 1
    else:
        cnt = 1

    maxcnt = max( maxcnt, cnt)


print(N - maxcnt)


### FIXED CODE ###

import numpy as np

def ii():
    return int(input())


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


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


N = ii()
P = []
for _ in range(N):
    p = ii()
    P.append(p-1)

Q = [0 for i in range(N)]
for i in range(N):
    Q[P[i]] = i

maxcnt = 1
cnt = 1
for i in range(1, N):
    if Q[i] > Q[i-1]:
        cnt += 1
    else:
        cnt = 1

    maxcnt = max(maxcnt, cnt)

print(N - maxcnt)
n,m = map(int,input().split())

q = []

for i in range(m):
    l,r,d = map(int,input().split())
    if l < r:
        q.append((l,r,d))
    else:
        q.append((r,l,-d))
q.sort(key=lambda x:x[:2],reverse=True)

#print(q)
arr = [0]+[" "]*(n)

while q!=[]:
    l,r,d = q[-1]
    if arr[l] == " ":
        flag = False
        for j in range(len(q)-1,-1,-1):
            if q[j][0]==l:
                if arr[q[j][1]]!=" ":
                    arr[l] = arr[q[j][1]] - arr[q[j][2]]
                    flag = True
                    break
            else:
                break
        if not flag:
            arr[l] = 0
    if arr[r] == " ":
        arr[r] = arr[l]+d
    elif arr[r] !=arr[l]+d:
        print("No")
        exit(0)
    q.pop()
print("Yes")


### FIXED CODE ###

import queue
n,m = map(int,input().split())

data =[0]
access = [False]*(n+1)
dis = [0]+[" "]*(n)
q = queue.Queue()
for i in range(n):
    data.append([])

for i in range(m):
    l,r,d = map(int,input().split())

    data[l].append((r,d))
    data[r].append((l,-d))

for i in range(1,n+1):
    data[i].sort(reverse=True)

for i in range(1,n+1):
    if data[i]!=[] and not access[i]: 
        q.put(i)
        access[i] = True
        dis[i] = 0
        while not q.empty():
            l = q.get()

            while data[l]:
                r,d = data[l].pop()
                data[r].remove((l,-d))
                if access[r]:
                    if dis[r] ==dis[l]+d:
                        continue
                    else:
                        print("No")
                        exit(0)
                else:
                    access[r] = True
                    dis[r] = dis[l]+d
                    q.put(r)
print("Yes")
d,t,s=int(input())
if S*t >= d:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

D,T,S = map(int,input().split())

if D/S > T:
    print("No")
else:
    print("Yes")
N = int(input())
if N % 2 == 1:
  print(0)
else:
  # i = 5 で始めると奇数が入る
  i = 10
  result = 0
  while N > i:
    result += N//i
    i *= 5
print(result) 


### FIXED CODE ###

N = int(input())
if N % 2 == 1:
  print(0)
else:
  i = 10
  result = 0
  while N >= i:
    result += N//i
    i *= 5
  print(result)
import sys

def is_center(x, y, P):
  H = [abs(x-p[0]) + abs(y-p[1]) + p[2] for p in P]
  return len(set(H)) == 1

def main():
  input = sys.stdin.readline
  N = int(input())
  P = [[0, 0, 0] for _ in range(N)]
  for i in range(N):
    x, y, h = map(int, input().split())
    P[i][0], P[i][1], P[i][2] = x, y, h
  for i in range(101):
    for j in range(101):
      if is_center(i, j, P):
        h = abs(i - P[0][0]) + abs(j - P[0][1]) + P[0][2]
        ans = '{} {} {}'.format(i, j, h)
        break
 
  print(ans)


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys

def is_center(x, y, P):
  H = [abs(x-p[0]) + abs(y-p[1]) + p[2] for p in P if p[2] != 0]
  return H


def center(C, P):
  for c in C:
    check = [p[2] == max(c[2] - abs(p[0] - c[0]) - abs(p[1] - c[1]), 0) for p in P]
    if all(check):
      return '{} {} {}'.format(c[0], c[1], c[2])

def main():
  input = sys.stdin.readline
  N = int(input())
  P = [[0, 0, 0] for _ in range(N)]

  for i in range(N):
    x, y, h = map(int, input().split())
    P[i][0], P[i][1], P[i][2] = x, y, h

  C = []
  for i in range(101):
    for j in range(101):
      H = is_center(i, j, P)
      if len(set(H)) == 1:
        C.append([i, j, H[0]])
  
  ans = center(C, P)
  print(ans)


if __name__ == '__main__':
  main()
n=int(input())
s=list(input())
count=0
for i in range(n):
  if s[i]== 'A':
    if (s[i+1]) =='B':
      if (s[i+2])=='C':
        count+=1
print(count)   
    


### FIXED CODE ###

n=int(input())
s=list(input())
count=0
for i in range(n-2):
  if s[i]== 'A':
    if (s[i+1]) =='B':
      if (s[i+2])=='C':
        count+=1
print(count)
#!/usr/bin/env python

def func():
    n,m = [int(i) for i in input().split(" ")]
    pibot = 10**(m-1)
    dic = {}

    for i in range(m):
        tmp = [int(i) for i in input().split(" ")]

        if tmp[0] not in dic.keys():
            dic[tmp[0]] = tmp[1]
        else:
            if dic[tmp[0]] != tmp[1]:
                print("-1")
                return

    a = [0] * m
    for key in dic.keys():
        a[key-1] = dic[key]

    tmp_s = ""
    for i in a:
        tmp_s += str(i)

    if int(tmp_s) < pibot:
        tmp_s = "-1"

    print(tmp_s)

if __name__ == "__main__":
    func()

### FIXED CODE ###

#!/usr/bin/env python

n, m = input().split(" ")
n = int(n)
m = int(m)
s_len = []
c_len = []
dig = 10**(n-1)

for i in range(m):
    tmp = input().split(" ")
    s_len.append(int(tmp[0]))
    c_len.append(int(tmp[1]))

for i in range(0, dig*10):
    flag = False
    if len(str(i)) < n:
        continue
    for j,s in enumerate(s_len):
        if str(i)[s-1] != str(c_len[j]) and flag == False:
            flag = True
            break
    if flag==False:
        print(i)
        exit()

print("-1")
N = input()
A = list(map(int, input().split()))

answer = 1
if 0 in A:
  print(0)
else:
  for i in A:
    answer *= i
    if answer > 10**18:
      print(-1)
      exit()
	print(answer)

### FIXED CODE ###

a = list(map(int, input().split()))
print(a[0] * a[1])
import bisect
import sys
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))

if N == 1:
  print (int(A[0] // 2 ** M))
  sys.exit()
while M:
  A[-1] //= 2
  if A[-1] < A[-2]:
    d = A[-1]
    b = bisect.bisect(A,d) 
    A[b+1:] = A[b:-1]
    A[b] = d
  M -= 1
print (sum(A))


### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(A)

while M:
  m = heapq.heappop(A) * (-1)
  heapq.heappush(A, (-1) * (m // 2))
  M -= 1
print (sum(A) * (-1))
N,M = map(int,input().split())

P = []
Y = []

for i in range(M):
    p,y = map(int,input().split())
    P.append(p)
    Y.append(y)

A = [0]*M
C = [0]*M

B = [0]*M
for i in range(M):
    B[i] = (Y[i]-1)*100000+i

B.sort()

for i in range(M):
    d = B[i] % 100000
    b = B[i] // 100000
    k = P[d]

    C[d] = A[k]
    A[k] += 1

for i in range(M):
    print('%06d%06d' % (P[i],C[i]+1))


### FIXED CODE ###

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

P = [0]*M
Y = [0]*M

for i in range(M):
    P[i],Y[i] = map(int,input().split())

A = [0]*N
C = [0]*M

B = [0]*M
for i in range(M):
    B[i] = Y[i]*100000+i

B.sort()

for i in range(M):
    d = B[i] % 100000
    k = P[d] - 1

    C[d] = A[k]
    A[k] += 1

for i in range(M):
    print('%06d%06d' % (P[i],C[i]+1))
X = int(input())
b = 0.0
c = True

while c:
    if ((X + b**5)**0.2).is_integer():
        c = False
        a = int(((X + b**5)**0.2))
    elif b == 0:
        b = 1.0
    elif b > 0:
        b = -1.0*b
    else:
        b = -1*b + 1
        
print(a, int(b))

### FIXED CODE ###

X = int(input())

c = 1
result = False


while not result:
    for i in range(c):
        a = c -i
        b = i
        if a**5 - b**5 == X:
            result = True
            A = a
            B = b
            break
    if result == True:
        break
    for i in range(c):
        b = c - i
        a = - i
        if a**5 - b**5 == X:
            result = True
            A = a
            B = b
            break
    if result == True:
        break
    for i in range(c):
        a = -c+i
        b = -i
        if a**5 - b**5 == X:
            result = True
            A = a
            B = b
            break
    if result == True:
        break
    for i in range(c):
        a = i
        b = -c + i
        if a**5 - b**5 == X:
            result = True
            A = a
            B = b
            break
    if result == True:
        break
    c += 1

print(A, B)
# https://atcoder.jp/contests/abc068/tasks/abc068_b


def two_factor(x):
    cnt = 0
    while x % 2 == 0:
        cnt += 1
        x //= 2
    return cnt


N = int(input())
a = map(two_factor, range(1, N + 1))
max_cnt = max(a)
print(a.index(max_cnt) + 1)


### FIXED CODE ###

# https://atcoder.jp/contests/abc068/tasks/abc068_b


def two_factor(x):
    cnt = 0
    while x % 2 == 0:
        cnt += 1
        x //= 2
    return cnt


N = int(input())
a = list(map(two_factor, range(1, N + 1)))
max_cnt = max(a)
print(a.index(max_cnt) + 1)
a = int(input())
b = int(input())
c = int(input())
print(c, a, b)

### FIXED CODE ###

A,B,C= map(int,input().split())
print(C,A,B)
import math
a, b, x = map(int, input().split())
 
h = x / (a * a) #height 
if h > b / 2:
  shahen = 4 * (b - x/(a * a) * (b - x/(a * a))) + a * a
  sin = a / (math.sqrt(shahen))
  print(90 - math.degrees(math.asin(sin)))
elif h == b / 2:
  print(45.0000000000)
else:
  shahen = 4 * x * x + (a * a * a * a) * b * b
  sin = 2 * x / (math.sqrt(shahen))
  print(90 - math.degrees(math.asin(sin)))


### FIXED CODE ###

a, b = map(int, input().split())
 
if a <= 9 and a >= 1 and b <= 9 and b >= 1:
  print(a * b)
else :
  print(-1)
def getMax(d,n,c):
    global bs
    if len(d[n])==0:
        bs=max(bs,c)

    for k in d[n]:
        getMax(d,k,c+1)

n,m=map(int,input().split())
d={}
for j in range(1,n+1):
    d[j]=[]
for i in range(m):
    a,b=map(int,input().split())
    d[a].append(b)
bs=-1
for i in range(1,n+1):
    c=0
    getMax(d,i,c)
print(bs)

### FIXED CODE ###

import sys

sys.setrecursionlimit(20000)


def getMax(d, n):
    if len(d[n]) == 0:
        return 0
    if not dp[n] == -1:
      
        return dp[n]
    for k in d[n]:
        dp[n] = max(dp[n], 1 + getMax(d, k))
    return dp[n]


n, m = map(int, input().split())
d = {}
dp = [-1 for _ in range(n + 1)]
for j in range(1, n + 1):
    d[j] = []
for i in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
bs = -1
for i in range(1, n + 1):
    bs = max(bs, getMax(d,i))
print(bs)
x=int(input())
l=[]
for s in range(x):
  for t in range(2,x):
    if s**t<=x:
      l.append(s**t)
print(max(l))

### FIXED CODE ###

x=int(input())
l=[]
for i in range(1,40):
  for j in range(2,40):
    if i**j<=x:
      l.append(i**j)
print(max(l))
n = input()
if n >= 1000:
    ans = "ABD"
else:
    ans = "ABC"
print(ans)

### FIXED CODE ###

n = int(input())
if n >= 1000:
    ans = "ABD"
else:
    ans = "ABC"
print(ans)
a, b = map(input(), input())
print a * b, 2 * a + 2 * b

### FIXED CODE ###

a, b = map(int, raw_input().split())
print a * b, 2 * a + 2 * b
record = sorted([input() for i in range(int(input().split()[1]))])
print("".join(record))

### FIXED CODE ###

n,l = map(int,input().split())
s = sorted([input() for i in range(n)])
print(*s,sep="")
N = float(input())

if N==0:
  print(0)
else:
q = N
r_s = []

while q!=1:
  hoge = (q-1) / (-2)
  if hoge.is_integer():
    r = int(1)
    q = float(hoge)
  else:
    r = int(0)
    q = float(q/(-2))
  
  r_s.append(r)
r_s.append(1)
r_s = r_s[::-1]

for i in range(len(r_s)):
  print(r_s[i], end="")


### FIXED CODE ###

N = float(input())

if N==0:
  print(0)
else:
  q = N
  r_s = []

  while q!=1:
    hoge = (q-1) / (-2)
    if hoge.is_integer():
      r = int(1)
      q = float(hoge)
    else:
      r = int(0)
      q = float(q/(-2))
  
    r_s.append(r)
  r_s.append(1)
  r_s = r_s[::-1]

  for i in range(len(r_s)):
    print(r_s[i], end="")
N, M = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
class UnionFind:
  def __init__(self, n):
    self.table = [-1 for _ in range(n)]
    
  def root(self, x):
    if self.table[x] < 0:
      return x
    else:
      return self.table[x] = self.root(self.table[x])
  
  def unite(self, x, y):
    s1, s2 = self.root(x), self.root(y)
    if s1 != s2:
      if self.table[s1] != self.table[s2]:
        if self.table[s1] < self.table[s2]:
          self.table[s2] = s1
        else:
          self.table[s1] = s2
      else:
        self.table[s1] += -1
        self.table[s2] = s1
    return
  
  def find Set(self, x, y):
    return self.root(x) == self.root(y)
uf = UnionFind(N)
for i in range(M):
  px, py = map(int, input().split())
  px -= 1
  py -= 1
  uf.unite(px, py)
ans = 0
for i, v in enumerate(p):
  if uf.findSet(i,v):
    ans += 1
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
class UnionFind:
  def __init__(self, n):
    self.table = [-1 for _ in range(n)]
    
  def root(self, x):
    if self.table[x] < 0:
      return x
    else:
      self.table[x] = self.root(self.table[x])
      return self.table[x]
  
  def unite(self, x, y):
    s1, s2 = self.root(x), self.root(y)
    if s1 != s2:
      if self.table[s1] != self.table[s2]:
        if self.table[s1] < self.table[s2]:
          self.table[s2] = s1
        else:
          self.table[s1] = s2
      else:
        self.table[s1] += -1
        self.table[s2] = s1
    return
  
  def findSet(self, x, y):
    return self.root(x) == self.root(y)
uf = UnionFind(N)
for i in range(M):
  px, py = map(int, input().split())
  px -= 1
  py -= 1
  uf.unite(px, py)
ans = 0
for i, v in enumerate(p):
  if uf.findSet(i,v):
    ans += 1
print(ans)
a,b,c = map(int,input().split())
k = int(input())
ans = max(a,b,c)
for i in range(k):
  ans = ans×2
print(ans)


### FIXED CODE ###

a,b,c = map(int,input().split())
k = int(input())
ans = max(a,b,c)
for i in range(k):
  ans = ans + ans
print(ans+min(a,b,c)+a+b+c-max(a,b,c)-min(a,b,c))
def main():
    A=int(input())
    B=int(input())
    C=int(input())
    if (A/B) < C:
        print(int(B/A))
    else:
        print(C)

main()

### FIXED CODE ###

def main():
    A, B, C = map(int, input().split())
    if (B/A) < C:
        print(int (B/A))
    else:
        print(C)

main()
one=list(input())
#print(one)
two=list(input())
if one==[] or two==[]
z={}
for num,i in enumerate(one):
    if i not in z:
        z[i]=[num]
    else:
        z[i].append(num)
p={}
for num,i in enumerate(two):
    if i not in p:
        p[i]=[num]
    else:
        p[i].append(num)
w=[]
#print(p)
#print(z)
for k,v in z.items():
    w.append(v)
o=[]
for k,v in p.items():
    o.append(v)
print("Yes") if w==o else print("No")

### FIXED CODE ###

def main():
    data0 = input()
    data1 = input()

    flag = True
    data_tmp = data0
    count = 0
    len_data = len(data0)
    while True:
        if data0 == "":
            break

        data0 = data0.replace(data0[0], "")
        data1 = data1.replace(data1[0], "")

        if len(data0) != len(data1):
            print('No')
            exit()

    print('Yes')

if __name__ == "__main__":
    main()
n,m = [int(i) for i in input().split()]
a = list(map(int,input().split()))

match = [0,2,5,5,4,5,6,3,7,6]

dig = [0] * (n+1)

inf = 10**9


for i in range(1,n+1):
    lst = []
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i-mat
        if bef >= 0:
            lst.append(dig[bef])
        if lst:
            dig[i] = max(lst) + 1


ans = ""
def dp(i):
    if i == 0:
        return
    global ans
    maxi = 0
    k = -1
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if bef >= 0:
            if dig[bef] == dig[i]-1 and (dig[bef] > 0 or bef == 0):
                if num > maxi:
                    maxi = num
                    k = bef
    ans += str(maxi)
    if k >=0:
        dp(k)

dp(n)
print(ans)

### FIXED CODE ###

n,m = [int(i) for i in input().split()]
a = list(map(int,input().split()))

import sys
sys.setrecursionlimit(50000)

match = [0,2,5,5,4,5,6,3,7,6]

dig = [0] * (n+1)

inf = 10**9


for i in range(1, n + 1):
    lst = []
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if bef >= 0:
            if bef == 0:
                lst.append(dig[bef])
            else:
                if dig[bef] > 0:
                    lst.append(dig[bef])
        if lst:
            dig[i] = max(lst) + 1


ans = ""


def dp(i):
    k = -1
    if i == 0:
        return
    global ans
    maxi = 0
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if dig[i] == 1:
            if bef == 0:
                maxi = max(maxi, num)
                k = 0
        else:
            if bef >= 0:
                if dig[bef] == dig[i] - 1:
                    if num > maxi:
                        maxi = num
                        k = bef
    ans += str(maxi)
    if k >= 0:
        dp(k)


dp(n)
print(ans)
n, m, x = map(int, input().split())
a=list(map(int,input().split()))

n-x = b

for toll in b:
  if ( n + b in a):
    toll = toll + 1
else:
  print(toll)
  

### FIXED CODE ###

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

ans = 0

for i in a:
  if i < x:
    ans += 1

print(min(ans, m-ans))
N = int(input())
a = list(map(int, input().split()))

from collections import deque
b = deque([])
if len(a) % 2 == 0:
    for i in range(1, N + 1):
        print(b)
        if i % 2 == 0:
            b.appendleft(a[i - 1])
        else:
            b.append(a[i - 1])
else:
    for i in range(1, N + 1):
        print(b)
        if i % 2 == 0:
            b.append(a[i - 1])
        else:
            b.appendleft(a[i - 1])

### FIXED CODE ###

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

from collections import deque
b = deque([])
if len(a) % 2 == 0:
    for i in range(1, N + 1):
        #print(b)
        if i % 2 == 0:
            b.appendleft(a[i - 1])
        else:
            b.append(a[i - 1])
else:
    for i in range(1, N + 1):
        #print(b)
        if i % 2 == 0:
            b.append(a[i - 1])
        else:
            b.appendleft(a[i - 1])

print(' '.join([str(i) for i in b]))
N = int(input())
for A in range(1,9) :
  if N / A < 10 and N % A == 0 :
    print("Yes")
    
    else :
    print("No")
    

### FIXED CODE ###

N = int(input())
number = []
for a in range(1,10):
    for b in range(1,10):
        number.append(b*a)
if N in number :
    print("Yes")
else :
    print("No")
k = int(input())
a,b = map(int, input().sprit())
ans = False
for i in range(a,b+1) :
  if i%k == 0 : 
    ans = True

if ans==True : print('OK')
else : print('NG')
    


### FIXED CODE ###

k = int(input())
a,b = map(int,input().split())
ans = 'NG'
for i in range(a,b+1) :
  if i%k == 0 : 
    ans = 'OK'

print(ans)
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, H = MAP() 
ab = [LIST() for _ in range(N)]

a, b = zip(*ab)
b = list(b)

b.sort()
A = max(a)

B = b[bisect(b, A):][::-1]
B = list(accumulate(B))

if H <= B[-1]:
	print(bisect_left(B, H)+1)
else:
	print(len(B) + ceil((H-B[-1])/A))


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, H = MAP() 
ab = [LIST() for _ in range(N)]

a, b = zip(*ab)
b = list(b)

b.sort()
A = max(a)

B = b[bisect(b, A):][::-1]
if B:
	B = list(accumulate(B))
else:
	B = [0]


if H <= B[-1]:
	print(bisect_left(B, H)+1)
else:
	if B[-1] == 0:
		print(ceil(H/A))
	else:
		print(len(B) + ceil((H-B[-1])/A))
s = input()
n = int(input())
ans=[]
a = "ABCDEFGHIJKLMNOPQRSTUWVXYZABCDEFGHIJKLMNOPQRSTUWVXYZ"
a_list=[]
for j in a:
	a_list.append(j)
for i in range (len(s)):
	ans.append(a_list[int(a_list.index(s[i]))+n])
print("".join(ans))

### FIXED CODE ###


n = int(input())
s = input()
ans=[]
a = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
a_list=[]
for j in a:
	a_list.append(j)
for i in range (len(s)):
	ans.append(a_list[a_list.index(s[i])+n].upper())
print("".join(ans))