import java.io.*;


public class Main{
    public static void main(String[] args) {
        try {
            BufferedReader br=new BufferedReader(new FileReader("rucsac.in"));
            String[] firstLine=br.readLine().split("");
            int N=Integer.parseInt(firstLine[0]);
            int G=Integer.parseInt(firstLine[1]);
            int[] weights=new int[N];
            int[] values=new int[N];
            
            for(int i=0;i<N;i++){
                String[] line=br.readLine().split(" ");
                weights[i]=Integer.parseInt(line[0]);
                values[i]=Integer.parseInt(line[1]);
            }
            br.close();
            int result=knapsack(N,G,weights,values);
            BufferedWriter bw=new BufferedWriter(new FileWriter("rucsac.out"));
            bw.write(String.valueOf(result));
            bw.close();
        } catch (Exception e) {
            System.err.println("Eroare la citirea sau scrierea fisierelor: "+ e.getMessage());
        }
    }

    public static int knapsack(int N, int G, int[] weights, int[] values){
        int[][] dp=new int[N+1][G+1];
        for(int i=1;i<=N;i++){
            for(int w=0;w<=G;w++){
                if(weights[i-1]<=w){
                    dp[i][w]=Math.max(dp[i-1][w],dp[i-1][w-weights[i-1]]+values[i-1]);
                }else{
                    dp[i][w]=dp[i-1][w];
                }
            }
        }

        return dp[N][G];
    }
}