재테크 설계

시간 제한3초메모리 제한512 MB

요약

비용과 일일 이익이 주어진 투자 수단을 사서 일수를 최소화하는 문제입니다. d 일 후 일일 이익의 합 곱하기 d 가 비용의 합 더하기 M 을 넘게 만드는 최소 d 를 찾습니다.

난이도: 보통10점 중 6점
유형: 그리디, 정렬, 수학, 이분 탐색
정답자: 아직 제출이 없습니다

문제

책임감 있는 청년이 된 당신은 은퇴를 준비하기로 마음먹었다. 대략적인 계산을 해 본 결과, 편안히 은퇴하려면 최소 M유로가 필요하다는 것을 알아냈다.

현재 당신은 무일푼이지만, 다행히도 관대한 억만장자 친구가 이자 없이 원하는 만큼의 돈을 빌려주겠다고 제안했다. 이 돈을 주식 시장에 투자해 수익을 낸 뒤, 원금은 친구에게 돌려주고 나머지는 당신이 가지면 된다.

이용할 수 있는 투자 기회는 n개이고, i번째 투자에는 ci유로가 든다. 또한 컴퓨터 과학 실력을 발휘해 i번째 투자가 하루에 pi유로를 벌어들인다는 것을 예측했다. 친구에게 돈을 갚고 은퇴하는 데 필요한 최소 일수는 얼마인가?

예를 들어 첫 번째 샘플을 보자. 두 번째 투자(비용 15유로)만 사면 하루에 p2 = 10유로를 벌 수 있다. 이틀이 지나면 20유로를 벌어, 친구에게 빌린 15유로를 정확히 갚고 남은 수익 5유로를 가지고 은퇴할 수 있다. 하루 만에 순이익 5유로를 만드는 방법은 없으므로 이틀이 가장 빠르다.

입력

첫째 줄에는 투자 기회의 수 1 ≤ n ≤ 105와 은퇴에 필요한 최소 금액 1 ≤ M ≤ 109가 주어진다.

다음 n개의 줄이 주어진다. 각 줄 i에는 두 정수, 즉 이 투자의 일일 수익 1 ≤ pi ≤ 109와 초기 비용 1 ≤ ci ≤ 109가 있다.

출력

최적의 투자 전략을 따랐을 때, 투자금을 회수하고 최소 M유로를 가지고 은퇴하는 데 필요한 최소 일수를 출력한다.

예제3

예제 1
입력
```
2 5
4 10
10 15
```
예상 출력
```
2
```
예제 2
입력
```
4 10
1 8
3 12
4 17
10 100
```
예상 출력
```
6
```
예제 3
입력
```
3 5
4 1
9 10
6 3
```
예상 출력
```
1
```