#include<stdio.h>
#include<stdlib.h>

int n, m, max_cap, i, gmc, cw, cv, j;
int w[10005], v[10005], u[10005];
int d[10005];
int sol;

int max_value(int x, int y)
{
    if(x > y)
        return x;
    else
        return y;
}

int main()
{
    FILE * in = fopen("knapsack.in", "r");

    fscanf(in, "%d %d", &n, &max_cap);

    for(i = 1; i <= n; i++)
    {
        fscanf(in, "%d %d", &w[i], &v[i]);
    }

    gmc = 0;

    u[0] = 1;

    for(i = 1; i <= n; i++)
    {
        cw = w[i];
        cv = v[i];
        for(j = gmc; j >= 0; j--)
        {
            if(u[j] == 1)
            {
                if(j + cw <= max_cap)
                {
                    d[j + cw] = max_value(d[j] + cv, d[j + cw]);
                    u[j + cw] = 1;

                    sol = max_value(d[j + cw], sol);

                    gmc = max_value(gmc, j + cw);
                }
            }

        }
    }

    printf("%d", sol);
}