Vào ngày Quốc tế Thiếu nhi, có $K$ bạn nhỏ đến nhà Minh chơi. Minh đem sô-cô-la quý mà mình cất giữ ra chiêu đãi các bạn nhỏ.

Minh có tổng cộng $N$ thanh sô-cô-la, trong đó thanh thứ $i$ là hình chữ nhật gồm $H_i \times W_i$ ô vuông.

Để công bằng, Minh cần cắt ra $K$ miếng sô-cô-la từ $N$ thanh này để chia cho các bạn nhỏ. Các miếng sô-cô-la cắt ra phải thỏa mãn:

1. Có hình vuông, độ dài cạnh là số nguyên.

2. Kích thước bằng nhau.

Ví dụ, một thanh sô-cô-la $6 \times 5$ có thể cắt ra $6$ miếng $2 \times 2$ hoặc $2$ miếng $3 \times 3$.

Tất nhiên các bạn nhỏ đều mong nhận được miếng sô-cô-la càng lớn càng tốt, bạn có thể giúp Minh tính xem độ dài cạnh lớn nhất là bao nhiêu không?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $K$. $(1 \le N,K \le 10^5)$.

$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $H_i$ và $W_i$. $(1 \le H_i,W_i \le 10^5)$.

Dữ liệu vào đảm bảo mỗi bạn nhỏ nhận được ít nhất một miếng sô-cô-la $1 \times 1$.

Dữ liệu ra

In ra độ dài cạnh lớn nhất có thể của các miếng sô-cô-la hình vuông được cắt ra.

Ví dụ

Input

2 10  
6 5  
5 6

Output

2