题目描述

译自 COCI 2021/2022 Contest #3 T3「Akcija」

有 $n$ 种只有一份的物品，每一种物品有两个属性 $w_i$ 和 $d_i$，表示其需要在第 $d_i$ 秒前购买，重量是 $w_i$，购买一份物品需要 $1$ 秒钟。

我们定义一种方案 $A$ 要比另一种方案 $B$ 优秀，当且仅当满足下面两项其中一项：

• $A$ 买得物品比 $B$ 买得物品多；
• $A$ 买得物品数量等于 $B$ 买得物品数量且 $A$ 买得物品总重量小于 $B$ 买得物品总重量。

试求出前 $k$ 优秀的不同方案，定义两种方案是相同的，当且仅当他们买下的物品子集相同。

输入格式

第一行为两个整数 $n,k$。

接下来 $n$ 行两个整数 $w_i,d_i$。

输出格式

输出 $k$ 行，每行两个整数 $x,y$，分别表示第 $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

数据范围与提示

对于全部数据，$1\le n,k\le 2000$，$1\le w_i\le 10^9$，$1\le d_i\le n$，保证一定存在至少 $k$ 种合法的方案。