import java.util.*;
import java.io.*;

class RucsacBkt
{
    int n, lungimeSol, volum[], cost[], solutieVolum[], solutieCost[], volumTotal, solOptimaV[], solOptimaC[];
    double profitBest = 0;

    public RucsacBkt(String numeFisier)
    {
        BufferedReader b;
        boolean linia1 = false, linia2 = false;
        int i = 0;
        String linie;

        try
        {
            b = new BufferedReader(new FileReader(numeFisier));

            while( ( linie = b.readLine() ) != null)
            {
                StringTokenizer st = new StringTokenizer(linie, " \t\n\r");

                if(!linia1)
                {
                    n = Integer.parseInt(st.nextToken());
                    volum = new int[n];
                    cost = new int[n];
                    solutieVolum = new int[n];
                    solutieCost = new int[n];
                    solOptimaV = new int[n];
                    solOptimaC = new int[n];

                    linia1 = true;
                    continue;
                }

                if(!linia2)
                {
                   volumTotal = Integer.parseInt(st.nextToken());

                   linia2 = true;
                   continue;
                }

                while(st.hasMoreTokens())
                {
                    volum[i++] = Integer.parseInt(st.nextToken());
                    cost[i-1] = Integer.parseInt(st.nextToken());
            	}
            }
        }catch(FileNotFoundException e)
            {
                System.out.println("Eroare la deschiderea fisierului " + numeFisier + ".");
            }
         catch(IOException f)
            {
                System.out.println("Eroare de I/E.");
            }
    }

    int volumCurent(int k)
    {
        int v = 0;
        for(int i = 0; i < k; i++)
                v += solutieVolum[i];
        return v;
    }

    double profitCurent(int k)
    {
		double p = 0;
		for(int i = 1; i < k; i++)
                p += (double)solutieCost[i]/(double)solutieVolum[i];
        return p;
	}

    boolean valid(int k, int volum)
    {
         for(int i = 0; i < k; i++)
            if(solutieVolum[i] == volum)
               return false;

        if((volumCurent(k) + volum) > volumTotal)
            return false;
        return true;
    }

    void bkt(int k)
    {
        int i;

        if(k >= n - 1)
        {
            if(profitCurent(k) > profitBest)
            {
               profitBest = profitCurent(k);
               lungimeSol = k;
               for(int j = 1; j <= k; j++)
               {
                  solOptimaV[j] = solutieVolum[j];
                  solOptimaC[j] = solutieCost[j];
               }
            }
        }
        for(i = 0; i < n; i++)
            if(valid(k, volum[i]))
            {
               solutieVolum[k] = volum[i];
               solutieCost[k] = cost[i];
               bkt(k+1);
            }
    }

    void afisareSolutie()
    {
        System.out.println("Volumul total = " + volumTotal);
		  System.out.println("Solutia optima :");
		  for(int i = 1; i < lungimeSol; i++)
		    System.out.println("\tObiect de volum " + solOptimaV[i] + " si cost " + solOptimaC[i]);
    }

    public static void main(String []args)
    {
         RucsacBkt rucsac = new RucsacBkt("DateBkt.txt");
         rucsac.bkt(1);
         rucsac.afisareSolutie();
    }
}