#include <fstream>
using namespace std;

int a[5002], b[5002];

int m(int g, int k){
    
    if(g<=0 || k<=0){
            return 0;
            }
    else{
         if(g<a[k]){ return(m(g,k-1));} 
         else {
              int y,u;
              y=m(g-a[k],k-1)+b[k];
              u=m(g,k-1);
              if(y<u){return(u);} else {return(y);}
              }
         }
    }


int main(){
    ifstream inr ("rucsac.in");
    ofstream our ("rucsac.out");
    int n,q;
    inr >> n;
    inr >> q;
    for(int i=1; i<=n; i++){
            inr >> a[i];
            inr >> b[i];
            }
    our << m(q,n);
    }