Problem:


Score : 400 points

Problem Statement

You are going out for a walk, when you suddenly encounter a monster. Fortunately, you have N katana (swords), Katana 1, Katana 2, …, Katana N, and can perform the following two kinds of attacks in any order:

Wield one of the katana you have. When you wield Katana i (1 ≤ i ≤ N), the monster receives a_i points of damage. The same katana can be wielded any number of times.

Throw one of the katana you have. When you throw Katana i (1 ≤ i ≤ N) at the monster, it receives b_i points of damage, and you lose the katana. That is, you can no longer wield or throw that katana.

The monster will vanish when the total damage it has received is H points or more. At least how many attacks do you need in order to vanish it in total?

Constraints

1 ≤ N ≤ 10^5

1 ≤ H ≤ 10^9

1 ≤ a_i ≤ b_i ≤ 10^9

All input values are integers.

Input

Input is given from Standard Input in the following format:

N H
a_1 b_1
:
a_N b_N

Output

Print the minimum total number of attacks required to vanish the monster.

Sample Input 1

1 10
3 5

Sample Output 1

3

You have one katana. Wielding it deals 3 points of damage, and throwing it deals 5 points of damage. By wielding it twice and then throwing it, you will deal 3 + 3 + 5 = 11 points of damage in a total of three attacks, vanishing the monster.

Sample Input 2

2 10
3 5
2 6

Sample Output 2

2

In addition to the katana above, you also have another katana. Wielding it deals 2 points of damage, and throwing it deals 6 points of damage. By throwing both katana, you will deal 5 + 6 = 11 points of damage in two attacks, vanishing the monster.

Sample Input 3

4 1000000000
1 1
1 10000000
1 30000000
1 99999999

Sample Output 3

860000004

Sample Input 4

5 500
35 44
28 83
46 62
31 79
40 43

Sample Output 4

9



Sample input:
1 10
3 5


Sample output:
3

Submission status: Accepted

Solution code:
N, H = map(int, input().split())

A = []
B = []

for _ in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  

def solve():
  count = 0
  remain = H
  
  B.sort()
  
  max_a = max(A)
  
  while B:
    if remain <= 0:
      return count
    
    b = B.pop()
    
    if b < max_a:
      break
      
    remain -= b
    count += 1
  
  count += (remain + max_a - 1) // max_a
    
  return count

print(solve())

Submission status: Accepted

Solution code:
import math


N,H = map(int, input().split())
A = []
B = []
for _ in range(N):
    a,b = map(int, input().split())
    A.append(a)
    B.append(b)

nage_count = 0
huri_count = 0
A_max = max(A)
for b in sorted(B, reverse = True):
  if b > A_max:
    nage_count += 1
    H -= b
    if H <= 0:
      break
  else: 
    break

# 今度は一番強いやつを振り続ける. 
if H>0:
  huri_count = math.ceil(H/A_max)
print(huri_count + nage_count)

Submission status: Accepted

Solution code:
import heapq
import math

n, h = map(int, input().split())
katana = [list(map(int, input().split())) for _ in range(n)]

max_a = -1
max_b = -1 # aが最大の刀のb
max_i = -1
for i in range(n):
    a, b = katana[i]
    if a > max_a:
        max_a = a
        max_i = i
    elif a == max_a and b < max_b:
        max_i = i
        max_b = b

nagetsuke = []
for i in range(n):
    a, b = katana[i]
    if b >= max_a:
        heapq.heappush(nagetsuke, -b)

ans = 0
damage = 0
while damage < h and len(nagetsuke) > 0:
    q = heapq.heappop(nagetsuke)
    damage -= q
    ans += 1

if len(nagetsuke) == 0:
    a, b = katana[max_i]
    if damage < h:
        ans += math.ceil((h-damage)/a)

print(ans)

Submission status: Accepted

Solution code:
N, H = map(int, input().split())

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

