Pagini recente » Cod sursa (job #1196254) | Cod sursa (job #1359055) | Cod sursa (job #75316) | Cod sursa (job #1803736) | Cod sursa (job #1450017)
#include <cstdio>
#include <algorithm>
#include <set>
#define timp first
#define plasa second
#define ll long long
using namespace std;
const int Nmax = 50010;
int n , k , total , i , limita , j;
ll sum;
ll maxim[Nmax] , ans[Nmax];
pair < int , int > A[Nmax];
multiset < int > S;
int main()
{
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf("%d %d %d", &n, &k, &total);
for (i = 1; i <= n; ++i)
{
scanf("%d %d", &A[i].plasa, &A[i].timp);
limita = max(limita , A[i].timp);
}
sort(A + 1 , A + n + 1);
for (j = 1, i = 1; i <= limita; ++i)
{
for ( ; j <= n && A[j].timp <= i; ++j)
S.insert(A[j].plasa),
sum += 1LL * A[j].plasa;
for ( ; S.size() > k; sum -= *S.begin(), S.erase(S.begin()));
maxim[i] = 1LL * sum;
}
for (i = 1; i <= total; ++i)
for (j = 1; j <= min(i , limita); ++j)
ans[i] = max(ans[i] , ans[i-j] + maxim[j]);
printf("%lld\n", ans[total]);
return 0;
}