// Instead of Moore, just sort by smallest # of pages, then by deadline.
// Still use binary search.

import java.util.*;
import java.io.*;


public class TaxedRSR_bad1 {
  public static int n,m;
  public static int book[][];
  public static long lo, hi;
  public static final double EPS = 1e-10;

  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(in.readLine());
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());
    book = new int[n][2];
    double minratio = Double.MAX_VALUE;
    double maxratio = 0;
    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(in.readLine());
      book[i][0] = Integer.parseInt(st.nextToken());
      book[i][1] = Integer.parseInt(st.nextToken());
      double r = 1.0*book[i][0]/book[i][1];
      if (r < minratio) minratio = r;
      if (r > maxratio) maxratio = r;
    }
    lo = (long)Math.ceil(minratio);
    hi = n*(long)Math.ceil(maxratio);
    // Sort by increasing deadline, then by increasing length:
    Arrays.sort(book,new Comparator() {
      public int compare(Object o1, Object o2) {
        int[] a = (int[])o1;
        int[] b = (int[])o2;
        if (a[0] != b[0]) return a[0]-b[0];
        else return a[1]-b[1];
      }
      });
//    Arrays.sort(book,Comparator.comparingInt(a->a[1]).thenComparing(a->a[0]));
//    Arrays.sort(book,Comparator.comparingInt(a->a[1]));

    long best = search(lo,hi,hi);
    System.out.println(best);
  }

  public static long search(long lo, long hi, long best) {
    if (lo > hi) {
      return best;
    }
    long mid = (lo+hi)/2;
    int late = lateness(mid);
    if (late <= m) {
      return search(lo,mid-1,Math.min(best,mid));
    } else { // late > m:
      return search(mid+1,hi,best);
    }
 }

  public static int lateness(long rate) {
    long total = 0;
    int i;
    // just keep reading until a book misses a deadline; drop that book
    // and keep reading
    int late = 0;
    for (i = 0; i < n; i++) {
      if (1.0*(total + book[i][0])/rate <= book[i][1]) {
        total += book[i][0];
      } else late++;// else break;
    }
    return late;
  }
}