Fair Chocolate Square Partitioning

On Children's Day, K children come to Xiao Ming's house as guests. Xiao Ming has N chocolate bars stored in his collection where the i^th chocolate has dimensions H_i × W_i (formed by a grid of squares).

In order to be fair, Xiao Ming wants to cut exactly K square pieces (one for each child) from these bars. The cut square pieces must satisfy:

1. The shape is a square with an integer side length.
2. All squares are of the same size.

For example, a chocolate bar of size $6\times 5$ can be cut into either six $2\times 2$ squares or two $3\times 3$ squares.

Each bar i can yield at most $\lfloor \frac{H_i}{s} \rfloor \times \lfloor \frac{W_i}{s} \rfloor$ squares for a given square side length s. Determine the maximum integer s such that the total number of squares obtained from all bars is at least K.

This can be formulated as: Find the maximum integer s such that $$ \sum_{i=1}^{N} \left\lfloor \frac{H_i}{s} \right\rfloor \times \left\lfloor \frac{W_i}{s} \right\rfloor \ge K. $$

inputFormat

The first line contains two integers N and K ($1 \le N \le 10^5$, $1 \le K \le 10^9$), representing the number of chocolate bars and the number of children, respectively.

Each of the next N lines contains two integers H_i and W_i ($1 \le H_i, W_i \le 10^9$), representing the dimensions of the i^th chocolate bar.

outputFormat

Output a single integer, the maximum possible side length of the square chocolate pieces that can be cut from the bars such that at least K pieces can be obtained.

sample

1 2
6 5

3