#include <iostream>
#include <vector>
#include <fstream>
#include <utility>
#include <algorithm>

using namespace std;

vector <int> a;
vector <int> k;
int d[101][10001];

int main()
{
    ifstream in;
    ofstream out;
    in.open("castle.in");
    out.open("castle.out");
    for (int i = 0; i < 101; i++) {
        for (int j = 0; j < 10001; j++) {
            d[i][j] = 1e9;
        }
    }
    for (int i = 0; i < 10001; i++) {
        d[0][i] = 0;
    }
    int n, s, b, c, su = 0;
    in >> n >> s;
    for (int i = 0; i < n; i++) {
        in >> b >> c;
        a.push_back(b);
        k.push_back(c);
    }
    for (int i = 0; i < n; i++) {
        d[i][0] = su;
        su += a[i];
    }
    d[n][0] = su;
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < s + 1; j++) {
            for (int z = 0; z < min(int(a[i - 1] / k[i - 1]) + 1, j + 1); z++) {
                d[i][j] = min(d[i][j], d[i - 1][j - z] + max(0, a[i - 1] - k[i - 1] * z));
            }
            d[i][j] = min(d[i][j], d[i][j - 1]);
        }
    }
    out << d[n][s];
    return 0;
}
