#include <fstream>

using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int s=0,s1=0;
int n,G;
    struct rez{
    int g1;
    int p1;
    int d;}x[5000];


int main()
{cin>>n>>G;
if(n==0 || G==0) cout<<0;
else
{
    for(int i=1;i<=n;i++)
    {
        cin>>x[i].g>>x[i].p;
           x[i].d=x[i].p-x[i].g;}
    for(int i=1;i<=n-1;i++)
{
	for(int j=i+1;j<=n;j++)
	{
		if(x[i].d>x[j].d)
		{
		swap(x[i],x[j]);
		}
	}

}
for(int i=1;i<=n-1;i++)
{
    if(x[i].d==x[i-1].d)
    {
        if(x[i].p1<x[i-1].p1) swap(x[i],x[i-1]);
    }
}
} afisare();


    return 0;
}