圣诞节是赠送礼物的时刻。Malnar 先生需要一些礼物点子。尽管他正在深思，电视节目却吸引了他的注意：“特别优惠！这款神奇的产品仅售 $w$ 库纳。立即拨打电话，因为此优惠仅在接下来的 $d$ 分钟内有效。但这还不是全部……”

共有 $n$ 种不同的产品在售，其中第 $i$ 种产品的价格为 $w_i$，且可以在第 $d_i$ 分钟（含）之前订购。拨打电话下单需要一分钟。如果存在一种拨打电话的顺序，能够订购这些产品并满足上述截止日期，则称该产品子集为“可获得的”。每种产品最多只能订购一次。

Malnar 先生打算以尽可能低的价格购买尽可能多的产品，但他还不确定应该购买哪些产品。他通过以下方式比较两个可获得的子集：更好的可获得子集是产品数量更多的那个；如果数量相等，则是总价格（所选产品价格之和）更小的那个。

Malnar 先生将按照上述方式对可获得的子集进行排名，并考虑前 $k$ 个最好的子集。请编写一个程序，确定这 $k$ 个最好的可获得子集的大小和总价格。

输入格式

第一行包含正整数 $n$ 和 $k$，分别表示不同产品的数量和需要考虑的可获得子集的数量。$k$ 小于或等于可获得子集的总数。

接下来的 $n$ 行，每行包含两个正整数 $w_i$ ($1 \le w_i \le 10^9$) 和 $d_i$ ($1 \le d_i \le n$)，分别表示第 $i$ 种产品的价格和该优惠有效的最后期限（分钟）。

输出格式

在第 $i$ 行输出第 $i$ 个最好的可获得子集的大小和总价格。

子任务

在每个子任务中，均满足 $1 \le n, k \le 2000$。

样例

输入 1

3 1
1 1
1 1
1 3

输出 1

2 2

输入 2

4 3
1 1
10 1
2 3
10 3

输出 2

3 13
3 22
2 3

说明 2

产品 1 和产品 2 不能同时出现在一个可获得的子集中，因此三个最好的可获得子集是 $\{1, 3, 4\}$，$\{2, 3, 4\}$ 和 $\{1, 3\}$。

输入 3

2 4
1 1
2 2

输出 3

2 3
1 1
1 2
0 0