Nhà hàng Nem Anh Dân nhận được một đơn hàng đặt M cái nem, nhưng trong kho đã hết sạch nem
và phải làm lại từ đầu. Nhà hàng có N công nhân gói nem, công nhân thứ i làm được Ai cái nem mỗi
ngày, nhưng phải được nghỉ ngơi 1 ngày sau Bi ngày làm việc liên tiếp.
Ví dụ: công nhân thứ i có Ai = 20; Bi = 5 nghĩa là mỗi ngày công nhân này gói được 20 cái nem, và cứ làm 5 ngày liên tiếp thì phải nghỉ 1 ngày. Chẳng hạn 11 ngày thì công nhân này chỉ gói được 200 cái nem, vì gói 5 ngày rồi nghỉ 1 ngày, rồi gói 5 ngày.
Yêu cầu: Các bạn hãy tính số lượng ngày tối thiểu để làm được M cái nem theo đơn hàng.
Dữ liệu: Vào từ file NEMANHDAN.INP gồm:
+ Dòng đầu tiên gồm số 2 số nguyên dương N và M.
+ N dòng tiếp theo, dòng thứ i gồm 2 số nguyên dương Ai và Bi của nhân viên thứ i.
Kết quả: Ghi ra file NEMANHDAN.OUT một số duy nhất là số ngày tối thiểu.
Input:
2 30
2 5
1 9
Output:
11
Giới hạn:
+ Có 40% số điểm: N ≤ 100; 1 ≤ M, Ai, Bi ≤ 1E4
+ Có 60% số điểm còn lại: N ≤ 100; 1 ≤ M, Ai, Bi ≤ 10E15