4 5
1 2
2 4
3 4
4 5

8

import java.io.*;
import java.util.*;
public class Main {
    private static int n;
    private static int m;
    private static int[] v = new int[1010];
    private static int[] w = new int[1010];
    private static int[] f = new int[1010];
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] num = reader.readLine().split(" ");
        int n = Integer.parseInt(num[0]);
        int m = Integer.parseInt(num[1]);
        for (int i = 1; i <= n; i++) {
            String[] arr = reader.readLine().split(" ");
            v[i] = Integer.parseInt(arr[0]);
            w[i] = Integer.parseInt(arr[1]);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= v[i]; j--) {
                f[j] = Math.max(f[j],f[j - v[i]] + w[i]);
            }
        }
        writer.write(f[m] + "\n");
        writer.flush();
        writer.close();
        reader.close();
    }
}