import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStream inputStream = new FileInputStream("rucsac.in");
		Scanner scanner = new Scanner(inputStream);

		OutputStream outputStream = new FileOutputStream("rucsac.out");
		PrintWriter writer = new PrintWriter(outputStream);

		int N = scanner.nextInt();
		int G = scanner.nextInt();
		List<Integer> weights = new ArrayList<>();
		List<Integer> profits = new ArrayList<>();

		weights.add(0);
		profits.add(0);

		for (int i = 1; i <= N; ++i) {
			weights.add(scanner.nextInt());
			profits.add(scanner.nextInt());
		}

		int S = 0;
		int Max[][] = new int[2][G + 1];

		for (int i = 1; i <= N; ++i) {
			int w = weights.get(i);
			int p = profits.get(i);
			int d = i % 2;
			Max[d][0] = 0;
			S = Math.min(S + w, G);

			for (int s = 1; s <= S; ++s) {

				// I take the object.
				if (s >= w && Max[d][s] < Max[1 - d][s - w] + p) {
					Max[d][s] = Max[1 - d][s - w] + p;
				}

				// I don't take the object.
				if (Max[d][s] < Max[1 - d][s]) {
					Max[d][s] = Max[1 - d][s];
				}
			}
		}

		writer.println(Max[N % 2][S]);
		writer.flush();

		inputStream.close();
		scanner.close();
		outputStream.close();
		writer.close();
	}
}