Pagini recente » Cod sursa (job #166346) | Cod sursa (job #785724) | Cod sursa (job #2628865) | Cod sursa (job #2109910) | Cod sursa (job #1675295)
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,k,t;
long long bst[50005],peste[1005],s;
pair<int,int>p[50005];
priority_queue<int>q;
int main(void)
{
int i,j,min1;
freopen("peste.in", "r", stdin);
freopen("peste.out", "w", stdout);
scanf("%d %d %d",&n,&k,&t);
for(i=1;i<=n;++i)
scanf("%d %d",&p[i].second,&p[i].first);
sort(p+1,p+n+1);
for(i=1;i<=n;++i)
{
if(q.size()<k)
{
s+=p[i].second;
q.push(-p[i].second);
}
else
{
min1=-q.top();
if(min1<p[i].second)
{
s=s-min1+p[i].second;
q.pop();
q.push(-p[i].second);
}
}
peste[p[i].first]=s;
}
for(i=1;i<=1000;++i)
if(!peste[i])
peste[i]=peste[i-1];
for(i=1;i<=t;++i)
for(j=1;j<=1000&&j<=i;++j)
bst[i]=max(bst[i],bst[i-j]+peste[j]);
printf("%lld\n",bst[t]);
return 0;
}