#include <iostream>
#include <fstream>
using namespace std;


int main(){
    ifstream inr ("rucsac.in");
    ofstream our ("rucsac.out");
    int n,q,u,v,e=0;
    inr >> n;
    inr >> q;
    int a[q+1][3],b;
    for(int j=1; j<=q; j++){
                    a[j][2]=0;
                    }
    for(int i=1; i<=n; i++){
            for(int j=1; j<=q; j++){
                    a[j][1]=a[j][2];
                    a[j][2]=0;
                    }
            inr >> a[0][2];
            inr >> b;
            a[a[0][2]][2]=b;
            e=a[1][2];
            for(int k=1; k<=q; k++){
                     if(a[k][1]!=0){
                                   u=k+a[0][2];
                                   v=a[k][1]+b;
                                   if(a[k][1]>a[k][2]){a[k][2]=a[k][1];}
                                   if(u<=q){
                                            if(v>a[u][2]){a[u][2]=v;}
                                            }
                                   }
                     if(e<a[k][2]){e=a[k][2];}
                    }
            }  
    our << e;
    }