Tariffs#2212
A mobile operator has decided to create several unlimited tariff plans, each with different monthly subscription fees and additional services. Customer relationship managers have determined how much each VIP subscriber is willing to spend on mobile services per month. Now, the company wants to offer each subscriber a personalized tariff plan. However, due to antitrust regulations, the company may offer no more than unlimited tariff plans.
Help the company's managers develop tariff plans to maximize the company's profit.
The first line contains two integers, the number of VIP subscribers (1 \leq N \leq 100) and the number of tariff plans (1 \leq K \leq 100). Following this are integers A_i (0 \leq A_i \leq 100000), where A_i is the amount the -th subscriber is willing to spend per month for communication services.
Output positive integers in ascending order, the subscription fees for the tariff plans. Each fee must be at least and no more than 10^9.
Each subscriber will be assigned to the tariff plan with the highest possible fee not exceeding A_i. If no such tariff plan exists, the subscriber will not be serviced by the company.
The company's profit is the sum of the subscription fees paid by all subscribers.
Comments on examples
Example 1: The subscriber willing to pay will not be serviced. The subscriber willing to pay is assigned to the first plan. Subscribers willing to pay are assigned to the second plan, those willing to pay and to the third plan, and the subscriber willing to pay to the fourth plan. The total profit is 4 + 5 \cdot 4 + 8 \cdot 2 + 80 = 120.
Example 2: Each subscriber is assigned to their own plan; the fourth plan is unused. Total profit is 1 + 2 + 30 = 33.
Example 3: All subscribers except the first and third are assigned to a single plan. Total profit is 4 \cdot 4 = 16.
Example 4: Since a zero fee plan is not allowed, the first and third subscribers will not be serviced.
Example 1