The store purchases bolts (
bolt), nuts (
nut), nails (
pin), washers (
shim) and screws (
screw), for which a certain amount of money has been allocated. The hardware plant has various modifications of these products at a retail price. When buying, the manager is guided by the following rules:
- You need to buy as many items as possible, regardless of their type and modification.
- If you can buy the maximum number of two different products in different ways, you need to choose the method that will buy the most nuts.
- If you can buy the maximum number of products with the same number of nuts in different ways, you need to choose the method in which the entire purchase will be cheaper.
Determine how many nuts will be bought in total and how much will remain unused.
Input
The program receives several lines as input. The first line contains two numbers separated by a space: N - the total number of bolts and nuts at the hardware plant and M - the amount of money allocated for the purchase (in rubles). Each of the next N lines contains an integer (price of the product in rubles) and the type of the product. All data in the lines is separated by a single space.
Imprint
In your answer, write down two whole numbers: first, the number of bolts purchased, then the remaining unused amount of money. (in one line with one space)
Examples
| # |
Input |
Output |
| 1 |
6 1650
600 screw
750 bolt
750 nut
450 pin
300 nut
150 bolt
2 0 |
|