Fraction Knapsack

include

include

include

include

include

using namespace std;

bool com (const vector& a,const vector& b) { return a[2]>b[2]; } int main() { int n =0; cin>>n;

vector<vector<double>> a(n, vector<double> (4));
int sol[n]={0};
    double profit=0,w;

 /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
for(int i=0;i<n;i++)
{
    cin>>a[i][0];
    cin>>a[i][1];
    a[i][2]= a[i][0]/a[i][1];
    a[i][3]=i;
}

cin>>w;

sort(a.begin(),a.end(),com);

int  i=0;
double max=0;
     for(i=0;i<n;i++)
   {

    if(w>=max+a[i][1])
      {

        max+=a[i][1];
        sol[(int)a[i][3]]++;
        profit+=a[i][0];
      }
         else
         {
             break;
         }
   }
  if(w>max)
  {
       sol[(int)a[i][3]]++;
       profit+=(w-max)*a[i][2];
  }

cout<<(int)profit<<endl;
for(int i=0;i<n;i++)
{
     cout<<sol[i]<<" ";
}



return 0;

}