The store purchases bolts (
bolt) and nuts (
nut), for which a certain amount of money is 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 items in different ways, you need to choose the method that will buy the most bolts.
- If you can buy the maximum number of products with the same number of bolts in different ways, you need to choose the method in which the entire purchase will be cheaper.
Determine how many bolts will be purchased 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 product (bolt - bolt, nut - nut). 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 6500
1500 nuts
500 nut
3500 bolt
3000 bolt
2500 nut
1000 bolt
2 500 |
|