A thief has entered a super shop at midnight. Poor thief came here because his wife had sent him to buy some necessary households. Instead of buying the items, he decided to steal them.

He has a bag with him which can carry up to W kg. On the list (given by his wife) there are four fields 1) item name, 2) the price of the item, 3) how many of this item is required and 4) the weight of this item. The items are solid items, so he can't take any item after dividing into pieces.

He wants to take items in his bag such that it fulfills his wife's list, and the total weight of the items is not greater than W. And he can't take any item other than the items mentioned in the list, otherwise his wife would find the item and he might get caught. But he can take more items than required. And he wants to sell those extra items and earn some money. Assume that he can take any item (is in the list) any number of times as long as it doesn't overflow the bag.

Now you are given the necessary information of the items and his bag, you have to find the maximum profit he can make.

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing two integers n (1 ≤ n ≤ 100) and W (1 ≤ W ≤ 10000), where n denotes the number of items. Each of the next n lines contains three integers p_i c_i w_i (1 ≤ p_i, c_i, w_i ≤ 100), meaning that the price of the i^th item is p_i, c_i of it must be taken, and the weight is w_i.

For each case, print the case number and the maximum profit he can get. If it's impossible to fulfill his wife's requirements, print Impossible.