Pagini recente » Cod sursa (job #932645) | Cod sursa (job #739435) | Cod sursa (job #1748462) | Cod sursa (job #1272638) | Cod sursa (job #2645731)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("rucsac.in");
ofstream cout ("rucsac.out");
struct Object{
int ci;
int gi;
int di;
} v[5005];
bool cmp(Object a,Object b)
{
return a.di>b.di;
}
int n;
int Gmax;
int ww = 0;
int main()
{
cin>>n>>Gmax;
for(int i=1;i<=n;i++)
cin>>v[i].gi>>v[i].ci;
for(int i=1;i<=n;i++)
v[i].di = v[i].ci / v[i].gi;
sort(v+1,v+n+1,cmp);
for(int i=1;i<=n;i++)
{
if(Gmax - v[i].gi >= 0)
{
ww = ww + v[i].ci;
}
else if(Gmax > 0)
{
ww = ww + Gmax * v[i].ci / v[i].gi;
}
Gmax = Gmax - v[i].gi;
}
cout<<ww;
return 0;
}