#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cstdio>
#include <vector>
#include <functional>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>

using namespace std;

typedef pair<int, int> ipair;
typedef long long ll;

#define ALL(x) begin(x), end(x)

int du(int a, int b) {
	return a / b + !!(a % b);
}

int main() {
#ifdef _DEBUG
	freopen("in.txt", "r", stdin);
#else
	freopen("castle.in", "r", stdin);
	freopen("castle.out", "w", stdout);
#endif
	cin.sync_with_stdio(0);
	cin.tie(0);

	int n, s;
	cin >> n >> s;
	vector<int> a(n), d(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> d[i];
	}

	vector<vector<ll>> dp(n + 1, vector<ll>(s + 1));
	dp[0][s] = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= s; ++j) {
			for (int l = max(1, a[i] / d[i] - 10); l <= a[i] / d[i] + 10 && l <= j; ++l) {
				dp[i + 1][j - l] = max(dp[i + 1][j - l], dp[i][j] + (int)min((ll)a[i], (ll)d[i] * l));
			}
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
		}
	}

	cout << accumulate(ALL(a), 0LL) - dp[n][0] << "\n";
}
