Description

Given $n$ products, each product has a price $w_i$ and a deadline $d_i$, where $d_i$ means that product $i$ must be purchased before minute $d_i$. Each purchase of one product takes $1$ minute to place the order, and the purchase is considered successful only after the order is placed.

Now you may choose some of these $n$ products (including choosing $0$ products) to buy (each product can be bought at most once), which is considered a purchasing plan.

When the number of products in one plan is greater than that in another plan, the former plan is defined to be better. When two plans have the same number of products and the former has a lower total price, the former plan is defined to be better. Among all purchasing plans that satisfy the requirements, find the number of products and the total price for the $1 \sim k$ best plans.

Input Format

The first line contains two positive integers $n, k$. The testdata guarantees that $k$ is not greater than the total number of valid plans.

The next $n$ lines each contain two positive integers $w_i, d_i$.

Output Format

Output $k$ lines. The $i$-th line should contain the number of products and the total price of the $i$-th best plan.

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

Hint

[Explanation for Sample 2]

The top $k$ best plans are $\{1,3,4\}$, $\{2,3,4\}$, and $\{1,3\}$ (using product indices to represent the products).

[Constraints and Notes]

This problem uses bundled subtasks.

• 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): No special restrictions.

For $100\%$ of the testdata, $1 \le n, k \le 2000$, $1 \le w_i \le 10^9$, $1 \le d_i \le n$.

[Hints and Notes]

In the official data, each subtask has $13$ test points, and the total time limit is as high as $6.5$ minutes. To reduce the burden on the judging servers, only the first two test points of each subtask are used for judging here.

This problem is translated from COCI 2021-2022 CONTEST #3 Task 3 Akcija.

The score of this problem follows the original COCI settings, with a full score of $110$.

Translated by ChatGPT 5