#include <cstdio>

using namespace std;
FILE* f, * g;

struct bla
{
    int gr, pr;
}v[5002];
int cost[4][10002];

int main()
{
    f = fopen("rucsac.in", "r");
    g = fopen("rucsac.out", "w");
    int n, G;
    fscanf(f, "%d %d", &n, &G);
    for (int i = 1;i <= n;++i)
        fscanf(f, "%d %d", &v[i].gr, &v[i].pr);
    int lc = 1, lp = 0;
    for (int i = 1;i <= n;++i)
    {
        for (int j = 1;j <= G;++j)
            if (v[i].gr <= j)
            {
                if (cost[lp][j] > cost[lp][j - v[i].gr] + v[i].pr)
                    cost[lc][j] = cost[lp][j];
                else
                    cost[lc][j] = cost[lp][j - v[i].gr] + v[i].pr;
            }
            else
                cost[lc][j] = cost[lp][j];
        lc ^= 1;
        lp ^= 1;
    }
    fprintf(g, "%d", cost[lp][G]);
    fclose(f);
    fclose(g);
    return 0;
}