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

using namespace std;

int main() { 
#ifndef LOCAL
    freopen("castle.in", "r", stdin);
    freopen("castle.out", "w", stdout);
#endif // LOCAL
    int n, s;
    cin >> n >> s;
    vector<int> a(n), k(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> k[i];
    }

    vector<int> prev(s + 1, 0), cur(s + 1, 0);
    cur[0] = a[0];
    for (int j = 1; j <= s; j++) {
        cur[j] = max(cur[j - 1] - k[0], 0);
    }
    swap(cur, prev);
    for (int i = 1; i < n; i++) {
        cur[0] = prev[0] + a[i];
        for (int j = 1; j <= s; j++) {
            int L = 0, R = j;
            while (R - L > 3) {
                int m1 = (2 * L + R) / 3, m2 = (L + 2 * R) / 3;
                int x1 = prev[j - m1] + max(a[i] - m1 * k[i], 0);
                int x2 = prev[j - m2] + max(a[i] - m2 * k[i], 0);
                if (x1 < x2) {
                    R = m2;
                } else {
                    L = m1;
                }
            }
            cur[j] = prev[j - L] + max(a[i] - L * k[i], 0);
            for (int h = L + 1; h <= R; h++) {
                int x = prev[j - h] + max(a[i] - h * k[i], 0);
                cur[j] = min(cur[j], x);
            }
        }
        swap(cur, prev);
    }

    cout << prev.back() << endl;

    return 0;
}
