Chuyến du hành vũ trụ

Một nhà du hành chuẩn bị cho chuyến đi thăm $n$ hành tinh. Với hành tinh thứ $i$, $a_i$ là số vali quà được phép mang xuống hành tinh đó, và $b_i$ là số cư dân của hành tinh.

Quà được đóng gói trong các vali, mỗi vali chứa đúng $x$ món quà (cùng một giá trị $x$ cho mọi vali). Nhà du hành mang lên tàu tổng cộng $a_1+a_2+\dots +a_n$ vali. Khi đến hành tinh thứ $i$, ông mang xuống $a_i$ vali, tức là $a_i·x$ món quà.

Diễn biến trên mỗi hành tinh:

• Ngày đầu tiên: ông đi dạo, làm quen với cư dân, không tặng quà.
• Từ ngày thứ hai trở đi: mỗi ngày ông tặng cho mỗi người trong $b_i$ cư dân đúng một món quà (tức mỗi ngày phát đi $b_i$ món).
• Ông rời hành tinh vào buổi tối của ngày mà số quà còn lại ít hơn $b_i$ (không đủ để phát cho ngày hôm sau). Số quà thừa được để lại.

Như vậy số ngày ở hành tinh thứ $i$ là $1+\lfloor {\displaystyle \frac{a_i·x}{b_i}}\rfloor$. Thời gian bay giữa các hành tinh coi như bằng $0$.

Nhà du hành muốn chuyến đi kéo dài đúng $c$ ngày. Hãy đếm số cách chọn số nguyên dương $x$ để tổng thời gian của chuyến đi bằng đúng $c$ ngày. Nếu có vô số giá trị $x$ thỏa mãn, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $c$ — số hành tinh và số ngày mong muốn.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$ và $b_i$.

Dữ liệu ra

In ra một số nguyên — số cách chọn số nguyên dương $x$ để chuyến đi kéo dài đúng $c$ ngày, hoặc $-1$ nếu có vô số giá trị $x$ thỏa mãn.

Ràng buộc

• $1\le n\le {10}^4$
• $0\le a_i\le {10}^9$
• $1\le b_i\le {10}^9$
• $1\le c\le {10}^9$

Lưu ý: các giá trị trung gian trong quá trình tính toán có thể rất lớn, vượt quá phạm vi số nguyên 64-bit.

Ví dụ