P8029 [COCI 2021/2022 #3] Akcija

给定 $n$ 个商品，每个商品有一个价格 $w_i$ 和一个截止期 $d_i$，其中 $d_i$ 表示第 $i$ 个商品必须在第 $d_i$ 分钟之前完成购买。每次购买一个商品均需花费 $1$ 分钟进行下单，在下单之后才视为购买成功。 现可从这 $n$ 个商品中选择若干个（包括 $0$ 个）进行购买（每个商品最多购买一次），视为一种购买方案。 当一种购买方案内的商品数量大于另一种方案时，规定前者更优；当一种购买方案的商品数量与另一种相同且前者的总价格更低时，规定前者更优。求所有符合题意的购买方案中，第 $1 \sim k$ 优的方案的商品数量和总价格各是多少。

第一行，两个正整数 $n,k$。数据保证 $k$ 不大于符合题意的方案总数。 接下来的 $n$ 行，每行两个正整数 $w_i,d_i$。

输出共 $k$ 行，其中第 $i$ 行为第 $i$ 优方案的商品数量和总价格。

**【样例 2 解释】** 前 $k$ 优的方案为 $\{1,3,4\}$、$\{2,3,4\}$ 和 $\{1,3\}$（用商品编号代替对应商品）。 **【数据规模与约定】** **本题采用子任务捆绑测试。** - Subtask 1（10 pts）：$k=1$，$w_1=\cdots=w_n$。 - Subtask 2（20 pts）：$k=1$。 - Subtask 3（20 pts）：$k=2$。 - Subtask 4（10 pts）：$1 \le n \le 20$。 - Subtask 5（30 pts）：$1 \le n,k \le 100$。 - Subtask 6（20 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le n,k \le 2000$，$1 \le w_i \le 10^9$，$1 \le d_i \le n$。 **【提示与说明】** 官方数据每个子任务有 $13$ 个测试点，所需总时限高达 $6.5$ 分钟。为了减少评测机负担，这里每个子任务只选取前两个测试点进行评测。 **题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _Task 3 Akcija_。** **本题分值按 COCI 原题设置，满分 $110$。**