题目描述

给定 $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$ 优方案的商品数量和总价格。

3 1
1 1
1 1
1 3

2 2

4 3
1 1
10 1
2 3
10 3

3 13
3 22
2 3

2 4
1 1
2 2

2 3
1 1
1 2
0 0

提示

【样例 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 CONTEST #3 Task 3 Akcija。

本题分值按 COCI 原题设置，满分 $110$。