#include <iostream>
#include <c++/set>
#include <c++/tuple>

using namespace std;

int main() {
    freopen("castle.in", "r", stdin);
    freopen("castle.out", "w", stdout);
    long long n, sold, need = 0;
    cin >> n >> sold;
    multiset<tuple<long long, long long, long long>> out;
    long long i;
    for (i = 0; i < n; i++)
    {
        long long a, k;
        cin >> a >> k;
        need += (a - 1) / k + 1;
        auto x = (a - 1) / k + 1;
        out.insert(make_tuple(a - k * (x - 1), x, k));
    }
    long long res = 0;
    while (need > sold)
    {
        auto c = *out.begin();
        out.erase(out.begin());
        if (get<2>(c) != 0)
        {
            res += get<0>(c);
            need--;
            if (get<1>(c) > 1)
                out.insert(make_tuple(get<2>(c), get<1>(c) - 1, 0));
        }
        else
        {
            long long take = min(need - sold, get<1>(c));
            need -= take;
            res += get<0>(c) * take;
        }
    }
    cout << res;
}

/*
1 10
8 1

3 3
4 2
1 1
10 8
 */