Knapsack

#include <iostream>
using namespace std;
#define siz 100

int n,c[siz],v[siz],used[siz],W;

void Knapsack()
{
    int cw,i,mx;
 double tv;

 for (i=0;i<n;i++) used[i]=0;

 cw=W;
 while (cw>0)
 {
  mx=-1;
        for (i=0;i<n;i++)
        if ((used[i]==0)&&((mx == -1)||((double)v[i]/c[i] > (double)v[mx]/c[mx]))) mx = i;

  used[mx]=1;
  cw-=c[mx];
  tv+=v[mx];
  if(cw<0)
  {
   tv-=v[mx];
   tv+=(1+(double)cw/c[mx])*v[mx];
  }
 }
 cout<<tv<<endl;
}

int main()
{
    cin>>W>>n;
    for(int i=0;i<n;i++) cin>>v[i]>>c[i];
    Knapsack();
    return 0;
}