Trang trại gà của nhà Bé Bo có \(n\) con gà siêu trứng đánh số từ \(1\) đến \(n\). Con gà \(i\ (1 \leq i \leq n)\) đẻ quả trứng đầu tiên ở giây \(p_{i}\), sau đó cứ \(t_{i}\) giây tiếp theo sẽ đẻ thêm một quả trứng.

Yêu cầu: Bạn hãy viết chương trình tính thời gian nhỏ nhất (tính bằng giây) để Bé Bo thu được ít nhất \(x\) quả trứng.

Dữ liệu vào:

+ Dòng thứ nhất chứa hai số nguyên dương \(n,x;\)

+ \(n\ d\)òng tiếp theo, dòng thứ \(i\ (1 \leq i \leq n)\) chứa hai số nguyên dương \(p_{i},t_{i}\ \left( 1 \leq p_{i},t_{i} \leq 500 \right).\)

Kết quả: Ghi ra file văn bản BAI3.OUT một số nguyên duy nhất là thời gian nhỏ nhất để Bé Bo thu được ít nhất \(x\) quả trứng.

Ví dụ:

Chú ý:

• 20% số test tương ứng với 20% số điểm có \(n = 1,\ \ x \leq 10^{15}\);

• 45% số test tương ứng với 45% số điểm có \(n \leq 20,\ \ x \leq 1000\);

• 35% số test tương ứng với 35% số điểm có \(n \leq 20,\ \ x \leq 10^{15}\).