Pagini recente » Cod sursa (job #2087497) | Cod sursa (job #74385) | Cod sursa (job #2372546) | Cod sursa (job #1343190) | Cod sursa (job #1450036)
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cctype>
#include <fstream>
#define timp first
#define plasa second
#define ll long long
using namespace std;
const int Nmax = 50010;
const int Bsize = (1 << 16);
int n , k , total , i , limita , j , p;
ll sum;
ll maxim[Nmax] , ans[Nmax];
pair < int , int > A[Nmax];
priority_queue < int , vector < int > , greater < int > > S;
/*char Buffer[Bsize];
void get_number(int &x)
{
x = 0;
while (!isdigit(Buffer[p]))
if (p < Bsize - 1)
++p;
else
{
fread(Buffer , 1 , Bsize , stdin);
p = 0;
}
while (isdigit(Buffer[p]))
{
x = x * 10 + Buffer[p] - '0';
if (p < Bsize - 1)
++p;
else
{
fread(Buffer , 1 , Bsize , stdin);
p = 0;
}
}
}
*/
int main()
{
/*freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
fread(Buffer , 1 , Bsize , stdin); p = 0;
get_number(n); get_number(k); get_number(total);
*/
ifstream fin("peste.in");
ofstream fout("peste.out");
fin >> n >> k >> total;
for (i = 1; i <= n; ++i)
{
//get_number(A[i].plasa); get_number(A[i].timp);
fin >> A[i].plasa >> A[i].timp;
limita = max(limita , A[i].timp);
}
sort(A + 1 , A + n + 1);
for (i = 1; i <= n; ++i)
{
S.push(A[i].plasa); sum += 1LL * A[i].plasa;
if (i > k)
sum -= S.top(),
S.pop();
maxim[A[i].timp] = 1LL * sum;
}
for (i = 1; i <= limita; ++i)
maxim[i] = max(maxim[i] , maxim[i-1]);
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]);
fout << ans[total];
return 0;
}