Maximize Square Side Length

You are given N rectangular sheets of paper. Each sheet has a grid drawn on it of size \(W \times H\) (the grid covers the entire sheet). Your task is to cut out exactly K squares (from the given N sheets) such that all the squares have the same side length, and this side length is as large as possible. The side length of the cut squares must be an integer, and each square must be cut along the grid lines.

For a sheet with dimensions \(W \times H\), if you choose a square side length \(s\), you can cut \(\left\lfloor \frac{W}{s} \right\rfloor \times \left\lfloor \frac{H}{s} \right\rfloor\) squares out of that sheet. You need to choose the maximum possible integer \(s\) such that the total number of squares obtained from all sheets is at least \(K\). If no valid square side length can produce \(K\) squares, output 0.

Example: Suppose \(N=2\), with the first sheet of size \(4 \times 3\) and the second sheet of size \(5 \times 4\), and \(K=6\). For \(s=2\), the number of squares from the first sheet is \(\left\lfloor \frac{4}{2} \right\rfloor \times \left\lfloor \frac{3}{2} \right\rfloor = 2 \times 1 = 2\) and from the second sheet is \(\left\lfloor \frac{5}{2} \right\rfloor \times \left\lfloor \frac{4}{2} \right\rfloor = 2 \times 2 = 4\). Total squares = 6 which is exactly \(K\). It can be verified that this is the maximum possible \(s\), so the answer is 2.

inputFormat

The first line contains two integers N and K, where N is the number of sheets and K is the number of squares you need to cut out.

Each of the following N lines contains two integers W and H, representing the width and height of the grid on that sheet.

Example:

2 6
4 3
5 4

outputFormat

Output a single integer representing the maximum possible integer side length \(s\) such that it is possible to obtain at least \(K\) squares from the given sheets. If it is impossible, print 0.

sample

2 6
4 3
5 4

2