#include <fstream>

using namespace std;
ifstream f ("rucsac.in");
ofstream g ("rucsac.out");
int
int main()
{
    f>>n>>G;
    for (i=1;i<=n;i++)
    {
        f>>gg>>p;
        for (j=G-gg;j>=1;j--)
        {
            if (a[j]>0)
            a[j+gg]=a[j]+p;
        }

    }

    return 0;
}