Maximum Wood Length for Customer Order

You are given (n) wood suppliers. Each supplier has a fixed number of wood pieces, all of the same length. The (i)-th supplier provides wood pieces of length (L_i) and has (C_i) pieces. A customer requires (m) wood pieces, all having the same length. You are allowed to cut a longer piece into several shorter pieces, but you cannot join pieces together. Your task is to determine the maximum possible length (x) (an integer) such that after cutting the available wood pieces into pieces of length (x), you can obtain at least (m) wood pieces.

For example, if (n=2) and (m=30), and the suppliers provide the following:

• Supplier 1: length (12) and count (10).
• Supplier 2: length (5) and count (10).

Then, cutting the wood yields:

• From supplier 1: Each wood of length 12 can be cut into (\lfloor 12/5 \rfloor = 2) pieces, giving a total of (10 \times 2 = 20) pieces.
• From supplier 2: Each wood of length 5 yields (\lfloor 5/5 \rfloor = 1) piece, giving a total of (10 \times 1 = 10) pieces.

Thus, the total number of pieces is 30, and the answer is (5).

inputFormat

The first line contains two space-separated integers (n) (the number of suppliers) and (m) (the required number of wood pieces). Each of the next (n) lines contains two space-separated integers (L_i) and (C_i), where (L_i) is the length of the wood pieces provided by the (i)-th supplier, and (C_i) is the count of pieces available from that supplier.

outputFormat

Output a single integer: the maximum possible length (x) such that at least (m) wood pieces of length (x) can be obtained.

sample

2 30
12 10
5 10

5