//
// 0-1 Knapsack and Dynamic Programming
//
import java.util.*;
import java.io.*;

public class KnapsackDP {
    private int[] v;          // value
    private int[] w;          // weight
    private boolean select[]; // is the item selected?
    private int n,cap;
    private boolean trace;
    private int[][] B;        // B[i][j] is the best value had from selecting amongst
                              // item[0] ... item[i]  with a knapsack capacity of j

    public KnapsackDP (String fname,boolean trace) throws IOException {
	Scanner sc  = new Scanner(new File(fname));
	n           = sc.nextInt();        // number of items
	cap         = sc.nextInt();        // capacity (sum of weights)
	v           = new int[n+1];        // value of an item, item[0] is a dummy, value 0
	w           = new int[n+1];        // weight of item, item[0] is a dummy, weight 0
	B           = new int[n+1][cap+1]; // for memoization
	select      = new boolean[n+1];    // is the item selected?
	this.trace  = trace;
	for (int i=1;i<=n;i++){
	    v[i] = sc.nextInt();
	    w[i] = sc.nextInt();
	}
	sc.close();
    }

    public String toString(){
	String s = "n: " + n + " cap: " + cap + "\n";
	for (int i=0;i<=n;i++) s = s + "("+ v[i] +","+ w[i] +") ";
	return s;
    }

    public void display(int item,int currentCap){
	System.out.println("n: "+ item +" cap: "+ currentCap);	
	for (int i=0;i<=n;i++) System.out.print("("+ v[i] +","+ w[i] +") "); System.out.println();
	System.out.print("      ");
	for (int j=0;j<10;j++)
	    System.out.print(" "+ j +" ");
	for (int j=10;j<=cap;j++)
	    System.out.print(j +" ");
	System.out.println();
	for (int i=0;i<=n;i++){
	    System.out.print("   "+ i +"  ");
	    for (int j=0;j<=cap;j++) 
		if (B[i][j] < 10) System.out.print(" "+ B[i][j] +" ");
		    else System.out.print(B[i][j] +" ");
	    System.out.println();
	}
	System.out.println();
    }

    public void solveDP(){
	for (int i=1;i<=n;i++)
	    for (int j=0;j<=cap;j++){
		if (w[i] <= j) // item i can be part of a solution
		    if (v[i] + B[i-1][j-w[i]] > B[i-1][j]) 
			B[i][j] = v[i] + B[i-1][j-w[i]];
		    else B[i][j] = B[i-1][j];
		else B[i][j] = B[i-1][j];
		if (trace) display(i,j);
	    }
    }

    private void getSolution(){
	int k = cap;
	for (int i=n;i>0;i--)
	    if (B[i][k] != B[i-1][k]){
		select[i] = true;
		k = k - w[i];
	    }
    }

    public void showSolution(){
	getSolution();
	int totV = 0;
	int totW = 0;
	for (int i=1;i<=n;i++) 
	    if (select[i]){
		totV = totV + v[i];
		totW = totW + w[i];
	    }
	System.out.println("totVal:"+ totV +"   totWgt:"+ totW);
	for (int i=1;i<=n;i++)
	    if (select[i]) System.out.print("("+ v[i] +","+ w[i] +") ");
	System.out.println();
	if (trace) display(n,cap);
    }

    public static void main(String[] args)  throws IOException {
	if (args.length == 0){
	    System.out.println("fname");
	    return;
	}
	String fname   = args[0];
	boolean trace  = args.length == 2;
	KnapsackDP kdp = new KnapsackDP(fname,trace);
	kdp.solveDP();
	kdp.showSolution();
    }
}