蓝桥杯2017-省AB-分巧克力

N, K = map(int, input().split())

c = []
for _ in range(N):
    H, W = map(int, input().split())
    c.append((H, W))

def can_cut(mid):
    # 检查边长为 mid 时，能不能切出至少 K 块
    total = 0
    for h, w in c:
        total += (h // mid) * (w // mid)
        if total >= K:
            return True
    return False

lo, hi = 1, 100000
while lo < hi:
    mid = (lo + hi + 1) >> 1
    if can_cut(mid):
        lo = mid
    else:
        hi = mid - 1

print(lo)