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:
def main():
    n,h = list(map(int, input().split()))
    bi = []
    max_attack = [0,0]
    for i in range(n):
        a, b = list(map(int, input().split()))
        bi.append(b)
        max_attack[0] = max(a, max_attack[0])
        max_attack[1] = max(b, max_attack[1])
    bi.sort(reverse=True)
    idx = 0
    count = 0
    while h > 0:
        damage = 0
        if idx < len(bi) and max_attack[0] < bi[idx]:
            damage = bi[idx]
            idx += 1
        else:
            count += h // max_attack[0]
            count += 0 if h % max_attack[0] == 0 else 1
            break
        h -= damage
        count += 1
    print(count)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

a = [0] * N
b = [0] * N

ab = []
for i in range(N):
  ai, bi = map(int, input().split())
  a[i] = -ai
  b[i] = -bi
  ab.append((-ai, -bi))
  
ab.sort()
b.sort()
mina = ab[0][0]

ans = 0
for bi in b:
  if bi <= mina:
    H += bi
    ans += 1
    if H <= 0:
      print(ans)
      exit()
  else:
    ans += (H-1)//(-mina) + 1
    print(ans)
    exit()
ans += (H-1)//(-mina) + 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math
N, H = map(int, input().split())
a_list = []
b_list = []
for _ in range(N):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)

a_max = max(a_list)
b_list.sort()
def judge(H, n, a_max, b_list):
    b_copy = b_list.copy()
    count = 0
    while H > 0:
        if len(b_copy) == 0:
            count += math.ceil(H / a_max)
            break
        else:
            b_max = b_copy.pop()
            if a_max > b_max:
                count += math.ceil(H / a_max)
                break
            else:
                H -= b_max
                count += 1
    if count <= n:
        return True
    return False

right = 10 ** 9
left = 1
while right != left:
    
    mid = (left + right) // 2
    if judge(H, mid, a_max, b_list):
        right = mid
    else:
        left = mid + 1

print(left)

Submission status: Accepted

Solution code:
import bisect
import sys

N, H = map(int, input().split())
ab = [map(int, input().split()) for _ in range(N)]
a, b = [list(i) for i in zip(*ab)]

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

l = [b[i] for i in range(N) if b[i] >= a_max]
d = 0
cnt = 0
for v in l:
    d += v
    cnt += 1
    if d >= H:
        print(cnt)
        sys.exit()
cnt += (H-d+a_max-1)//a_max
print(cnt)

Submission status: Accepted

