#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

const int maxn = 2e5;

int a[maxn];
int k[maxn];
int r[maxn];
long long n, s, u;
bool w[maxn];

int main()
{
    freopen("castle.in", "r", stdin);
    freopen("castle.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> s;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> k[i];
        u += (r[i] = (a[i]-1)/k[i]+1);
    }
    if (u <= s) {
        cout << "0\n";
        return 0;
    }
    u -= s;
    set<pair<int, int>> se;
    for (int i = 0; i < n; ++i) {
        if (r[i] > 0) {
            se.insert({a[i]-k[i]*(r[i]-1), i});
        }
    }
    long long res = 0;
    while (u > 0) {
        auto p = *se.begin();
        se.erase(se.begin());
        if (w[p.second]) {
            int y = min(u, 1ll*r[p.second]);
            res += 1ll*y*k[p.second];
            u -= y;
            r[p.second] -= y;
        } else {
            res += p.first;
            --r[p.second];
            --u;
        }
        if (r[p.second] > 0) {
            se.insert({k[p.second], p.second});
        }
        w[p.second] = 1;
    }
    cout << res << '\n';
    return 0;
}
