#include <stdio.h>
#include <stdlib.h>
#define NMAX 5001
#define GMAX 10001
int W[NMAX],P[NMAX],profit[GMAX];
int main()
{
    FILE *fin, *fout;
    int n,G,i,j,ans;
    fin = fopen("rucsac.in","r");
    fout = fopen("rucsac.out","w");
    fscanf(fin,"%d %d",&n,&G);
    for(i=0;i<G;i++)
        fscanf(fin,"%d %d",&W[i],&P[i]);
    for(j=1;j<=G;j++)
        profit[j] = -1;
    for(i=0;i<n;i++)
        for(j=G-W[i];j>=0;j--)
            if(profit[j]!=-1 && profit[j] + P[i] > profit[j+W[i]])
                profit[j+W[i]] = profit[j] + P[i];
    ans = 0;
    for(j=0;j<=G;j++)
        ans = ans > profit[j] ? ans : profit[j];
    fprintf(fout,"%d\n",ans);
    fclose(fin);
    fclose(fout);
    return 0;
}