#!/usr/bin/python

#import heapq

def hInsert(d):
    global heap
    global nHeap

#    print nHeap

    heap[nHeap] = d
    pos = nHeap
    nHeap += 1

    while pos != 0:
        parent = (pos - 1) // 2
        if heap[parent][0] >= heap[pos][0]:
            break
        (heap[parent],heap[pos]) = (heap[pos],heap[parent])
        pos = parent

def hRemove():
    global heap
    global nHeap

    nHeap -= 1

    heap[0] = heap[nHeap]

    pos = 0

    while pos < nHeap // 2:
        c = 2 * pos + 1
        if c < nHeap - 1 and heap[c+1][0] > heap[c][0]:
            c += 1
        if heap[pos][0] >= heap[c][0]:
            break
        (heap[pos],heap[c]) = (heap[c],heap[pos])
        pos = c

def countLate(jobList,rate):
    nLate = 0
    total = 0

    global m
    global heap
    global nHeap

#    h = []

    nHeap = 0

    for j in jobList:
#        k = list(j)
#        total += k[0]
#        k[0] *= -1
#        heapq.heappush(h,k)
        total += j[0]
        hInsert(j)

#        if (total + rate - 1) // rate > k[1]:
        if (total + rate - 1) // rate > j[1]:
            nLate += 1
            if nLate > m:
                return nLate
#            total += h[0][0]
            total -= heap[0][0]
#            heapq.heappop(h)
            hRemove()

    return nLate

(n,m) = map(int,raw_input().split())

heap = [None]*n
nHeap = 0

low = 1
high = 0
jobs = []
for i in xrange(n):
    j = map(int,raw_input().split())
    jobs.append(j)
    high += j[0]

jobs.sort(key=lambda tup:tup[1])

while low < high:
    mid = (low + high) // 2
    nLate = countLate(jobs,mid)
    if nLate > m:
        low = mid + 1
    else:
        high = mid

print low