import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int weight = scan.nextInt();
int[] w = new int[n + 1];
int[] v = new int[n + 1];
for (int i = 1; i <= n; i) {
w[i] = scan.nextInt();
v[i] = scan.nextInt();
}
int[][] dp = new int[n + 1][weight + 1];
for (int i = 1; i <= n; i) {
for (int j = 1; j <= weight; j++) {
if (j < w[i]) {
dp[i][j] = dp[i - 1][j];
}
if (j >= w[i]) {
dp[i][j] = Math.max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);
}
}
}
System.out.println(dp[n][weight]);
}
}