Optimal Purchase Plans

You are given n items. The i-th item has a price \(w_i\) and a deadline \(d_i\), meaning that the item must be purchased before minute \(d_i\). Purchasing an item takes exactly one minute (i.e. placing an order takes one minute, and only after that the purchase is successful).

You may choose any subset (possibly empty) of these items (each at most once) to purchase. A purchasing plan is valid if there exists an ordering of the items such that the j-th purchased item is ordered in minute \(j\) and for each purchased item the requirement \(j \le d_i\) (when sorted in the order of purchase) is satisfied.

The ranking of valid purchasing plans is defined as follows:

1. A plan with more items is considered better than one with fewer items.
2. If two plans have the same number of items, the plan with the lower total price is considered better.

Your task is: given n and an integer \(k\), among all valid purchasing plans, determine for the top \(1\) to \(k\) plans what are the number of items purchased and the total price.

Note: If there are less than \(k\) distinct valid outcomes, you may assume that \(k\) does not exceed the number of distinct valid plans.

inputFormat

The first line contains two integers \(n\) and \(k\) (\(1 \le n \le 100\)), where \(n\) is the number of items and \(k\) is the number of top plans to output.

Each of the next \(n\) lines contains two integers \(w_i\) and \(d_i\) (\(1 \le w_i \le 10^9, 1 \le d_i \le 10^9\)), representing the price and the deadline of an item respectively.

outputFormat

Output \(k\) lines. The i-th line should contain two integers: the number of items purchased and the total price for the \(i\)-th best valid purchasing plan. The plans are ranked primarily by number of items (more is better) and secondarily by total price (less is better).

sample

3 3
2 1
3 2
1 2

2 3
2 4
2 5