use std::fs::File;
use std::io::{*};
use std::cmp::{max};

fn main() {
    let mut input = BufReader::new(File::open("rucsac.in").unwrap());
    let mut output = BufWriter::new(File::create("rucsac.out").unwrap());

    let mut line = String::new();
    input.read_line(&mut line).unwrap();
    let inputs : Vec<usize> = line.split(" ").map(|x| x.trim().parse().unwrap()).collect();

    let n : usize = inputs[0];
    let g : usize = inputs[1];

    let mut current_dp : Vec<usize> = vec![0; g + 1]; 
    for _i in 0..n {
        let mut line = String::new();
        input.read_line(&mut line).unwrap();
        let inputs : Vec<usize> = line.split(" ").map(|x| x.trim().parse().unwrap()).collect();

        let w : usize = inputs[0];
        let p : usize = inputs[1];

        let mut following_dp : Vec<usize> = vec![0; g + 1];

        for j in 0..g + 1 {
            following_dp[j] = current_dp[j];

            if j >= w {
                following_dp[j] = max(following_dp[j], current_dp[j - w] + p);
            }
        }

        current_dp = following_dp;
    }

    writeln!(output, "{}", current_dp[g]).unwrap();
}