#include <stdio.h>

int main(void){
    int N,W;
    int i,j,max=0;
    int date[101][2]={};//date[N+1[2]
    int table[101][10001]={};//table[N+1][W+1]
    scanf("%d %d",&N,&W);
    for(i=1;i<N+1;i++){
        scanf("%d",&date[i][0]);
        scanf("%d",&date[i][1]);//1~N?????????????????????????´?(Vn,Wn)
    }
    
    for(i=1;i<N+1;i++){
       // use = 0;//????????????????????¨?????¢??????
        for(j=1;j<W+1;j++){
            if(date[i][1] > j){
                table[i][j] = table[i-1][j];
            }else{//?????¨????????????????????§???????????????????????¨??£??\
                if(table[i-1][j] >= table[i-1][j - date[i][1]] + date[i][0]){
                    table[i][j] = table[i-1][j];
                }else{
                    table[i][j] = table[i-1][j - date[i][1]] + date[i][0];
                }
                /*
                if(use){
                    if(table[i-1][j] >= table[i][j-1]){
                        table[i][j] = table[i-1][j];
                        use = 0;
                    }else{
                        table[i][j] = table[i-1][j-1];
                    }
                }else{
                    if(table[i][j-1] >= table[i-1][j - date[i][1]] + date[i][0]){
                        table[i][j] = table[i][j-1];
                    }else{
                        table[i][j] = table[i-1][j - date[i][1]] + date[i][0];
                        use = 1;
                    }
                }*/
                /*
                if(table[i-1][j] > table[i][j - date[i][1]] + date[i][0]){//?????¨?¨???§????????§????????¨???
                    table[i][j] = table[i-1][j];
                    use = 0;
                }else{
                    if(!(use)){
                        table[i][j] = table[i][j - date[i][1]] + date[i][0];
                        use = 1;
                    }else{
                        table[i][j] = table[i][j - date[i][1]];
                    }
                }
                 */
            }
            printf("%d",table[i][j]);
        }
        printf("\n");
        if(max < table[i][W])
            max = table[i][W];
    }
    
    printf("%d\n",max);
    return 0;
}