题目描述
Problem Description
Given \( n \) items, each with a price \( w_i \) and a deadline \( d_i \), where \( d_i \) indicates that the \( i \)-th item must be purchased before the \( d_i \)-th minute. Each purchase takes 1 minute to complete, and it is only considered successful after the order is placed.
From these \( n \) items, you can choose any number (including zero) to purchase (each item can be purchased at most once), which constitutes a purchasing plan.
A purchasing plan with more items is considered better than another if the number of items is greater. If two plans have the same number of items but the total price of one is lower, the plan with the lower total price is considered better. Determine the number of items and the total price for the 1st to the \( k \)-th best purchasing plans among all valid plans.
Input Format
The first line contains two positive integers \( n \) and \( k \). It is guaranteed that \( k \) is not greater than the total number of valid plans.
The next \( n \) lines each contain two positive integers \( w_i \) and \( d_i \).
Output Format
Output \( k \) lines, where the \( i \)-th line contains the number of items and the total price for the \( i \)-th best plan.
Sample Input and Output
Input Sample #1
3 1
1 1
1 1
1 3
Output Sample #1
2 2
Input Sample #2
4 3
1 1
10 1
2 3
10 3
Output Sample #2
3 13
3 22
2 3
Input Sample #3
2 4
1 1
2 2
Output Sample #3
2 3
1 1
1 2
0 0
Notes
[Sample 2 Explanation]
The top \( k \) best plans are \(\{1,3,4\}\), \(\{2,3,4\}\), and \(\{1,3\}\) (using item indices to represent the items).
[Data Range and Constraints]
This problem uses subtask-based testing.
- 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 additional constraints.
For 100% of the data, \( 1 \le n, k \le 2000 \), \( 1 \le w_i \le 10^9 \), \( 1 \le d_i \le n \).
[Hints and Remarks]
The official data for each subtask includes 13 test cases, with a total time limit of up to 6.5 minutes. To reduce the load on the judging system, only the first two test cases from each subtask are used for evaluation.
This problem is translated from COCI 2021-2022 CONTEST #3 Task 3 Akcija.
The score for this problem is set according to the original COCI contest, with a maximum score of 110.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分