P8647 [Lanqiao Cup 2017 NOI Qualifier AB] Dividing Chocolate.

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?

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 the maximum possible side length of the square chocolate pieces that can be cut.

Lanqiao Cup 2022 Provincial Contest Group A Problem I. Translated by ChatGPT 5