#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <utility>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <time.h>
#define forn(i, n) for (int i = 0; i < (n); i++)
#define fornn(i, q, n) for (int i = (q); i < (n); i++)
#define times clock() * 1.0 / CLOCKS_PER_SEC
using namespace std;

typedef long long ll;

int solve();
int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#else
	freopen("castle.in", "r", stdin), freopen("castle.out", "w", stdout);
#endif
	solve();
	return 0;
}

vector<pair<int, int> > G;

ll dp[107][10007];

int solve() {
	int n, s;
	scanf("%d %d", &n, &s);
	G.resize(n);
	forn(i, n) {
		scanf("%d %d", &G[i].first, &G[i].second);
	}
	forn(i, n + 1) {
		forn(j, s + 1) {
			dp[i][j] = 1000000000000000007;
		}
	}
	forn(j, s + 1) {
		dp[0][j] = 0;
	}
	fornn(i, 1, n + 1) {
		forn(j, s + 1) {
			double curt = times;
			forn(k, j + 1) {
				int col = j - k;
				if (times - curt > 0.0000001) break;
				ll pp = max(0, G[i - 1].first - G[i - 1].second * col);
				dp[i][j] = min(dp[i][j], dp[i - 1][k] + pp);
			}
		}
	}
	ll m = 1000000000000000007;
	forn(i, s + 1) {
		m = min(m, dp[n][i]);
	}
	cout << m;
	return 0;
}