Christmas, a time for giving. Mr. Malnar is in need of gift ideas. Although deep in thought, the television program grabs his attention: "Special offer! This amazing product is on sale for just ~w~ kunas. Call now because the offer is available only if you call within the next ~d~ minutes. But that's not all..."

There are ~n~ different products on sale, where the ~i^\text{th}~ product has a cost of ~w_i~, and it's available for order until the minute ~d_i~ (inclusive). Making a call to place an order requires one minute. A subset of products is called obtainable if it is possible to make a sequence of calls which order those products while meeting the mentioned deadlines. No product can be ordered more than once.

Mr. Malnar intends to buy as many products as possible, at the least possible price, but he's not yet sure which products he should buy. He compares two obtainable subsets in the following way: the better obtainable subset is the one with more products, and if they have equal size, it's the one that has a smaller total cost (sum of costs of chosen products).

Mr. Malnar will rank the obtainable subsets in the described manner, and he will take into consideration ~k~ of the best ones. Write a program that determines the size and the total cost for ~k~ of the best obtainable subsets.

Input Specification

The first line contains positive integers ~n~ and ~k~, the number of different products and the number of obtainable subsets to be taken into consideration, respectively. ~k~ will be less than or equal to the total number of obtainable subsets.

The following ~n~ lines contain two positive integers ~w_i~ ~(1 \le w_i \le 10^9)~ and ~d_i~ ~(1 \le d_i \le n)~, the cost of the ~i^\text{th}~ product and the last minute for which the offers stand, respectively.

Output Specification

In the ~i^\text{th}~ line, print the size and the total cost of the ~i^\text{th}~ best obtainable subset.

Constraints

For all subtasks:

~1 \le n, k \le 2000~

Subtask	Points	Constraints
1	10	~k = 1~, ~w_1 = \dots = w_n~
2	20	~k = 1~
3	20	~k = 2~
4	10	~1 \le n \le 20~
5	30	~1 \le n, k \le 100~
6	20	No additional constraints.

Sample Input 1

3 1
1 1
1 1
1 3

Sample Output 1

2 2

Sample Input 2

4 3
1 1
10 1
2 3
10 3

Sample Output 2

3 13
3 22
2 3

Explanation for Sample Output 2

Products ~1~ and ~2~ can't simultaneously be in an obtainable subset, so the three best obtainable subsets are ~\{1, 3, 4\}~, ~\{2, 3, 4\}~, and ~\{1, 3\}~.

Sample Input 3

2 4
1 1
2 2

Sample Output 3

2 3
1 1
1 2
0 0