Optimal Storage Problem

You are given a warehouse with a limited volume V and n types of widgets. Each widget type is described by its name, volume, and value. Your task is to choose an integer number of copies of one or more widget types such that the total volume is exactly V and the total value is maximized.

If it is impossible to exactly fill the warehouse with any combination of widgets, output IMPOSSIBLE.

Note: You can use an unlimited supply of each widget and the answer should print the chosen widget names along with the number of copies used. In case of multiple possible optimal solutions, any one of them is acceptable.

The optimization can be formulated as an unbounded knapsack problem. The recurrence is given by:

[ \text{dp}[j] = \max_{\text{for each widget } i \text{ with volume } v_i \le j}{\text{dp}[j-v_i] + w_i } ]

where \(dp[j]\) denotes the maximum value achievable with a total volume of exactly \(j\), and \(w_i\) is the value of widget \(i\).

inputFormat

The first line contains two integers n and V, where n is the number of widget types and V is the total volume of the warehouse.

Each of the following n lines contains a widget's description in the format:

name volume value

All numbers are positive integers. The widget names are strings without spaces.

outputFormat

If it is possible to exactly fill the warehouse, output one or more lines, each containing the widget name and the number of copies used, separated by a space. The order of widget names should be the same as their input order if they are used in the solution.

If there is no combination of widgets that exactly fills the volume V, output a single line containing IMPOSSIBLE.

## sample

3 50
gadget 10 60
doohickey 20 100
thingamajig 30 120

gadget 5

</p>