import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;


public class Rucsac {
	int n,G;
	int g[];
	int c[];
	int m[][];
	Rucsac(){
		Scanner sc;
		try {
			sc = new Scanner(new File("Rucsac.in"));
			n = sc.nextInt();
			G = sc.nextInt();
			
			g = new int[n+1];
			c = new int[n+1];
			m = new int[n+1][G+1];
			m[0] = new int[G+1];
			
			for(int i = 1; i <= n; i++){
				g[i] = sc.nextInt();
				c[i] = sc.nextInt();
				m[i] = new int[G+1];
			}
			//for(int i = 1; i <= n; i++){
				
		//	}
		} catch (FileNotFoundException e) {
			n = 0;
			e.printStackTrace();
		}
			
	}
	
	public int findMax(){
		m[n] =  m[n-1];
		for(int i = 1; i<=n; i++)
			for(int gr = 0;gr<=G;gr++)
			if (gr-g[i] >=0){
				m[i][gr] = Math.max(m[i-1][gr], c[i] + m[i-1][gr-g[i]]); 	
			}
			else
				m[i][gr] = m[i-1][gr];
		System.out.print(m[n][G]);
		return m[n][G];
	}
	
	
	void print(int i, int gr){
		if (i==0)
			return;
		if (gr-g[i] >=0){
			if (m[i][gr] == m[i-1][gr])
				print(i-1,gr);
			else{
				print(i-1,gr-g[i]);
				System.out.println(i);
			}
		}
		else
			print(i-1,gr);
	}
	
	public void printSol(){
		System.out.println("S-au ales obiectele: ");
		print(n,G);
	};
	
	
	public static void main(String args[]){
		Rucsac tr = new Rucsac();
		tr.findMax();
		tr.printSol();
	}
}