농장의 공동 급수 시간

문제

한 농장은 여러 재배 구역에서 같은 시간 동안 급수 장치를 가동하려 한다. 구역마다 물을 담아 두는 전용 물통이 하나씩 있고, 농장 중앙에는 필요한 구역에 물을 나누어 줄 수 있는 예비 물탱크가 있다. 농장 관리자는 모든 구역의 장치를 동시에 켜서 정수 시간만큼 가동한 뒤 동시에 끄기로 했다. 가동 시간은 0 이상 H 이하의 정수 T로 정한다. 구역 i의 전용 물통에는 처음에 A_i만큼의 물이 들어 있다. 이 구역의 급수 장치는 한 시간에 B_i만큼의 물을 사용하므로, T시간 가동하려면 정확히 B_i × T만큼의 물이 필요하다. 처음 들어 있는 물은 해당 구역에서만 사용할 수 있다. 어떤 구역의 전용 물통에 물이 남더라도 다른 구역의 물통이나 중앙 물탱크로 옮길 수는 없다. 가동 중에 비가 오거나 외부에서 물이 추가로 들어오는 일도 없다. 중앙 물탱크에는 처음에 W만큼의 물이 있다. 관리자는 장치를 켜기 전에 이 물을 원하는 구역들에 나누어 줄 수 있다. 각 구역에 나누어 주는 양은 0 이상의 정수이며, 모든 구역에 나누어 준 양의 합은 W를 넘을 수 없다. 전용 물통의 용량에는 제한이 없고, 물을 옮길 때 손실도 생기지 않는다. 중앙 물탱크의 물을 전부 사용할 필요는 없다. 정한 시간 동안 어느 한 구역이라도 필요한 물을 모두 공급받지 못하면 그 시간은 선택할 수 없다. 반대로 각 구역의 전용 물통에 있는 물과 중앙에서 보충한 물을 합쳐 필요한 양을 충족한다면 선택할 수 있다. 장치를 켠 뒤 구역별로 가동 시간을 달리하거나 잠시 멈추는 방식은 허용하지 않는다. 모든 구역에 같은 T를 적용해야 한다. 초기 물의 양과 시간당 사용량, 중앙 물탱크의 물의 양이 주어질 때 선택할 수 있는 가장 긴 가동 시간을 구한다. 출력하는 시간은 H를 넘을 수 없다. 양의 정수 시간 동안 가동할 수 없으면 0을 출력한다. 물을 나누어 주는 방법이 여러 개여도 가동 시간의 최댓값만 구하며, 실제 분배 방법은 출력하지 않는다.

입력

첫째 줄에 정수 N, H, W가 주어진다. 1 ≤ N ≤ 20,000, 1 ≤ H ≤ 1,000,000, 0 ≤ W ≤ 1,000,000,000,000이다.
다음 N개 줄에는 구역별 정수 A_i, B_i가 주어진다. 0 ≤ A_i ≤ 1,000,000,000, 1 ≤ B_i ≤ 1,000이다.
물의 양과 시간은 각각 문제에서 정한 단위를 사용한다.

출력

모든 구역에서 공통으로 선택할 수 있는 최대 정수 가동 시간을 출력한다. 양의 정수 시간을 선택할 수 없으면 0을 출력한다.

3 10 9
4 2
0 1
10 3

3

2 8 0
0 1
20 2

0

2 5 3
20 2
10 1

5

출처: Devin.KR 자체 제작