Pagini recente » Cod sursa (job #1118283) | Cod sursa (job #1863269) | Cod sursa (job #2793217) | Cod sursa (job #2559521) | Cod sursa (job #1958401)
#include <bits/stdc++.h>
#define maxN 1002
#define maxT 50002
#define ll long long
using namespace std;
FILE *fin = freopen("peste.in", "r", stdin);
FILE *fout = freopen("peste.out", "w", stdout);
/* ==================== */
int n, k, totalT;
/* ==================== */
struct Net
{
int f, t;
bool operator < (const Net &ot) const
{
if (t == ot.t)
return f < ot.f;
return t < ot.t;
}
} v[maxN];
priority_queue < int > q;
ll dp[maxT], best[maxT];
/* ==================== */
ll ans;
void compBest()
{
ll sum = 0;
for (int i = 1; i <= n; ++ i)
{
sum += 1LL * v[i].f;
q.push(-v[i].f);
if (i > k)
{
sum += q.top();
q.pop();
}
best[v[i].t] = max(best[v[i].t], sum);
}
for (int i = 1; i < maxT; ++ i)
best[i] = max(best[i], best[i - 1]);
}
int main()
{
scanf("%d %d %d", &n, &k, &totalT);
for (int i = 1; i <= n; ++ i)
scanf("%d %d", &v[i].f, &v[i].t);
sort(v + 1, v + n + 1);
compBest();
for (int i = 1; i <= totalT; ++ i)
{
dp[i] = max(dp[i], dp[i - 1]);
for (int j = 1; j <= i; ++ j)
dp[i] = max(dp[i], best[j] + dp[i - j]);
}
printf("%lld\n", dp[totalT]);
return 0;
}