w.sort(reverse=True)
ans = 0
for v, t in w:
  if t == 1:
    H -= v
    ans += 1
  else:
    ans += -(-H//v)
    H = 0
  
  if H <= 0:
    break

print(ans)

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = lambda :stdin.readline().rstrip()
    N,H = map(int,input().split())
    A = []
    B = []
    for i in range(N):
        a,b = map(int,input().split())
        A.append(a)
        B.append(b)
    A.sort()
    B.sort() #
    a = A.pop()
    b = B.pop()
    ans = 0
    from math import ceil
    while H > 0:
        if b > a:
            ans += 1
            H -= b
            if B:
                b = B.pop()
            else:
                b = 0
                
            
        else:
            ans += ceil(H/a)
            break
    print(ans)
    return

main()

Submission status: Accepted

Solution code:
def main():
    N, H = list(map(int, input().split(' ')))
    swords = [list(map(int, input().split(' '))) for _ in range(N)]
    swords.sort(key=lambda s: s[0], reverse=True)
    max_a = swords[0][0]
    throwable_swords = list(filter(lambda s: s[1] > max_a, swords))
    # if len(swords) = 0, then use only the sword with max_a.
    sum_b = sum(list(map(lambda s: s[1], throwable_swords)))
    if H <= sum_b:
        # throw all swords
        throwable_swords.sort(key=lambda s: s[1], reverse=True)
        ans = 0
        for s in throwable_swords:
            ans += 1
            H -= s[1]
            if H <= 0:
                break
        print(ans)
    else:
        # attack with the max_a sword and throw swords
        ans = len(throwable_swords)
        H -= sum_b
        ans += (H + max_a - 1) // max_a
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,power = map(int,input().split())
swing_ls = [0] * n
throw_ls = [0] * n
for i in range(n):
    swing, throw = map(int,input().split())
    swing_ls[i] = swing
    throw_ls[i] = throw
swing_best = max(swing_ls)
throw_ls.sort(reverse=True)
def isOK(index, key, l):
    if l[index] <= key:
        return True
    else:
        return False
def meguru_search(l, key):
    '''
    key以上の値を持つ最小のインデックスを返す
    '''
    left = -1
    right = len(l)

    while (right - left) > 1:
        mid = left + (right - left) // 2
        # 直感的に記憶　
            # 「含まれている」んだったら「含むを許容（等号付き）する右側」はmidまで動かして問題ない
                # 新しいrightの位置がkeyの位置だとしても、「含む」は許容されてる
            # 「含まれていない」んだったら「含まない(<)左の壁」をそこまで動かしてもkeyを通り過ぎることはない
        if isOK(mid, key, l):
            right = mid
        else:
            left = mid
    
    # whileを抜ける時、rightとleftは一個差で、かつkeyがrightの位置にある
    return right
last_ind = meguru_search(throw_ls, swing_best) - 1
if last_ind != -1:
    throw_use_q = deque(throw_ls[:last_ind+1])
else:
    throw_use_q = []
count = 0
while power > 0:
    if throw_use_q:
        point = throw_use_q.popleft()
        power -= point
    else:
        count += -(-power // swing_best)
        break
    count += 1
print(count)

Submission status: Accepted

Solution code:
import heapq
import math
def main():
  N, H = map(int, input().split())
  A = 0
  B = []
  for i in range(N):
    a, b = map(int, input().split())
    A = max(A, a)
    B.append(-1*b)
  lis = []
  heapq.heapify(B)
  while True:
    temp = -1*heapq.heappop(B)
    if temp > A:
      lis.append(-1*temp)
    if len(B) == 0:
      break
  wa = 0
  ans = 0
  for i in range(len(lis)):
    wa += -1*heapq.heappop(lis)
    ans += 1
    if wa >= H:
      break
  if wa < H:
    ans += math.ceil((H-wa)/A)
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7

n,h = map(int, input().split())
blist = []
amax = 0
for i in range(n):
    a,b = map(int, input().split())
    amax = max(amax, a)
    blist.append(b)
# aが最大のやつじゃないとフル価値なし
ans = (h+amax-1)//amax
blist.sort(reverse = True)
btotal=0
for i,num in enumerate(blist):
    tmp = h
    if num <= amax:
        break
    else:
        btotal+=num
        tmp-=btotal
        if tmp <= 0:
            ans = min(ans, i+1)
            break
        else:
            ans = min((tmp+amax-1)//amax + i+1, ans)
print(ans)

Submission status: Accepted

Solution code:
import math

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

a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
m = max(a)
b.sort(reverse=True)

ans = 0
for i in range(n):
    if m <= b[i]:
        h -= b[i]
        ans += 1
        if h <= 0:
            print(ans)
            exit()

ans += math.ceil(h / m)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

# 入力から変数を初期化
N, H = map(int, input().split())
a = []
b = []
for i in range(N):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
ans = H

# 振る刀の最大値
amax = max(a)

# 投げる刀を降順でソートしておく
b.sort(reverse=True)

# 攻撃力の高い刀から順にk本投げ、残りの体力をamaxを使って削る
damage_throw = 0
for k in range(N+1):
    damage_throw += 0 if k == 0 else b[k-1]
    H_minus_throw = H - damage_throw
    if H_minus_throw <= 0:
        tmp_ans = k
    else:
        num_swing = -(-H_minus_throw // amax)
        tmp_ans = k + num_swing
    ans = min(tmp_ans, ans)

print(ans)

Submission status: Accepted

Solution code:
N,H=list(map(int,input().split()))
sword=[list(map(int,input().split())) for i in range(N)]
through=[i[1] for i in sword]
through.sort(reverse=True)
max_atk=max([i[0] for i in sword])
ans=0
for i in through:
   ans+=1
   if i > max_atk:
      H-=i
   else:
      H-=max_atk
   if H <= 0:
      break
import math
if 0 < H:
   ans+=math.ceil(H/max_atk)
print(ans)

Submission status: Accepted

Solution code:
import math
N, H = map(int, input().split())
countA=0
countB=0
count=0
flag=True
maxA=0
maxB=0
listA=[0 for j in range(N)]
listB=[0 for j in range(N)]
bigB=[]
for i in range(N):
    A, B = map(int, input().split())
    listA[i]=A
    listB[i]=B
    if maxA<A:
        maxA=A
        maxAindex=i
        maxB=B

listB.sort()
listB.reverse()

for i in range(N):
    if maxA<=listB[i]:
        countB+=listB[i]
        count+=1
    if countB>=H:
        print(count)
        flag=False
        break

if flag:
    print(count+math.ceil((H-countB)/maxA))

Submission status: Accepted

Solution code:
import numpy as np
N, H = map(int,input().split())

maxA = 0
B = []
for _ in range(N):
    a, b = map(int,input().split())
    B.append(b)
    if maxA < a:
        maxA = a

B = np.array(B)
throw_all = np.sort((B[B>maxA]))[::-1]
SUM = 0
cnt = 0
for a in throw_all:
    SUM += a
    cnt += 1
    if SUM >= H:
        print(cnt)
        exit()

ans = -(-(H-SUM)//maxA)+ cnt
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

import math

n, h = na()
a = []
b = []
for i in range(n):
    _a, _b = na()
    a.append(_a)
    b.append(_b)

a.sort(reverse=True)
b.sort(reverse=True)

i = 0
cnt = 0
while h > 0:
    if i < n and a[0] < b[i]:
        h -= b[i]
        i += 1
        cnt += 1
    else:
        cnt += math.ceil(h / a[0])
        break

print(cnt)

Submission status: Accepted

Solution code:
N, H = map(int,input().split())
L = []
maxi = 0
for _ in range(N):
    a,b = map(int,input().split())
    maxi = max(maxi, a)
    L.append(b)
 
#L = sorted([x for x in L if x > maxi])[::-1]
L = sorted(filter(lambda x:x>maxi,L))[::-1]
throw = 0
for i in range(len(L)):
    throw += L[i]
    if throw >= H:
        print(i + 1)
        quit()
from math import ceil
print(ceil((H - throw) / maxi) + len(L))

Submission status: Accepted

Solution code:
N, H = map(int,input().split())
L = []
maxi = 0
for _ in range(N):
    a,b = map(int,input().split())
    maxi = max(maxi, a)
    L.append(b)
 
L = sorted([x for x in L if x > maxi])[::-1]
throw = 0
for i in range(len(L)):
    throw += L[i]
    if throw >= H:
        print(i + 1)
        quit()
from math import ceil
print(ceil((H - throw) / maxi) + len(L))

Submission status: Accepted

Solution code:
N, H = map(int,input().split())
L = []
maxi = 0
for _ in range(N):
    a,b = map(int,input().split())
    maxi = max(maxi, a)
    L.append(b)
 
L = sorted([x for x in L if x > maxi],reverse=True)
throw = 0
for i in range(len(L)):
    throw += L[i]
    if throw >= H:
        print(i + 1)
        quit()
from math import ceil
print(ceil((H - throw) / maxi) + len(L))

Submission status: Accepted

Solution code:
N, H = map(int,input().split())
L = []
maxi = 0
for _ in range(N):
    a,b = map(int,input().split())
    maxi = max(maxi, a)
    L.append((a,b))
L = [x for x in L if x[1] > maxi]
L = sorted(L,key = lambda x:x[1],reverse=True)
throw = 0
for i in range(len(L)):
    throw += L[i][1]
    if throw >= H:
        print(i + 1)
        quit()
from math import ceil
print(ceil((H - throw) / maxi) + len(L))

Submission status: Accepted

Solution code:
N, H = map(int,input().split())
L = []
maxi = 0
for _ in range(N):
    a,b = map(int,input().split())
    maxi = max(maxi, a)
    L.append((a,b))
cand = []
throw = 0
cnt = 0
for l in L:
    if maxi <  l[1]:
        throw += l[1]
        cand.append(l[1])
        cnt += 1
import math
if H - throw > 0: 
    print(math.ceil((H - throw)/maxi) + cnt )
else:
    throw = 0
    cnt = 0
    cand.sort()
    for x in cand[::-1]:
        throw += x
        cnt += 1
        if throw >= H:
            print(cnt)
            quit()

Submission status: Accepted

Solution code:
from math import ceil


n, h = map(int, input().split())
katana = []
attacker = 0

for _ in range(n):
    array = list(map(int, input().split()))
    katana.append(array)
    if array[0] > attacker:
        attacker = array[0]

katana.sort(key=lambda x:x[1], reverse=True)

ans = 0
for i in range(n):
    if katana[i][1] < attacker:
        break
    h -= katana[i][1]
    ans += 1
    if h <= 0:
        print(ans)
        exit()

ans += ceil(h/attacker)

print(ans)

Submission status: Accepted

Solution code:
n,h=map(int,input().split())
ab=sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x:x[1],reverse=True)
m=max([i[0] for i in ab])
ans=0
for i in ab:
  if i[1]>m:
    h-=i[1]
    ans+=1
    if h<=0:
      print(ans)
      exit()
if h%m==0:
  print(ans+h//m)
else:
  print(ans+h//m+1)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N, H = getNM()

a = []
b = []

for i in range(N):
  x, y = map(int, input().split())
  a.append(x)
  b.append(y)

# 振った場合の最大値
max_a = max(a)

ans = 0
# 振る刀の最大攻撃力より高い攻撃力を持つ投げ刀を高い順にソートする
# 刀iで好きなだけ振って攻撃する→気が済んだら投げることで振りの攻撃力と投げの攻撃力を
# 両方利用することができる
# 実は投げてしまった刀も振ることができるというルールに変更しても
# 問題の答えは変わらない
# 実際のムーブとしては
# ①最も攻撃力が高い振り刀で攻撃する
# ②一定の体力以下になると攻撃力が高い順に投げ刀で攻撃していって撃破
# という流れになる
for x in reversed(sorted(filter(lambda x: x >= max_a, b))):
    H -= x
    ans += 1
    if H <= 0: break

ans += max(0, (H + max_a - 1) // max_a)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math


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


def main():
    N, H = map(int, input().split())
    A = []
    B = []
    for i in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    max_a = max(A)
    B.sort(reverse=True)
    attack = 0
    cnt = N
    for i in range(N):
        if B[i] < max_a:
            cnt = i
            break
        attack += B[i]
        if attack >= H:
            print(i + 1)
            return

    print(cnt + math.ceil((H - attack) / max_a))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, H = (int(_) for _ in input().split())
    S = sorted([[int(_) for _ in input().split()] for __ in range(N)])[::-1]
    output = 0
    for a, b in sorted(S, key=lambda x:-x[1]):
        if b > S[0][0]:
            H -= b
            output += 1
            if H <= 0: break
    if H > 0:
        output += (H+S[0][0]-1)//S[0][0]
    print(output)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,h=map(int,input().split())
th=[]
ma=0
for i in range(n):
    a,b=map(int,input().split())
    ma=max(ma,a)
    th.append([b,a])
ans=0
th.sort(reverse=True)
for i in range (n):
    if h>0 and th[i][0]>ma:
        h-=th[i][0]
        ans+=1
    if h<=0:
        print(ans)
        exit()
if h%ma==0:
    ans+=h//ma
else:
    ans+=1+(h//ma)
print(ans)

Submission status: Accepted

Solution code:
n, h = map(int, input().split())
a = [0]*n
b = [0]*n
maxa = 0
for i in range(n):
    a[i], b[i] = map(int, input().split())
    maxa = max(maxa, a[i])

c = []
for i in range(n):
    if b[i] >= maxa:
        c.append(b[i])
        
c.sort()
csum = sum(c)
count = len(c)

if csum >= h:
    i = 0
    while csum - c[i] >= h:
        if i == len(c):
            break
        else:
            csum -= c[i]
            i += 1
            count -= 1
else:
    if (h - csum) % maxa == 0:
        count += (h - csum) // maxa
    else:
        count += (h - csum) // maxa
        count += 1

print(count)

Submission status: Accepted

Solution code:
N, H = map(int, input().split())

Bs = []
max_swing_i = 0
max_swing = 0
throw_when_max_swing = 0
for i in range(N):
    a, b = map(int, input().split())
    if a > max_swing:
        max_swing = a
        throw_when_max_swing = b
        max_swing_i = i

    Bs.append(b)

# 取りのぞいて並び替える
#Bs = Bs.pop(max_swing_i)
Bs.sort(reverse=True)

ans = 0
for i in range(len(Bs)):
    if H <= 0 or Bs[i] < max_swing:
        break

    H -= Bs[i]
    ans += 1

if H > 0:
    if H % max_swing == 0:
        ans += H // max_swing
    else:
        ans += H // max_swing + 1

print(ans)

Submission status: Accepted

Solution code:
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N,H = map(int,(input().split()))
a = [[0]*2 for _ in range(N)]
for i in range(N):
    a[i] = list(map(int,(input().split())))
a.sort(key=lambda x:x[1],reverse=True)
M = max(a,key=lambda x:x[0])[0]

c = 0
for i in range(N):
    if a[i][1] > M:
        H -= a[i][1]
        c += 1
        if H <= 0:
            H = 0
            break
    else:
        break
c += math.ceil(H/M)
print(c)

Submission status: Accepted

Solution code:
import math
n,h = map(int,input().split())
A = 0; b = []; ans = 0
for _ in range(n):
    u,v = map(int,input().split())
    A = max(A,u); b.append(v)

for B in sorted(b,key=lambda x:-x):
    if h <= 0 or B <= A:break
    h -= B
    ans += 1
print(max(0,math.ceil(h/A)) + ans)

Submission status: Accepted

Solution code:
import math
n,h = map(int,input().split())
l = []; x,y = 0,0
for _ in range(n):
    a,b = map(int,input().split())
    if a > x or a == x and b < y:
        x,y = a,b
    if b < x:continue
    l.append((a,b))
l.remove((x,y))
l = sorted(l,key=lambda x:-x[1])
ans = 0
for a,b in l:
    if b <= x:break
    if b < y and y >= h:
        print(ans+1);exit()
    h -= max(b,x)
    ans += 1
    if h <= 0:
        print(ans);exit()
d = math.ceil((max(0,h-y))/x)
print(ans + d + 1)

Submission status: Accepted

Solution code:
import math
n, h = map(int,input().split())
am = 0
b = [0 for i in range(n)]

for i in range(n):
    ai,bi = map(int,input().split())
    if ai > am:
        am = ai
    b[i] = bi

b.sort(reverse=True)
ans = n

for i,bi in enumerate(b):
    if bi > am:
        h -= bi
        if h <= 0:
            print(i+1)
            exit()
    else:
        ans = i
        break

ans += math.ceil(h/am)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math

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

data = []

for _ in range(N):
    a, b = map(int, input().split())
    data.append([a, True])
    data.append([b, False])

data = sorted(data)[::-1]
ans = 0

for d in data:
    flag = d[1]
    if flag:
        ans += math.ceil(H / d[0])
        break
    else:
        ans += 1
        H -= d[0]
        if H <= 0:
            break
    
print(ans)

Submission status: Accepted

Solution code:

import math

N,H = map(int, input().split())
A = 0
B = []
for i in range(N):
  a,b = map(int, input().split())
  A = max(A, a)
  B.append(b)

B.sort(reverse=True)

accum_B = [0] * (N+1)
for i in range(1, N+1):
  accum_B[i] = accum_B[i-1] + B[i-1]

ans = H+1
for i in range(N+1):
  if H - accum_B[i] <= 0:
    ans = min(ans, i)
  else:
    ans = min(ans, i + math.ceil((H - accum_B[i]) / A))

print(ans)

Submission status: Accepted

Solution code:
import bisect

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

Attack = []
Throw = []
for _ in range(N):
    a, b = map(int, input().split())
    Attack.append(a)
    Throw.append(b)
attack = max(Attack)
Throw.sort()

Throw_num = bisect.bisect_left(Throw, attack)
Throw_sum = sum(Throw[Throw_num:])

if Throw_sum <= H:
    print((H - Throw_sum - 1) // attack + 1 + N - Throw_num)
else:
    Throw.sort(reverse=True)
    for i in range(N):
        H -= Throw[i]
        if H <= 0:
            print(i + 1)
            exit()

Submission status: Accepted

Solution code:
n, h = map(int, input().split())
a_ls = []
b_ls = []

for i in range(n):
    a, b = map(int, input().split())
    a_ls.append(a)
    b_ls.append(b)

a_ls.sort()
a_ls.reverse()

b_ls.sort()
b_ls.reverse()

tmp = 0
cnt = 0

for i in range(n):
    dmg = b_ls[i]
    if dmg < a_ls[0]:
        break
    else:
        cnt += 1
        tmp += dmg
        if tmp >= h:
            print(cnt)
            exit()

left = h - tmp

cnt += (left + a_ls[0] - 1) // a_ls[0]
print(cnt)

Submission status: Accepted

Solution code:
n,h = map(int,input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i],b[i] = map(int,input().split())

ama = max(a)
b.sort(reverse=True)
c = 0
i = 0
while(h > 0):
    if(i >= n):break
    if(b[i] > ama):
        c += 1
        h -= b[i]
        i += 1
    else:
        break
h = max(0,h)
c += h // ama
if(h % ama != 0):c += 1
print(c)

Submission status: Accepted

Solution code:
from operator import itemgetter
import math
N, H = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)] 

ab.sort(key=itemgetter(1), reverse=True)

amax = max([i[0] for i in ab]) 
num = 0
dmg = 0
jdg = False

for a, b in ab:
    if b > amax:
        num += 1
        dmg += b
        if dmg >= H:
            jdg = True
            break
if not jdg:
    num += math.ceil((H - dmg) / amax)
print(num)

Submission status: Accepted

Solution code:
N, H = map(int, input().split())
A = list()
B = list()
for i in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
A.sort(reverse = True)
B.sort(reverse = True)
cnt = 0
b = 0
while(H > 0 and b<=N-1 and cnt==b):
  cnt += 1
  if(B[b]>A[0]):
    H -= B[b]
    b += 1
if(H <= 0):
  print(b)
else:
  print(b +(H-1)//A[0]+1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


def solve():
    N, H = map(int, input().split())
    cut_dmgs = []
    thr_dmgs = []
    for _ in range(N):
        a, b = list(map(int, input().split()))
        heappush(cut_dmgs, -a)
        heappush(thr_dmgs, -b)

    ans = 0
    max_cut_dmg = -min(cut_dmgs)
    while thr_dmgs:
        thr_dmg = -heappop(thr_dmgs) 
        if thr_dmg <= max_cut_dmg:
            break
        ans += 1
        H -= thr_dmg
        if H <= 0:
            return ans
    return ans + (H + max_cut_dmg - 1) // max_cut_dmg


print(solve())

Submission status: Accepted

Solution code:
import math
from bisect import bisect_left as bl
from itertools import accumulate

n,h = map(int,input().split())
A = []
B = []
ans = 0

for _ in range(n):
  a,b = map(int,input().split())
  A.append(a)
  B.append(b)

A.sort(reverse=1)
B.sort()

index = bl(B, A[0])
B = B[index:]
B = list(accumulate(B[::-1]))
if B[-1] >= h:
  print(bl(B,h)+1)
  exit()
  
h -= B[-1]
ans += len(B)
ans += math.ceil(h/A[0])
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

def main():
    N, H = map(int, readline().rstrip().split())
    A, B = [], []
    for _ in range(N):
        a, b = map(int, readline().rstrip().split())
        A.append(a)
        B.append(b)
    
    a_max = max(A)
    B.sort(reverse=True)
    damage = 0
    cost = 0
    for b in B:
        if b < a_max:
            break
        damage += b
        cost += 1
        if damage >= H:
            break
    if damage < H:
        cost += -(-(H - damage) // a_max)
    
    print(cost)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter
import math

n, h = map(int, input().split())
ab = []
A = 0
B = 1
maxA = 0
for i in range(n):
    ab.append(list(map(int, input().split())))
    maxA = max(maxA, ab[i][A])

ab.sort(key=itemgetter(B), reverse=True)

sumB = 0
for _ab in ab:
    sumB += _ab[B]

ans = 0
damage = 0
i = 0
while damage < h and ans < n:
    damage += max(maxA, ab[ans][B])
    ans += 1

if damage < h:
    ans += math.ceil((h - damage)/maxA)

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
import math

n, h = map(int, input().split())
ab = []
A = 0
B = 1
maxA = 0
for i in range(n):
    ab.append(list(map(int, input().split())))
    maxA = max(maxA, ab[i][A])

ab.sort(key=itemgetter(B), reverse=True)

sumB = 0
for _ab in ab:
    sumB += _ab[B]

ans = 0
damage = 0
i = 0
while damage < h and ans < n:
    damage += max(maxA, ab[ans][B])
    ans += 1

ab.sort(key=itemgetter(A), reverse=True)

if damage < h:
    ans += math.ceil((h - damage)/ab[0][A])

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc085/tasks/abc085_d
from math import ceil
n, h = map(int, input().split())

cut = []
throw = []
for _ in range(n):
    a, b = map(int, input().split())
    cut.append(a)
    throw.append(b)
throw.sort(reverse=True)
MAX = max(cut)

attack = 0
for i in range(len(throw)):
    if throw[i] > MAX:
        h -= throw[i]
        attack += 1
    else:
        break
    if h <= 0:
        break

attack += max(0, ceil(h / MAX))
print(attack)

Submission status: Accepted

Solution code:
n,h=map(int,input().split())

#a>bだったらaを振り続ければいい
#aの最大になるまで、bを投げ続けて、aが最大になったらあとはaの最大を振る
#順番は無視していいので、
#bを1回、aを無限回触れる問題に帰着する？

ba=[]
max_a=0
for _ in range(n):
    a,b=map(int,input().split())
    max_a=max(max_a,a)
    ba.append([-1*b,a])

ba.sort()
cnt=0


#print(ba)
for item in ba:
    b=item[0]*(-1)
    a=item[1]

    if b>=max_a:
        h-=b
        cnt+=1
    else:
        break

    if h<=0:
        break

if h>0:
    cnt-=(-1*h)//max_a

print(cnt)

Submission status: Accepted

Solution code:
n,h = map(int,input().split())
a_li = []
b_li = []
for _ in range(n):
    a,b = map(int,input().split())
    a_li.append(a)
    b_li.append(b)
count = 0
ma = max(a_li)
b_li.sort(reverse=True)
for b in b_li:
    if b < ma:
        break
    count+=1
    h -= b
    if h<=0:
        print(count)
        exit()
import math
tmp = math.ceil(h/ma)
print(count+tmp)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())

X = [list(map(int,input().split())) for _ in range(N)]
X = sorted(X,key=lambda X:-X[0])
a = X[0][0]
X = sorted(X,key=lambda X:-X[1])

i = 0
count = 0
while M > 0:
	if i < N and X[i][1] > a:
		M -= X[i][1]
		i += 1
	else:
		count += -(-M//a)
		break
	count += 1

print(count)

Submission status: Accepted

Solution code:
N,H=map(int,input().split())

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

amax=max(a)
n=0
total=0
b.sort(reverse=True)
for i in range(N):
  if b[i] > amax:
    n+=1
    total+=b[i]
  else:
    break

if H <= total:
  for i in range(n):
    H-=b[i]
    if H <= 0:
      print(i+1)
      break
else:
  print(n+int((H-total-1)/amax)+1)

Submission status: Accepted

Solution code:
import math


def find_argmax(num_list):
    argmax = sorted(enumerate(num_list), key=lambda x:x[1])[-1][0]
    return argmax


def find_all_more_than(threshold, num_list):
    indices = [
        idx
        for idx, num in enumerate(num_list) 
        if num > threshold
    ]
    return indices


def read_input():
    initial_inputs = input().split(" ")
    N = int(initial_inputs[0])
    H = int(initial_inputs[1])
    a_list = []
    b_list = []
    for _ in range(N):
        inputs = input().split(" ")
        a = int(inputs[0])
        b = int(inputs[1])
        a_list.append(a)
        b_list.append(b)
    return N, H, a_list, b_list


# TLE
def searchA(N, H, a_list, b_list):
    # initialize used_indices
    used_indices = [ False for b in b_list]

    # initialize search_area
    search_area = [ b for b in b_list ]

    # count how many times
    times_count = 0
    
    while H > 0:
        # search
        idx = find_argmax(search_area)

        # check
        if used_indices[idx]:
            # calculate rest and finish
            rest_count = math.ceil(H / search_area[idx])
            return times_count + rest_count

        # attack
        H -= search_area[idx]

        # change
        search_area[idx] = a_list[idx]
        used_indices[idx] = True
        
        # count
        times_count += 1

    return times_count

# still TLE
def searchB(N, H, a_list, b_list):
    # initialize used_indices
    used_indices = [ False ] * N

    # initialize search_area
    search_area = [ b for b in b_list ]

    # count how many times
    times_count = 0

    # pick up b indices higher than max(a_list)
    higher_b_indices = find_all_more_than(max(a_list), b_list)
    higher_b_list = [ b_list[idx] for idx in higher_b_indices ]

    for b in reversed(sorted(higher_b_list)):
        if not H > 0:
            return times_count

        # attack
        H -= b
        times_count += 1

    # fix search_area used_indices
    for idx in higher_b_indices:
        # change
        search_area[idx] = a_list[idx]
        used_indices[idx] = True

    while H > 0:
        # search
        idx = find_argmax(search_area)

        # check
        if used_indices[idx]:
            # calculate rest and finish
            rest_count = math.ceil(H / search_area[idx])
            return times_count + rest_count

        # attack
        H -= search_area[idx]
        times_count += 1

        # change
        search_area[idx] = a_list[idx]
        used_indices[idx] = True
        
    return times_count


# still TLE
def searchC(N, H, a_list, b_list):
    # count how many times
    times_count = 0

    # pick up b indices higher than max(a_list)
    max_a = max(a_list)
    higher_b_indices = find_all_more_than(max_a, b_list)
    higher_b_list = [ b_list[idx] for idx in higher_b_indices ]

    for b in reversed(sorted(higher_b_list)):
        if not H > 0:
            return times_count

        # attack
        H -= b
        times_count += 1

    # use max(a_list)
    rest_count = math.ceil(H / max_a)
    return times_count + rest_count


def main():
    # read input
    N, H, a_list, b_list = read_input()

    # search
    times_count = searchC(N, H, a_list, b_list)

    # output
    print(times_count)
    

if __name__ == '__main__':
    main()