Solution code:
def main():
    from math import ceil
    n, h, *ab = map(int, open(0).read().split())

    *c, = map(lambda x: -x, ab[::2])
    d = sorted(c + ab[1::2], key=abs, reverse=True)
    ans = 0
    for x in d:
        if x < 0:
            ans += ceil(h / abs(x))
            break

        h -= x
        ans += 1
        if h <= 0:
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from math import ceil
    from itertools import accumulate
    from bisect import bisect_left
    n, h, *ab = map(int, open(0).read().split())

    x = max(ab[::2])
    *y, = filter(lambda i: i >= x, ab[1::2])
    y = sorted(y, reverse=True)
    *z, = accumulate(y)

    if z[-1] <= h:
        print(len(y) + ceil((h - z[-1]) / x))
    else:
        print(bisect_left(z, h) + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from math import ceil
    from itertools import accumulate
    from bisect import bisect_left
    n, h, *ab = map(int, open(0).read().split())

    x = max(ab[::2])
    *y, = filter(lambda i: i >= x, ab[1::2])
    y.sort(reverse=True)
    *z, = accumulate(y)

    if z[-1] <= h:
        print(len(y) + ceil((h - z[-1]) / x))
    else:
        print(bisect_left(z, h) + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    from math import ceil
    n, h, *ab = map(int, open(0).read().split())
    a = ab[::2]
    *b, = map(lambda x: -x, ab[1::2])
    c = a + b
    c.sort(key=lambda x: abs(x), reverse=True)

    q = deque(c)
    cnt = 0
    while h > 0:
        cnt += 1
        x = q.popleft()
        h -= abs(x)
        if x > 0:
            cnt += ceil(h / x)
            break

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def S(): return sys.stdin.readline().rstrip()

N,H = map(int,S().split())
ab = [LI() for i in range(N)]

A = [(ab[i][0],1) for i in range(N)]
B = [(ab[i][1],2) for i in range(N)]

from operator import itemgetter

C = sorted(A+B,key = itemgetter(0),reverse=True)

damage = 0  # 与ダメージ
ans = 0  # 攻撃回数
for i in range(2*N):
    if C[i][1] == 1:
        ans += (H-damage+C[i][0]-1)//C[i][0]
        break
    else:
        ans += 1
        damage += C[i][0]
        if damage >= H:
            break

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math

N, H = 2, 10
ARR = [
    [3, 5],
    [2, 6]
]

N, H = 4, 1000000000
ARR = [
    [1, 1],
    [1, 10000000],
    [1, 30000000],
    [1, 99999999]
]

N, H = 5, 500
ARR = [
    [35, 44],
    [28, 83],
    [46, 62],
    [31, 79],
    [40, 43]
]

N, H = map(int, input().split())
ARR = [list(map(int,input().split())) for i in range(N)]


def calculate(n, h, arr):
    arr = np.array(arr)
    A1 = arr[:, 0]
    B1 = arr[:, 1]

    largestA1 = max(A1)

    b2 = sorted(B1, key=lambda x: -x)

    result = 0
    for i in range(len(b2)):

        if h <= 0:
            break
        if b2[i] >= largestA1:
            h = h - b2[i]
            result += 1
        else:
            break

    if h > 0:
        result += math.ceil(h / largestA1)

    return result


res = calculate(N, H, ARR)
print(res)

Submission status: Accepted

Solution code:
import sys
import math

n, h = map(int, input().split())
a = 0
b = []

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

b.sort(reverse=True)

b = [x for x in b if x > a]

for i, x in enumerate(b):
    h -= x
    if h <= 0:
        print(i + 1)
        sys.exit()

if len(b) == 0:
    i = -1

ans = i + 1 + math.ceil(h / a)

print(ans)

Submission status: Accepted

Solution code:
n, h = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(n)]
A,B = zip(*AB)
a = max(A)
B = [b for b in B if b > a]
B.sort(reverse=True)
ans = 0
hp = h
attack_cnt = 0
for b in B:
    if hp <= 0:
        break
    attack_cnt += 1
    hp -= b
if hp > 0:
    attack_cnt += (hp - 1) // a + 1
print(attack_cnt)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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)

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

    throw = []
    for i in range(N):
        if B[i] > A[-1]:
            throw.append(B[i])
    # print(throw)
    throw = throw[::-1]

    ans = 0

    while H > 0:
        if throw:
            H -= throw.pop()
            ans += 1
        else:
            need_try = (H + A[-1] - 1) // A[-1]
            ans += need_try
            break

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from bisect import bisect_left

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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)

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

    throw = []
    for i in range(N):
        if B[i] > A[-1]:
            throw.append(B[i])
    # print(throw)
    throw = throw[::-1]

    ans = 0

    while H > 0:
        if throw:
            H -= throw.pop()
            ans += 1
        else:
            need_try = (H + A[-1] - 1) // A[-1]
            ans += need_try
            break

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

B = sorted(B, reverse=True)

ans = 0
f = 0

for i in B:
    if i < a_max:
        continue
    ans += 1
    H -= i
    if H <= 0:
        f = 1
        break

if f:
    print(ans)
