import java.util.*; import java.io.*; public class Main { static Pizza[] pizzas; static int[][][] dp; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] first = br.readLine().split(" ", 2); int n = Integer.parseInt(first[0]); int k = Integer.parseInt(first[1]); pizzas = new Pizza[n]; for (int i = 0; i < n; i++) { String[] line = br.readLine().split(" ", 2); pizzas[i] = new Pizza(Integer.parseInt(line[0]), Integer.parseInt(line[1])); } Arrays.sort(pizzas); dp = new int[2][n][k + 1]; for (int[][] arr1 : dp) { for (int[] arr : arr1) { Arrays.fill(arr, -1); } } System.out.println(dfw(0, n - 1, k)); } static int dfw(int type, int idx, int cost) { if (cost < 0) { return Integer.MIN_VALUE; } if (idx < 0) { return 0; } if (dp[type][idx][cost] == -1) { if (type == 0) { dp[type][idx][cost] = Math.max(dfw(0, idx - 1, cost), dfw(1, idx - 1, cost - pizzas[idx].cost) + pizzas[idx].value); } else { dp[type][idx][cost] = Math.max(dfw(1, idx - 1, cost), dfw(0, idx - 1, cost) + pizzas[idx].value); } } return dp[type][idx][cost]; } static class Pizza implements Comparable { int cost; int value; public Pizza(int cost, int value) { this.cost = cost; this.value = value; } public int compareTo(Pizza another) { return cost - another.cost; } } }