#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;
const int INF = 2e9;

int get(int a, int k) {
    if (a % k == 0) return a / k;
    return a / k + 1;
}

int main() {
    freopen("castle.in", "r", stdin);
    freopen("castle.out", "w", stdout);
    int n, s;
    cin >> n >> s;
    vector<int> a(n);
    vector<int> k(n);
    int ss = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> k[i];
        ss += get(a[i], k[i]);
    }
   // cout << ss << endl;
    vector<vector<int> > dp;
    dp.assign(n, vector<int>(s + 1, INF));
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            for (int t = 0; t <= ss; t++) {
                dp[i][t] = max(a[i] - t * k[i], 0);
            }
        }
        else {
            for (int t = 0; t <= s; t++) {
                for (int q = 0; q <= min(get(a[i], k[i]), t); q++) {
                    dp[i][t] = min(dp[i - 1][t - q] + max(a[i] - q * k[i], 0), dp[i][t]);
                    //cout << i << " " << t << " " << dp[i][t] << endl;
                }
            }
        }
    }
    //cout << s << endl;
    cout << dp[n - 1][s];
    return 0;
}