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 kunas. Call now because the offer is available only if you call within the next minutes. But that's not all..."
There are different products on sale, where the product has a cost of , and it's available for order until the minute (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 of the best ones. Write a program that determines the size and the total cost for of the best obtainable subsets.
The first line contains positive integers and , the number of different products and the number of obtainable subsets to be taken into consideration, respectively. will be less than or equal to the total number of obtainable subsets.
The following lines contain two positive integers and , the cost of the product and the last minute for which the offers stand, respectively.
In the line, print the size and the total cost of the best obtainable subset.
For all subtasks:
|6||20||No additional constraints.|
Sample Input 1
3 1 1 1 1 1 1 3
Sample Output 1
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 and can't simultaneously be in an obtainable subset, so the three best obtainable subsets are , , and .
Sample Input 3
2 4 1 1 2 2
Sample Output 3
2 3 1 1 1 2 0 0