#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;
pair <int,int> v[1001];
int d[2][5001];
int main()
{
    FILE *fin=fopen ("energii.in","r");
    FILE *fout=fopen ("energii.out","w");
    int n,k,t;
    fscanf (fin, "%d%d", &n, &k);
    for (int i=1; i<=n; i++){
        fscanf (fin, "%d%d", &v[i].first, &v[i].second);
        v[i].second=-v[i].second;
    }
    t=1;
    for (int i=1; i<=n; i++){
        for (int j=0; j<=k; j++){
            d[t][j] = d[1-t][j];
            if (j >= v[i].first && d[1-t][j-v[i].first]+v[i].second < d[t][j])
                d[t][j] = d[1-t][j-v[i].first]+v[i].second;
        }
        t = 1-t;
    }
    fprintf (fout, "%d", -d[1-t][k]);
    return 0;
}