else:
    if H%a_max == 0:
        print(ans + H//a_max)
    else:
        print(ans + H//a_max+1)

Submission status: Accepted

Solution code:
n,h = map(int,input().split())
katana_a = []
katana_b = []
for i in range(n):
    a,b = map(int,input().split())
    katana_a.append(a)
    katana_b.append(b)
amax = max(katana_a)
katana_b.sort(reverse=True)
ans = 0
k = 0
while h > 0:
    if k == n:
        break
    if katana_b[k] > amax:
        h -= katana_b[k]
        ans += 1
        k += 1
    else:
        break
if h <= 0:
    print(ans)
else:
    print(ans + (h+amax-1)//amax)

Submission status: Accepted

Solution code:
from math import ceil
n,h = map(int,input().split())
a,b = [],[]
for _ in range(n):
    a_,b_ = map(int,input().split())
    a.append(a_)
    b.append(b_)
mx_a = max(a)
b.sort(reverse=True)
cnt = 0
tmp = 0
for b_ in b:
    if b_ >= mx_a:
        tmp += b_
        cnt += 1
        if tmp >= h:
            print(cnt)
            exit()
    else:
        break
print(cnt+ceil((h-tmp)/mx_a))

Submission status: Accepted

Solution code:
import math as m1
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_)
b = list(reversed(sorted(b)))
m = max(a)
ans = 0
for i in b:
    if i > m:
        if h - i <= 0:
            print(ans + 1)
            exit()
        h -= i
        ans += 1
print(ans + m1.ceil(h / m))

Submission status: Accepted

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

p=sorted(p,key=lambda x:-x[0])

i=0
ans=0
while h>0:
    if p[i][1]==1:
        h-=p[i][0]
        ans+=1
        i+=1
    else:
        ans-=(-h//p[i][0])
        break

print(ans)

Submission status: Accepted

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

ab.sort(reverse=True, key=lambda x: x[0])
#print(ab)
count = 0
for x, y in ab:
    if h <= 0:
        break
    if y == "a":
        if h%x == 0:
            count += h//x
            h = 0
        else:
            count += h//x + 1
            h = 0
    if y == "b":
        h -= x
        count += 1

print(count)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def ceil(a,b):
    return a//b + int(a%b != 0)

N,H = LI()
a,b = LIR(N,2)

x = []
for i in range(N):
    x.append((a[i],0))
    x.append((b[i],1))

x.sort(key=lambda x: (-x[0],x[1]))

val = 0
count = 0
for x0 in x:
    if x0[1] == 0:
        use_a = x0[0]
        break
    else:
        val += x0[0]
        count += 1
        if val >= H:
            print(count)
            exit()

H -= val
ans = count + ceil(H,use_a)
print(ans)

Submission status: Accepted

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

N,H = map(int,readline().split())
maxA = 0
B = [0] * N
for i in range(N):
  a,b = map(int,readline().split())
  B[i] = b
  if maxA < a:
    maxA = a

usefulB = []
for i in range(N):
  if B[i] > maxA:
    usefulB += [B[i]]

usefulB = sorted(usefulB,reverse = True)

cnt = 0
for b in usefulB:
  H -= b
  cnt += 1
  if H <= 0:
    print(cnt)
    break
else:
  cnt += (H + maxA - 1) // maxA
  print(cnt)

Submission status: Accepted

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

p=sorted(p,key=lambda x:-x[0])

i=0
ans=0
while h>0:
    if p[i][1]==1:
        h-=p[i][0]
        ans+=1
        i+=1
    else:
        ans-=(-h//p[i][0])
        break

print(ans)

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, h = ns()
    a = []
    b = []
    for i in range(n):
        ai, bi = ns()
        a.append((ai, i))
        b.append((bi, i))

    a = sorted(a, key=lambda x: x[0], reverse=True)
    b = sorted(b, key=lambda x: x[0], reverse=True)

    a_max = a[0][0]
    a_max_idx = a[0][1]

    sum_b = 0
    b_cnt = 0
    for i in range(n):
        if b[i][0] > a_max:
            b_cnt += 1
            sum_b += b[i][0]

    cnt = 0
    if sum_b <= h:
        cnt += (h - sum_b + a_max - 1) // a_max
        cnt += b_cnt
    else:
        for i in range(n):
            h -= b[i][0]
            cnt += 1
            if h <= 0:
                break

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,H = IL()
S = ILL(N)

MAX = max(a for a,b in S)
B = [b for a,b in S]

B.sort()

ans = 0
while B and H>0:
  h = B.pop()
  if h>MAX:
    H -= h
    ans += 1
  else:
    break
    
print(ans + max(-(-H//MAX),0))

Submission status: Accepted

Solution code:
n,h,*d=map(int,open(0).read().split())
a=max(d[::2])
b=sorted(d[1::2])
c=0
while b and b[-1]>a>0<h:h-=b.pop();c+=1
print(c--h*(h>0)//a)

Submission status: Accepted

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

#aの最大値を求める。
maxa = max(A)

#maxaのうち、bが最小の刀を求める。これを刀ｓとする。刀ｓを取り除く
minb = 10**10
s = 0
for i in range(n):
    if A[i] == maxa and B[i] < minb:
        minb = B[i]
        s = i
B.pop(s)

#bを降順に並べ、maxaより大きいbは投げつける
B.sort(reverse = True)
for i in range(len(B)):
    if B[i] > maxa:
        h = h - B[i]
        ans += 1
        if h <= 0:
            print(ans)
            exit()
    else:
        break

#まずsを投げてからaで割る
h = h - minb
ans += 1
if h <= 0:
    print(ans)
else:
    ans += (h+(maxa-1)) // maxa
    print(ans)

Submission status: Accepted

Solution code:
n,h,*d=map(int,open(0).read().split());a=max(d[::2]);b=sorted(d[1::2]);c=0
while b and b[-1]>a>0<h:h-=b.pop();c+=1
print(c--h*(h>0)//a)

Submission status: Accepted

Solution code:
n,h,*d=map(int,open(0).read().split());a=max(d[::2]);b=sorted(d[1::2]);c=0
while b and b[-1]>a>0<h:h-=b.pop();c+=1
print(c-(-h//a)*(h>0))

Submission status: Accepted

Solution code:
n,h,*d=map(int,open(0).read().split());a=max(d[::2]);b=sorted(d[1::2]);c=0
while b and(h>0)*(b[-1]>a):h-=b.pop();c+=1
while b and b[-1]>a>0<h:h-=b.pop();c+=1
print(c-(-h//a)*(h>0))

Submission status: Accepted

Solution code:
n,h,*d=map(int,open(0).read().split());a=max(d[::2]);b=sorted(d[1::2]);c=0
while b and(h>0)*(b[-1]>a):h-=b.pop();c+=1
print(c-(-h//a)*(h>0))

Submission status: Accepted

Solution code:
n,h,*d=map(int,open(0).read().split());a=max(d[::2]);b=sorted(d[1::2]);c=0
while b and(h>0)*(b[-1]>a):h-=b.pop();c+=1
c-=(-h//a)*(h>0)
print(c)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, h, *d = map(int, open(0).read().split())
a = max(d[::2])
b = sorted(b for b in d[1::2] if b >= a)[::-1]
i = 0
for b in b:
    h -= b
    i += 1
    if h <= 0:
        print(i)
        exit()
print(i + 0--h // a)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,h=map(int,readline().split())
    li=[list(map(int,readline().split())) for _ in range(n)]
    li.sort(key=lambda x:x[1])
    a_max=0
    j=-1
    for i in range(n):
        if a_max<li[i][0]:
            a_max=li[i][0]
            j=i
    flags=[True]*n
    is_killed=False
    cnt=0
    for i in range(n-1,-1,-1):
        if i==j:
            if h<=li[i][1]:
                cnt+=1
                is_killed=True
                break
        elif a_max<li[i][1]:
            cnt+=1
            flags[i]=False
            h-=li[i][1]
            if h<=0:
                is_killed=True
                break
        else:
            break

    if is_killed:
        print(cnt)
    else:
        if h<=li[j][1]:
            cnt+=1
        elif li[j][0]>=li[j][1]:
            cnt+=(h+a_max-1)//a_max
        else:
            cnt+=1
            h-=li[j][1]
            cnt+=(h+a_max-1)//a_max
    
        print(cnt)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math

input = sys.stdin.readline

def main():
    N, H = map(int, input().split())
    katana = []
    for _ in range(N):
        a, b = map(int, input().split())
        katana.append([a, 1])
        katana.append([b, 0])
    
    katana.sort(key=lambda x: x[0])
    nage = 0; ans = 0
    while True:
        tmp = katana.pop()
        nage += tmp[0]*(tmp[1] == 0)
        ans += (tmp[1] == 0)
        if nage >= H:
            print(ans)
            return
        if tmp[1] == 1:
            attack = tmp[0]
            break

    ans += math.ceil((H - nage)/attack)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

n, h = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
max_a = max(a)
b.sort()
idx = bisect.bisect_right(b, max_a)
ans = 0
tmp = 0
for i in range(n - 1, -1, -1):
    tmp += b[i]
    if tmp >= h:
        print(n - i)
        exit()
    if i <= idx:
        break

print(n - idx + math.ceil((h - sum(b[idx:])) / max_a))

Submission status: Accepted

Solution code:
from math import ceil

def attack(ab,N,H):
    cut_max = 0
    for i in range(N):
        cut_max = max(cut_max,ab[i][0])

    throw = [ab[i][1] for i in range(N)]
    throw.sort(reverse = True)
    throw.append(0)

    cnt,pt = 0,0
    while H > 0:
        if throw[pt] > cut_max:
            H -= throw[pt]
            cnt += 1
            pt += 1
        else:
            cnt += (ceil(H/cut_max))
            H = 0

    return cnt

def main():
    N,H = map(int,input().split())
    ab = [list(map(int,input().split())) for _ in range(N)]

    print(attack(ab,N,H))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,h = map(int,input().split())
l = sorted([list(map(int,input().split())) for _ in range(n)])[::-1]
a,b = l[0]
cou = 0
if b>=h:
  print(1)
  exit()
l1 = sorted([i for j,i in l[1:]])[::-1]
for k in l1:
  if a<k:
    cou += 1
    h -= k
    if h<=0:
      print(cou)
      exit()
    elif h-b<=0:
      print(cou+1)
      exit()
h -= b
cou += 1
if h<=0:
  print(cou)
else:
  t = -(-h//a)
  print(cou+t)

Submission status: Accepted

Solution code:
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(reverse=True)
B.sort(reverse=True)
maxA = A[0]
cnt=0
for i in range(n):
    if B[i]>=maxA:
        h-=B[i]
        cnt+=1
        if h<=0:
            print(cnt)
            break
    else:
        cnt+=-(-h//maxA)
        print(cnt)
        break
else:
    cnt+=-(-h//maxA)
    print(cnt)

Submission status: Accepted

Solution code:
import heapq

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

hq = []

for i in range(n):
    a, b = map(int, input().split())
    heapq.heappush(hq, [-a, float("inf")])
    heapq.heappush(hq, [-b, 1])

ans = 0
while h > 0:
    damage, cnt = heapq.heappop(hq)
    damage = -damage

    if cnt == float("inf"):
        ans += (h + damage - 1) // damage
        h = 0
        heapq.heappush(hq, [-damage, float("inf")])
    else:
        ans += 1
        h -= damage

print(ans)

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def calc_min_attack(A, B, h):
        n = len(A)
        max_a_memo, max_a_ind = -1, -1
        for i in range(n):
            if A[i] > max_a_memo:
                max_a_memo, max_a_ind = A[i], i
        throw_off_damage = sorted([B[i] for i in range(n) if B[i] >= max_a_memo])

        cnt = 0
        if sum(throw_off_damage) >= h:
            # 投げつけまくるだけ
            while h > 0:
                h -= throw_off_damage.pop()
                cnt += 1
            return cnt
        else:
            cnt += len(throw_off_damage)
            h -= sum(throw_off_damage)
            assert(h > 0)
            return cnt + ((h + max_a_memo - 1) // max_a_memo)
        
        
    
    n, h = mi()
    A = []
    B = []
    for _ in range(n):
        a, b = mi()
        A.append(a)
        B.append(b)

    print(calc_min_attack(A, B, h))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from functools import reduce
from math import ceil

n, h = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort(key=lambda x: x[0], reverse=True)
max_a = ab[0][0]
ab = list(filter(lambda x: x[1] >= max_a, ab))

ab.sort(key=lambda x: x[1], reverse=True)
for i, v in enumerate(ab):
    h -= v[1]
    if h <= 0:
        print(i+1)
        exit()

res = ceil(h / max_a) + len(ab)
print(res)

Submission status: Accepted

Solution code:
n,h = map(int,input().split())
A = []
B = []
m = 0
for j in range(n):
    a,b = map(int,input().split())
    m = max(a,m)
    A.append(a)
    B.append(b)
B.sort(reverse=True)
for i in range(n):
    if B[i] > m:
        h -= B[i]
    else:
        print(i+1+(h-1)//m)
        break
    if h <= 0:
        print(i+1)
        break
else:
    print(n+1+(h-1)//m)

Submission status: Accepted

Solution code:
# ABC85 D 
import math

def main():
    N, H = list(map(int, input().split()))
    a_max = 0
    b_list = []

    for _ in range(N):
        a,b = list(map(int, input().split()))
        a_max = max(a, a_max)
        b_list.append(b)

    b_list = sorted(b_list)[::-1]
    
    cnt = 0
    for b in b_list:
        if b < a_max:
            break
        if H <= 0:
            break
        H -= b
        cnt += 1
    
    if H > 0:
        print(cnt + math.ceil(H / a_max))
    else:
        print(cnt)

if __name__ == "__main__":
    main()