Pagini recente » Cod sursa (job #2977518) | Cod sursa (job #945777) | Cod sursa (job #631581) | Cod sursa (job #1671652) | Cod sursa (job #1412990)
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,timp,p[50002],t[50002],fol[1002],i,j,ram,tmax,pmax;
long long ans[50002],peste[50002];
int main()
{
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf("%d%d%d",&n,&k,&timp);
tmax=0;
pmax=0;
for(i=1;i<=n;i++)
{
scanf("%d%d",&p[i],&t[i]);
if(t[i]>tmax)
{
tmax=t[i];
}
if(p[i]>pmax)
{
pmax=p[i];
}
}
for(i=1;i<=tmax;i++)
{
memset(fol,0,sizeof(fol));
peste[i]=0LL;
for(j=1;j<=n;j++)
{
if(t[j]<=i)
{
fol[p[j]]++;
}
}
ram=k;
for(j=tmax;j>=1&&ram;j--)
{
if(fol[j])
{
if(fol[j]<=ram)
{
peste[i]+=1LL*j*fol[j];
ram-=fol[j];
}
else
{
peste[i]+=1LL*j*ram;
ram=0;
}
}
}
}
for(i=0;i<=timp;i++)
{
ans[i]=0;
for(k=1;k<=i;k++)
{
if(ans[i-k]+peste[k]>ans[i])
{
ans[i]=ans[i-k]+peste[k];
}
}
}
printf("%lld\n",ans[timp]);
}