Knapsack（ The 2023 ICPC Asia Nanjing Regional Contest (The 2nd Universal Cup. Stage 11: Nanjing) ）

Little Cyan Fish, an inexperienced businessman, recently launched a store named Queen’s Organic Jewelry. This jewelry store houses $n$ gemstones, where the $i$-th gemstone is priced at $w_i$ dollar and has a beauty of $v_i$. Prior to visiting the store, you have $W$ dollars in hand, which you plan to use to purchase gemstones of the greatest possible total beauty.

Interestingly, Little Cyan Fish’s store is running a promotion today. Any visitor to the store can select any $k$ gemstones and take them home absolutely free of charge! With this opportunity at hand, you’re keen to know the maximum total beauty of gemstones you could obtain with your $W$ dollars, assuming you adopt the optimal strategy.

Please bear in mind that the store stocks only one unit of each gemstone, so you cannot obtain the same gemstone more than once. Also note that you don’t have to spend all the money.

Input

There is only one test case in each test file.

The first line of the input contains three integers $n$, $W$ and $k$ ($1\le n\le 5\times 10^3$, $1\le W\le 10^4$, $0\le k\le n$), indicating the total number of gemstones in the store, the amount of money you have and the number of gemstones you can take for free.

For the following $n$ lines, the $i$-th line contains two integers $w_i$ and $v_i$ ($1\le w_i\le W$, $1\le v_i\le 10^9$), indicating the price and the beauty of the $i$-th gemstone.

Output

Output one line containing one integer indicating the answer.

Examples

Input

4 10 1
9 10
10 1
3 5
5 20

Output

35

Input

5 13 2
5 16
5 28
7 44
8 15
8 41

Output

129

题目大意

Little Cyan Fish开了一家名为“Queen’s Organic Jewelry”的珠宝店。店里有$n$颗宝石，每颗宝石有一个价格 $w_i$ 和美度 $v_i$。你手上有$W$元钱，打算用这$W$元购买尽可能高总美度的宝石。店里还在做促销活动，你可以免费选择$k$颗宝石带回家，免费的宝石不需要花费钱。

你需要计算在有限的$W$元钱下，结合免费选择的$k$颗宝石，你能获得的最大总美度。

解题思路

1. 0/1背包问题：这个问题本质上是一个背包问题。你可以将每个宝石看作一个物品，物品的重量就是价格$w_i$，物品的价值就是美度$v_i$。我们要解决的就是在有$W$元预算的情况下，选择一定数量的宝石，使得其总美度最大。

2. 免费宝石选择：这里的难点在于可以选择$k$颗免费宝石。免费的宝石并不需要花费金钱，因此这部分宝石不受预算限制，但是它们也有一个美度限制。因此，我们需要处理两部分：

   • 购买宝石：这部分宝石需要受到预算限制，属于经典的0/1背包问题。
   • 免费宝石：从剩余的宝石中选出$k$个美度最高的宝石来获得。

3. 策略设计：

   • 首先，将所有宝石按价格$w_i$从小到大排序。
   • 使用动态规划（0/1背包）来处理购买宝石的部分。通过动态规划，记录在不同预算下能达到的最大美度。
   • 然后，对于剩下的宝石，使用一个优先队列（堆）来维护$k$个最大美度的宝石，并计算出这部分宝石的最大美度和。

4. 具体步骤：

   • 先进行背包动态规划，计算在不同预算下能获得的最大美度。
   • 然后，从排序后的宝石列表中选择$k$个美度最高的宝石，逐步计算当选择了不同数量的免费宝石时，总美度的最大值。
   • 最终得到的最大美度就是在给定预算和免费宝石选择下的最优解。

代码分析

#include <map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define int long long
#define Max(a, b) (((a) > (b)) ? (a) : (b))
#define Min(a, b) (((a) < (b)) ? (a) : (b))
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

const int inf = 1e9 + 7;
const int N = 2e5 + 10;

struct Node
{
    int w;
    int v;
} node[N];

int dp[N]; // 动态规划数组
int ans[N]; // 存储从后向前计算的最多可获得的美度

bool cmp(Node x, Node y)
{
    return x.w < y.w; // 按照宝石的价格升序排序
}

void solved()
{
    int n, w, k;
    cin >> n >> w >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> node[i].w >> node[i].v; // 输入每个宝石的价格和美度
    }
    sort(node + 1, node + 1 + n, cmp); // 按价格排序

    ans[n + 1] = 0;
    priority_queue<int> q; // 优先队列，用于维护免费宝石的最大美度
    int sum = 0;
    for (int i = n; i >= 1; i--)
    {
        if (q.size() < k)
        {
            q.push(-node[i].v); // 将美度最大的宝石放入队列
            sum += node[i].v;
        }
        else
        {
            if (!q.empty() && -q.top() < node[i].v) // 如果队列满了，替换美度最小的宝石
            {
                sum += node[i].v;
                sum += q.top();
                q.pop();
                q.push(-node[i].v);
            }
        }
        ans[i] = sum; // 记录当前从i到n的最大美度
    }

    int maxx = 0;
    for (int i = 0; i <= n; i++) // 从0到n枚举购买宝石的情况
    {
        for (int j = w; j >= node[i].w; j--) // 动态规划更新
        {
            dp[j] = max(dp[j], dp[j - node[i].w] + node[i].v);
        }
        maxx = max(maxx, dp[w] + ans[i + 1]); // 取最大值
    }

    cout << maxx << endl; // 输出最大美度
}

signed main()
{
    BoBoowen;
    int T = 1;
    while (T--)
    {
        solved(); // 解决问题
    }
    return 0;
}

详细分析

1. 结构体Node：用于存储每个宝石的价格和美度信息。

   struct Node
   {
       int w; // 价格
       int v; // 美度
   } node[N];
   

2. 动态规划数组 dp：用于记录在预算j下，可以获得的最大美度。

   int dp[N];
   

3. ans数组：记录从每个位置向后免费选择宝石的最大美度。

   int ans[N];
   

4. 排序：按价格对宝石进行升序排序。

   sort(node + 1, node + 1 + n, cmp);
   

5. 优先队列 q：用于维护当前可以选择的最多$k$个最大美度的免费宝石。

• 通过优先队列，确保每次选出美度最大的宝石，并替换掉美度较小的宝石。

6. 动态规划：通过状态转移方程来计算在不同预算下，能够购买的最大美度。

7. 最终答案：通过比较购买宝石和免费宝石的最大美度来得到最终答案。

时间复杂度

1. 排序：O(n log n)。
2. 动态规划：O(n * W)，其中$W$是背包的容量（最大预算）。
3. 优先队列：O(n log k)，每个宝石处理时可能进行一次堆操作。

因此，总的时间复杂度是O(n * W + n log n + n log k)，在最坏情况下，n = 5000，W = 10000，k = n时，整体时间复杂度是可以接受的。

总结

这道题综合了0/1背包和最大选择问题的思想。首先通过动态规划计算在给定预算下能获得的最大美度，然后利用优先队列来选择$k$个免费宝石，最后合并两者的最大美度，得出最终的最优解。