#define _CRT_SECURE_NO_DEPRECATE
#pragma comment(linker, "/STACK:512000000")
#include <iostream>
#include <algorithm>


typedef long long ll;


using namespace std;


ll a[100005];
ll b[100005];
ll dp[105][10005];


#define TASK "castle"


int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	freopen(TASK".in", "r", stdin);
	freopen(TASK".out", "w", stdout);
#endif // _DEBUG

	int n, s;
	cin >> n >> s;
	ll sum_a = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		sum_a += a[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= s; j++) {
			if (j + a[i] / b[i] <= s) {
				dp[i + 1][j + a[i] / b[i]] = max(dp[i + 1][j + a[i] / b[i]], dp[i][j] + a[i] - a[i] % b[i]);
			}
			else {
				dp[i + 1][s] = max(dp[i + 1][s], dp[i][j] + (s - j) * b[i]);
			}
			if (j + (a[i] + b[i] - 1) / b[i] <= s) {
				dp[i + 1][j + (a[i] + b[i] - 1) / b[i]] = max(dp[i + 1][j + (a[i] + b[i] - 1) / b[i]], dp[i][j] + a[i]);
			}
			else {
				dp[i + 1][s] = max(dp[i + 1][s], dp[i][j] + (s - j) * b[i]);
			}
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
		}
	}
	ll ans = 0;
	for (int j = 0; j <= s; j++) {
		ans = max(ans, dp[n][j]);
	}
	cout << sum_a - ans;
}