Mikhail the Freelancer mơ ước hai điều: Trở thành một lập trình viên tuyệt vời và mua một căn hộ ở Moscow. Để trở thành một lập trình viên tuyệt vời, anh ta cần ít nhất p điểm kinh nghiệm, và một căn hộ có giá trị q đô la. Mikhail quyết tâm thực hiện ước mơ của mình bằng cách đăng ký làm việc tại một trang web tự do. Ông có đề xuất để làm việc trên n dự án riêng biệt. Mikhail đã đánh giá rằng việc tham gia vào dự án thứ i sẽ tăng trải nghiệm của anh ấy lên a_i điểm kinh nghiệm và mang lại b_i đô la mỗi ngày. Vì công việc tự do ngụ ý giờ làm việc linh hoạt, Mikhail có thể tự do ngừng làm việc trên một dự án bất cứ lúc nào và bắt đầu làm việc với một dự án khác. Làm như vậy, anh ta nhận được phần chia sẻ kinh nghiệm và tiền bạc tương ứng. Mikhail chỉ đang cố gắng trở thành một lập trình viên tuyệt vời, vì vậy tại mỗi thời điểm anh ta chỉ có thể làm việc trên một dự án. Tìm giá trị thực, bằng với số ngày tối thiểu Mikhail cần để biến giấc mơ của mình thành hiện thực.

Dữ liệu vào: Nhập từ tệp văn bản DREAMS.INP theo định dạng sau:

• Dòng đầu tiên chứa ba số nguyên n, p và q (1 ≤  n  ≤ 10⁶, 1 ≤  p ,  q ≤ 10⁶) là số lượng dự án, số điểm kinh nghiệm và số tiền cần thiết.
• Mỗi dòng trong n dòng tiếp theo chứa hai số nguyên a_i và b_i ( 1 ≤  a_i, b_i  ≤ 1 000 000 ) là sự gia tăng kinh nghiệm và thu nhập hàng ngày khi làm việc trong dự án thứ i

Dữ liệu ra: Ghi ra tệp văn bản DREAMS.OUT. In một giá trị thực là số ngày tối thiểu Mikhail cần để có được điểm kinh nghiệm và số tiền cần thiết.

Giải thích: Giả sử Mikhail được đề xuất làm việc trên ba dự án và a ₁  = 6 , b₁  = 2 , a₂  = 1 , b₂  = 3, a ₃  = 2, b₃  = 6. Ngoài ra, p  = 20 và q  = 20. Để đạt được mục tiêu của mình, Mikhail phải làm việc trong 2,5 ngày cho cả hai dự án thứ nhất và thứ ba. Thật vậy:

a ₁ x 2,5 +  a ₂ x 0 +  a ₃ x 2,5 = 6 x 2,5 + 1 x 0 + 2 x 2,5 = 20

b₁ x 2,5 +  b ₂  x 0 +  b ₃ x 2,5 = 2 x 2,5 + 3 x 0 + 6 x 2,5 = 20

Ví dụ:

Giới hạn:

• Có 30% số test ứng với 30% số điểm của bài có 1 ≤ n ≤ 10, 1 ≤ p,q ≤ 10³.
• Có 30% số test ứng với 30% số điểm của bài có 1 ≤ n ≤ 100, 1 ≤ p, q ≤ 10⁶.
• Có 40% số test ứng với 40% số điểm của bài có 1 ≤ n ≤ 10⁶, 1 ≤ p,q ≤ 10⁶.