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