#include <fstream>
#include <string>

#define I_F "magica.in"
#define O_F "magica.out"
#define MAX 1000

using namespace std;

int p[MAX][2];
int n,m;
long ans;

void Input();
void Sell1();
int max(int a, int b);
void Dyna();
void Sell2();
void Output();

int main()
{
	Input();
	Sell1();
	if (ans<m)
		Dyna();
	Sell2();
	Output();
}

void Input()
{
	ifstream fin(I_F);
	fin>>n>>m;
	string ts;
	int i,j;
	getline(fin,ts);
	for (i=0; i<n; i++)
	{
		getline(fin,ts);
		for (j=0; j<ts.length(); j++)
			if (ts[j]!=' ')
				p[i][0]=p[i][0]*10+ts[j]-'0';
			else
				break;
		for (j++; j<ts.length(); j++)
			p[i][1]=p[i][1]*10+ts[j]-'0';
	}
	fin.close();
}

void Sell1()
{
	bool f[MAX]={false};
	int i,j,nt=n;
	for (i=0; i<n; i++)
		if (p[i][1]-m<=p[i][0])
		{
			ans+=p[i][0];
			nt--;
			f[i]=true;
		}
	
	for (i=0; i<n; i++)
		if (f[i])
			for (j=i+1; j<n; j++)
				if (!f[j])
				{
					f[i]=false;
					f[j]=true;
					p[i][0]=p[j][0];
					p[i][1]=p[j][1];
				}
	n=nt;
}

int max(int a, int b)
{
	if (a>b)
		return a;
	else
		return b;
}

void Dyna()
{
	int f[10000][MAX]={{0}};
	int d[MAX];
	int i,j;
	for (i=0; i<n; i++)
		d[i]=p[i][2]-p[i][1]-m;
	
	for (i=1; i<10000; i++)
	{
		for (j=0; j<n; j++)
			if (d[j]>i)
				f[i][j]=f[i][j-1];
			else
				f[i][j]=max(f[i][j-1],f[i-d[j]][j-1]+p[j][0]);
		if (f[i][n-1]>=m)
		{
			ans-=i;
			break;
		}
	}
}

void Sell2()
{
	for (int i=0; i<n; ans+=p[i++][1]);
	ans-=n*m;
}

void Output()
{
	ofstream fout(O_F);
	fout<<ans<<'\n';
	fout.close();
}