/************************************************
Algorithmen und Problemloesungen mit C++,
http://www.algorithmen-und-problemloesungen.de
Copyright @2007 by Doina Logofatu
************************************************/

#include <queue>
#include <fstream>

class Object{
  float g, v;
  short idx;
public:   
  Object(float greutate, float valoare,short index=0)
    :g(greutate),v(valoare),idx(index){	
      }	
  inline float getG()const { return g;}
  inline float getV()const { return v;}
  inline short getIdx()const { return idx;}
  inline bool operator<(const Object& other) const {
    return v/g < other.v/other.g;
  }  
};


class ObjectLessComparator{	// functor for operator<
public:	
  inline bool operator()(const Object* pLeft, const Object* pRight) const
    {return (*pLeft)<(*pRight);}
};

typedef std::priority_queue<Object*,std::vector<Object*>, ObjectLessComparator> ObjectsPriorityQueue;


std::ostream& operator<<(std::ostream& os, const Object &rObj){
  os << "Object " << rObj.getIdx()<< ": ";
  os << rObj.getG() << " " << rObj.getV();
  return os;
}

void readData(ObjectsPriorityQueue &v, float& M){
  std::ifstream in("objects.in");
  float g,val;
  short idx=0;
  if(!in.eof()) in>>M;
  while(!in.eof() && (in>>g) && (in >> val) ){	  		
    v.push(new Object(g,val,++idx));
  }
}

void processAndWrite(ObjectsPriorityQueue &v, float M){
  std::ofstream out("rucksack.out");
  while(!v.empty()) {
    Object *pObj = v.top();	  
    if(M>0) {
      float g = pObj->getG();
      out << (*pObj);
      M -= g;
      if(M>=0){          
        out << " - vollstaendig" << std::endl;	  
      } 
      else{        
        out << " - " << M+g<< std::endl;
      }
    }
   v.pop();
   delete pObj;
 }
}

int main(){
  ObjectsPriorityQueue v;
  float M;
  readData(v, M);
  processAndWrite(v, M);
  return 0;
}