import java.io.*;
import java.util.StringTokenizer;

public class Main {

  public static class MyScanner implements Closeable {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner(String file) throws FileNotFoundException {
      br = new BufferedReader(new InputStreamReader(new FileInputStream(file)), 1 << 16);
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine(){
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }

    @Override
    public void close() throws IOException {
      br.close();
    }
  }

  public static void main(String[] args) throws IOException {
    try(MyScanner scanner = new MyScanner("rucsac.in");
        PrintWriter pw = new PrintWriter(new FileOutputStream("rucsac.out"))) {
      int N = scanner.nextInt();
      int G = scanner.nextInt();

      int[] price = new int[N+1];
      int[] weight = new int[N+1];

      for (int i = 1; i <= N; i++) {
        weight[i] = scanner.nextInt();
        price[i] = scanner.nextInt();
      }

      //int[][] dp = new int[N+1][G+1];

      int[][] dp2 = new int[2][G+1];

      int[] current = dp2[0];
      int[] next = dp2[1];
      for (int i = 1; i <= N; i++) {
        for (int g = 0; g <= G; g++) {
          //dp[i][g] = dp[i-1][g];
          next[g] = current[g];

          if (g - weight[i] >= 0) {
            //dp[i][g] = Math.max(dp[i][g], dp[i-1][g - weight[i]] + price[i]);
            next[g] = Math.max(next[g], current[g - weight[i]] + price[i]);
          }
        }
        int[] temp = current;
        current = next;
        next = temp;
      }

      //pw.println(dp[N][G]);
      pw.println(current[G]);
    }

  }
}