도서관의 장서 점검 로봇이 서가 \(N\)곳을 정해진 순서대로 방문하며 모든 책을 스캔해야 한다.

\(i\)번째 서가로 이동하는 데에는 스캔 속도와 무관하게 \(m_i\)분이 걸리고, 그 서가에는 책이 \(b_i\)권 있다. 로봇의 스캔 속도를 양의 정수 \(k\)로 설정하면 \(1\)분에 책 \(k\)권을 스캔하므로, \(i\)번째 서가의 스캔에는 \(\lceil b_i / k \rceil\)분이 걸린다. 속도는 처음에 한 번만 설정할 수 있다.

도서관이 닫을 때까지 \(T\)분이 남아 있다. 이동 시간과 스캔 시간을 합쳐 \(T\)분 안에 점검을 끝낼 수 있는 스캔 속도 \(k\)의 최솟값을 구하여라. 속도가 빠를수록 로봇의 배터리가 많이 소모되므로 가능한 한 느리게 설정하고 싶다.

• \(1 \le N \le 100\,000\)
• \(0 \le m_i \le 10^6\)
• \(1 \le b_i \le 10^9\)
• \(m_1 + \dots + m_N + N \le T \le 10^{18}\) (즉 답은 항상 존재한다)

첫째 줄에 서가의 수 \(N\)과 남은 시간 \(T\)가 공백으로 구분되어 주어진다.

다음 \(N\)개의 줄에 걸쳐 \(i\)번째 줄에 이동 시간 \(m_i\)와 책의 수 \(b_i\)가 공백으로 구분되어 주어진다.

점검을 제시간에 끝낼 수 있는 최소 스캔 속도를 출력한다.

riseoj 작성

출처 Original