/**************************************************************

    Problem: 1190

    User: yekehe

    Language: C++

    Result: Accepted

    Time:5932 ms

    Memory:960 kb

****************************************************************/

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int read()

{

    char c;while(c=getchar(),c!='-'&&(c<''||c>''));

    int x=,y=;c=='-'?y=-:x=c-'';

    while(c=getchar(),c>=''&&c<='')x=x*+c-'';

    return x*y;

}

int w[],v[],f[][];

void work(int i)//预处理

{

    for(int k=;k<=;k++)

        if(w[i]&(<<k)){

            for(int j=;j>=(w[i]>>k);j--)

                f[k][j]=max(f[k][j-(w[i]>>k)]+v[i],f[k][j]);

            return ;

        }

}

int main()

{

    while(){

        int N=read(),M=read(),ans=;

        if(N<&&M<)break;

        memset(f,,sizeof f);

            for(int i=;i<=N;i++)

                w[i]=read(),v[i]=read();

            for(int i=;i<=N;i++)work(i);

            for(int i=;i<=;i++)

                for(int j=;j<=;j++)

                    f[i][j]=max(f[i][j],f[i][j-]);

            for(int i=;i<=&&<<i<=M;i++){//枚举层数

                for(int j=min(,M>>i);j>=;j--){//枚举背包容量，类似01背包转移

                    for(int k=;k<=j;k++){

                        f[i][j]=max(f[i][j],f[i-][min((k<<)+(M>>i-&),)]+f[i][j-k]);//k*2是因为从上一层转移。

                        ans=max(ans,f[i][j]);

                    }

                }

            }

        printf("%d\n",ans);

    }

    return ;

}