#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 1e9;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
typedef long long ll;
ll n,m;
#define data data_
const int N = 1e6;
struct data{
    ll len, ddl;
} p[N];

ll q[N];
ll h = 1, t = 1;
ll getpos(ll id, ll spd){
    ll l = 0, r = t ,res = -1;
    while (l<=r) {
        ll mid = (l+r) >> 1;
        if (q[mid] + p[id].len <= p[id].ddl * spd) {
            l = mid + 1;
            res = mid;
        } else {
            r = mid -1;
        }
    }
    return res;
}
bool check(ll spd){
    h = t = 0;
    q[h] =0;
    rep(i,1,n) {
        ll pos = getpos(i ,spd);
        if (pos == -1) continue;
        ll cur = p[i].len + q[pos];
        if (pos == t || q[pos + 1] >= cur){
            q[pos + 1] = cur;
            if (pos == t) t ++;
        }
    }
    rep(i,0,t) q[i] = 0;
    return t >= n-m;
}
bool cmp(data a, data b) {
    return (a.ddl < b.ddl) || (a.ddl == b.ddl && a.len < b.len);
}
int main(){
    
    cin >> n >> m;
    rep(i,1,n){
        cin >> p[i].len >> p[i].ddl;
    }

    /*n = 100; m= 0;
    rep(i,1,n) {p[i].len = 1,p[i].ddl = i;}
    sort(p+1, p+1+n, cmp);
    */
     //rep(i,1,n) cout << p[i].len << " " << p[i].ddl <<endl;
    ll l = 0, r = 1e12 ,ans = -1;
    while (l<=r) {
        ll mid = (l+r)>>1;
        if (check(mid)) { r = mid - 1; ans = mid;} else
            l = mid + 1;
    }
    cout << ans;
}