儿童节有k个小朋友，老师准备了n块巧克力。每块巧克力都是矩形的，可以将一块巧克力切成若干块正方形，但不能将多块拼成一块。每个小朋友分到一块正方形巧克力。求小朋友们能分到的最大边长。
第一行两个整数n和k。 接下来n行，每行两个整数Hi和Wi，表示每块巧克力的长和宽。
一行一个整数，表示最大边长。
2 10 6 5 5 6
2
对于30%的数据，n≤10，k≤100 对于100%的数据，n≤100000，k≤109，Hi,Wi≤105