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

class RucsacGreedy
{
    int n, volum[], cost[], volumTotal;
    double profit[];

    public RucsacGreedy(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];
                    profit = new double[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());
                    profit[i-1] = (double)cost[i-1]/(double)volum[i-1];
            	}
            }
        }catch(FileNotFoundException e)
            {
                System.out.println("Eroare la deschiderea fisierului " + numeFisier + ".");
            }
         catch(IOException f)
            {
                System.out.println("Eroare de I/E.");
            }
    }

    void sortare()
    {
        boolean sortat;
        int i, temp1, temp2;
        double tempProfit;

        do
        {
             sortat = true;
             for(i = 0; i < n - 1; i++)
                if(profit[i] < profit[i+1])
                {
                    tempProfit = profit[i];
                    temp1 = volum[i];
                    temp2 = cost[i];

                    profit[i] = profit[i+1];
                    volum[i] = volum[i+1];
                    cost[i] = cost[i+1];

                    profit[i+1] = tempProfit;
                    volum[i+1] = temp1;
                    cost[i+1] = temp2;

                    sortat = false;
                }
        }while(!sortat);
    }

    void greedy()
    {
        System.out.println("Volumul total = " + volumTotal);
		  System.out.println("Solutia optima :");

    		for(int i = 0; i < n; i++)
  	   	{
		      if(volum[i] <= volumTotal)
            {
				     System.out.println("\tObiect de volum " + volum[i] + " si cost " + cost[i]);
				     volumTotal -= volum[i];
            }
  		   }
    }

    public static void main(String []args)
    {
         RucsacGreedy fb = new RucsacGreedy("DateGreedy.txt");
         fb.sortare();
         fb.greedy();
    }
}