You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小青鱼，一位没有经验的商人，最近开了一家名叫“皇后有机珠宝”（QOJ）的店。这家珠宝店共有 $n$ 枚宝石，其中第 $i$ 枚售价为 $w_i$ 元，美丽度为 $v_i$。进入商店之前，您准备了 $W$ 元用来买下美丽度总和尽量高的宝石。

有趣的是，小青鱼的店今天正在促销。任何顾客都可以任选 $k$ 枚宝石并免费获得它们。有了这样的机会，您很想知道，如果您使用最佳策略，用 $W$ 元到底能获得美丽度总和多高的宝石。

请注意，每枚宝石独此一份，您不能多次获取同一枚宝石。另外，您无需花完所有的钱。

输入格式

每个测试文件仅有一组测试数据。

第一行输入三个整数 $n$，$W$ 和 $k$（$1 \leq n \leq 5 \times 10^3$，$1 \leq W \leq 10^4$，$0 \leq k \leq n$），表示商店中宝石的总数，您拥有的金钱数以及您可以免费获得的宝石数量。

对于接下来 $n$ 行，第 $i$ 行输入两个整数 $w_i$ 和 $v_i$（$1 \leq w_i \leq W$，$1 \leq v_i \leq 10^9$），表示第 $i$ 枚宝石的售价和美丽度。

输出格式

输出一行一个整数表示答案。

4 10 1
9 10
10 1
3 5
5 20

35

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

129

提示

对于第一组样例数据，小青鱼的商店有 $4$ 枚宝石，您可以免费获得其中 $1$ 枚。一种最优策略是免费获取第一枚宝石，并购买第三和第四枚宝石。

$$\begin{array}{ | c | c | c | c | } \hline \bf{宝石} & \bf{售价 w_i} & \bf{美丽度 v_i} & \bf{操作} \\ \hline 1 & 9 & 10 & 免费获取 \\ \hline 2 & 10 & 1 & / \\ \hline 3 & 3 & 5 & 购买 \\ \hline 4 & 5 & 20 & 购买 \\ \hline \end{array}$$

所以答案是 $10 + 5 + 20 = 35$。