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

#include <fstream>
#include <vector>
#include <algorithm>

//#include <iostream>

using namespace std;

class Object{
  float g, v;
  short idx;
public: 
  //Object(){};
  //Object(Object ob){};
  //~Object(){std::cout<<"!!!!!\n";};
  static short cont;
  inline float getG(){ return g;}
  bool operator<(Object&);
  friend istream& operator>>(istream&, Object*);
  friend ostream& operator<<(ostream&, Object);

  friend bool smaller(Object* o1, Object* o2);
};

short Object::cont = 0;

inline bool Object::operator<(Object& other){
  return v/g < other.v/other.g;
}

bool smaller(Object* o1, Object* o2){
  return o1->v/o1->g < o2->v/o2->g;
}

istream& operator>>(istream& is, Object* ob){
  is >> ob->g >> ob->v;
  ob->idx = ++Object::cont;
  return is;
}

ostream& operator<<(ostream& os, Object ob){
  os << "Object " << ob.idx << ": ";
  os << ob.g << " " << ob.v;
  return os;
}

void readData(vector<Object*>& v, float& M){
  ifstream in("objects.in");
  Object* ob;
  v.clear();
  if(in && !in.eof()) in>>M;
  while(in && !in.eof() && in>>ob){
    v.push_back(ob);
  }
}

void processAndWrite(vector<Object*>& v, float& M){
  std::ofstream out("rucksack.out");
  sort(v.begin(), v.end(), smaller);
  size_t i=v.size()-1;
  while(i>=0 && M>0){
    if(M>=v[i]->getG()){
      M -= v[i]->getG();
      --i;
     } else{
        M = -M;
    }
  }
  for(size_t j=v.size()-1; j>i; --j){
    out << *v[j] << " - vollstaendig" << std::endl;
  }
  if(i>=0 && M<0){
    out << *v[i] << " - " << -M << " kg";
  }
}

int main(){
  vector<Object*> v;
  float M;
  readData(v, M); 
  processAndWrite(v, M);
  return 0;
}