// [modified](from: https://www.geeksforgeeks.org/knapsack-problem/)

// A Dynamic Programming based solution for 0-1 Knapsack problem
#include<stdio.h>

// Max number of items
#define MAX_N 100

// Max weight
#define MAX_W 10000

// DP Table
int K[MAX_N][MAX_W];

// Weights
int wt[MAX_N];

// Values
int val[MAX_N];

// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }
 
// Returns the maximum value that can be put in a knapsack of capacity W
int knapsack(int W, int n) {
   int i, w;
 
   // Build table K[][] in bottom up manner
   for (i = 0; i <= n; i++) {
       for (w = 0; w <= W; w++) {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (wt[i-1] <= w)
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }

   return K[n][W];
}

int main() {
    int i;
    int n;
    int w;
    scanf("%d %d", &n, &w);
    for (i = 0; i < n ;i++){
        scanf("%d %d", (val+i), (wt+i));
    }
    int max_value = knapsack(w, n);
    printf("%d\n", max_value);
    return 0;
}
 
