Space Voyage

Description:

Input:

The first input line contains space-separated integers n and c — the number of planets that the Beaver is going to visit and the number of days he is going to spend traveling, correspondingly.

The next n lines contain pairs of space-separated integers a_i, b_i (1 ≤ i ≤ n) — the number of suitcases he can bring to the i-th planet and the number of citizens of the i-th planet, correspondingly.

The input limitations for getting 30 points are:

• 1 ≤ n ≤ 100
• 1 ≤ a_i ≤ 100
• 1 ≤ b_i ≤ 100
• 1 ≤ c ≤ 100

The input limitations for getting 100 points are:

• 1 ≤ n ≤ 10⁴
• 0 ≤ a_i ≤ 10⁹
• 1 ≤ b_i ≤ 10⁹
• 1 ≤ c ≤ 10⁹

Due to possible overflow, it is recommended to use the 64-bit arithmetic. In some solutions even the 64-bit arithmetic can overflow. So be careful in calculations!

Output:

Print a single number k — the number of ways to choose x so as to travel for exactly c days. If there are infinitely many possible values of x, print -1.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Sample Input:

2 5
1 5
2 4

Sample Output:

1

Note:

In the first example there is only one suitable value x = 5. Then the Beaver takes 1 suitcase with 5 presents to the first planet. Here he spends 2 days: he hangs around on the first day, and he gives away five presents on the second day. He takes 2 suitcases with 10 presents to the second planet. Here he spends 3 days — he gives away 4 presents on the second and the third days and leaves the remaining 2 presents at the hotel. In total, the Beaver spends 5 days traveling.

For x = 4 or less the Beaver won't have enough presents for the second day on the first planet, so the voyage will end too soon. For x = 6 and more the Beaver will spend at least one more day on the second planet, and the voyage will take too long.