package ccs.leetcode;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

class Solution {
  public static void main(String[] args) throws IOException {
    try (Scanner in = new Scanner(new BufferedReader(new FileReader("rucsac.in")));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("rucsac.out"))); ) {
      int n = in.nextInt();
      int g = in.nextInt();

      int[] w = new int[n];
      int[] p = new int[n];
      for (int i = 0; i < n; ++i) {
        w[i] = in.nextInt();
        p[i] = in.nextInt();
      }

      int[] dp = new int[g + 1];
      for (int i = 0; i < n; ++i) {
        for (int j = g; j >= w[i]; --j) {
          dp[j] = Math.max(dp[j], dp[j - w[i]] + p[i]);
        }
      }

      int result = Arrays.stream(dp).max().orElse(0);
      out.println(result);
    }
  }
}