Cod sursa(job #904169)
#include <fstream>
#include <algorithm>
using namespace std;
#define F stdin
const int Buffer=1<<18;
char Buff[Buffer]; int Next=0;
int get_int()
{
int Nbr=0;
while( Buff[Next]<'0' || '9'<Buff[Next] )
if ( ++Next >= Buffer ) fread(Buff,Buffer,1,F), Next=0;
while ( '0'<=Buff[Next] && Buff[Next]<='9' )
{
Nbr=Nbr*10+Buff[Next]-'0';
if ( ++Next >= Buffer ) fread(Buff,Buffer,1,F), Next=0;
}
return Nbr;
}
#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];
inline int cmp(int x, int y)
{ return b[x] < b[y]; }
int main()
{
freopen("peste.in", "r", stdin);
freopen("peste.out", "w", stdout);
n=get_int();
k=get_int();
m=get_int();
int i, j, x;
for (i=1; i<=n; i++)
{
a[i]=get_int();
b[i]=get_int();
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;
}