Description

On Children’s Day, there are $K$ children visiting Xiaoming’s home. Xiaoming takes out his treasured chocolates to treat them.

Xiaoming has a total of $N$ chocolate bars. The $i$-th bar is a rectangle made up of a grid of size $H_i \times W_i$.

To be fair, Xiaoming needs to cut out $K$ pieces of chocolate from these $N$ bars and give them to the children. The cut pieces must satisfy:

1. The shape is a square, and the side length is an integer.
2. All pieces are of the same size.

For example, a $6 \times 5$ chocolate bar can be cut into $6$ pieces of $2 \times 2$ chocolate, or $2$ pieces of $3 \times 3$ chocolate.

Of course, the children all want the chocolate to be as large as possible. Can you help Xiaoming compute the maximum possible side length?

Input Format

The first line contains two integers $N$ and $K$. $(1 \le N,K \le 10^5)$.

The next $N$ lines each contain two integers $H_i$ and $W_i$. $(1 \le H_i,W_i \le 10^5)$.

The input guarantees that each child can get at least one $1 \times 1$ piece of chocolate.

Output Format

Output the maximum possible side length of the square chocolate pieces that can be cut.

2 10  
6 5  
5 6  

2

Hint

Lanqiao Cup 2022 Provincial Contest Group A Problem I.

Translated by ChatGPT 5