#include<bits/stdc++.h>
using namespace std;
inline int read() 
{
	char c=getchar();
	int x=0,bj=1;
	while(c<'0'||c>'9') 
	{
		if(c=='-') 
		{
			bj=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9') 
	{
		x=x*10+(c^48);
		c=getchar();
	}
	return x*bj;
}
int n,m;
int num[31];
int a[31][101];
int w[31][101];
int f[31][1001];
int g[31][1001];
int main()
{
	n=read(),m=read();
	while(n+m!=-2)
	{
		memset(a,0,sizeof(a));
		memset(num,0,sizeof(num));
		memset(w,0,sizeof(w));
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		for(register int i=1;i<=n;i++)
		{
			register int x=read();
			int cnt=31;
			while(x%(1<<(--cnt)));
			a[cnt][++num[cnt]]=x/(1<<cnt);
			w[cnt][num[cnt]]=read();
		}
		register int cnt=31;
		while(m<=(1<<(--cnt)));
		for(register int t=0;t<=cnt;t++)
		{
			for(register int i=1;i<=num[t];i++)
			{
				for(register int j=10*num[t];j>=a[t][i];j--)
				{
					f[t][j]=max(f[t][j],f[t][j-a[t][i]]+w[t][i]);
				}
			}
		}
		for(register int j=0;j<=10*num[0];j++)
		{
			g[0][j]=f[0][j];
		}//对0进行初始化
		for(register int i=1;i<=cnt;i++)
		{
			for(register int j=0;j<=10*n;j++)//因为每位上最多就是10*n，可以节省时间
			{
				for(register int k=0;k<=j;k++)
				{
					g[i][j]=max(g[i][j],f[i][j-k]+g[i-1][min(10*n,k*2+((m>>(i-1))&1))]);
				}
			}
		}
		printf("%d\n",g[cnt][1]);
		n=read(),m=read();
	}
	return 0;
}