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

#define MAXW 5000
#define MAXG 1000

int mat[2][MAXW + 1], v[MAXG][2];

int main()
{
    FILE *fin, *fout;
    int g, w, i, j;
    fin = fopen("energii.in", "r");
    fscanf(fin, "%d%d", &g, &w);
    for(i = 0; i < g; i++){
      fscanf(fin, "%d%d", &v[i][0], &v[i][1]);
    }
    fclose(fin);
    for(j = 1; j <= w; j++){
      mat[0][j] = -1;
    }
    for(i = 1; i <= g; i++){
      for(j = 1; j <= w; j++){
        mat[i % 2][j] = mat[(i - 1) % 2][j];
        if((v[i - 1][0] < j) && (mat[(i - 1) % 2][j - v[i - 1][0]] != -1) && (((mat[(i - 1) % 2][j - v[i - 1][0]] + v[i - 1][1]) < mat[i % 2][j]) || (mat[i % 2][j] == -1))){
          mat[i % 2][j] = mat[(i - 1) % 2][j - v[i - 1][0]] + v[i - 1][1];
        }else if((j <= v[i - 1][0]) && ((v[i - 1][1] < mat[i % 2][j]) || (mat[i % 2][j] == -1))){
          mat[i % 2][j] = v[i - 1][1];
        }
      }
    }
    fout = fopen("energii.out", "w");
    fprintf(fout, "%d", mat[g % 2][w]);
    fclose(fout);
    return 0;
}