Pagini recente » Cod sursa (job #205851) | Cod sursa (job #2415024) | Cod sursa (job #2128466) | Cod sursa (job #2473530) | Cod sursa (job #205638)
Cod sursa(job #205638)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxn 50010
#define maxt 1010
#define ll long long
int n, k, m, nr;
int a[maxn], b[maxn], p[maxn];
ll c[maxn];
int best[maxt], v[maxt];
int cmp(int x, int y)
{
return b[x] < b[y];
}
int main()
{
freopen("peste.in", "r", stdin);
freopen("peste.out", "w", stdout);
scanf("%d %d %d ", &n, &k, &m);
int i, j, x;
for (i=1; i<=n; i++)
{
scanf("%d %d ", &a[i], &b[i]);
p[i] = i;
}
sort(p+1, p+n+1, cmp);
j = x = 1;
for (i=1; i<maxt; i++)
{
best[i] = best[i-1];
for (; b[p[j]] == i; j++)
if (a[p[j]] >= x)
{
nr++;
best[i] += a[p[j]];
v[a[p[j]]]++;
}
for (; x<maxt && nr>k; )
if (v[x])
{
best[i] -= x;
v[x]--, nr--;
}
else x++;
}
for (i=0; i<=m; i++)
for (j=1; j<maxt && i+j<=m; j++) c[i+j] = max(c[i+j], c[i] + best[j]);
printf("%lld\n", c[m]);
return 0;
}