package knapsack;

import java.io.File ;
import java.io.FileNotFoundException ;
import java.io.PrintWriter ;
import java.io.UnsupportedEncodingException ;
import java.util.Scanner ;

public class Knapsack {
	
	public static int max ( int a , int b ){
		if ( a > b )
			return a ;
		return b ;
	}
	
	public static void print_vect ( int[] a ){
		for ( int i = 0 ; i < a.length ; i++ )
			System.out.print(a[i] + " ") ;
		
		System.out.println() ;
	}

	public static void main ( String[] args ) throws FileNotFoundException, UnsupportedEncodingException {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(new File("rucsac.in"));
		
		int N = scanner.nextInt();
		int G = scanner.nextInt();
		
		int[] prev_line = new int[G+1] ;
		
		int[] actu_line = new int[G+1] ;
		
		int cw , cp ; // current weight and profit 
		
		for (int j = 0 ; j < N ; j ++ ){
			cw = scanner.nextInt();
			cp = scanner.nextInt();
			
			
			for ( int i = cw ; i <= G ; i ++ ){
				actu_line[i] = max ( cp + prev_line[i-cw] , prev_line[i]);
				
			}
			
			for ( int i = cw ; i <=G ; i++)
				prev_line[i] = actu_line[i] ;
		
		}
		scanner.close();
		
		PrintWriter writer = new PrintWriter("rucsac.out", "UTF-8");
		writer.print(actu_line[G]) ;
		writer.close();
	}

}