Dekisugi has been recently hired by the Public Works Department of the Doracity for construction of its airport.
For constructing buildings,he requires iron rod of a fixed length L. Dekisugi being the most intelligent person in Doracity purchases iron rods from a notorious dealer named Takeshi . Takeshi has N iron rods . The of these rods can be moulded to have any length in the range [Ai, Bi], inclusive. Two rods with length [a,b] and [c,d] can be joined together to form a single rod of length [a+c,b+d].This rod can be combined again and so on.
However each rod has its cost and Dekisugi has exactly M Yen to spend.What is the smallest amount in which Dekisugi can achieve his goal or tell him that it is impossible.
The first line of the input contains the number of test cases, T. T test cases follow.
Each test case starts with 3 integers N, M, L, the number of iron rods available in the shop, the number of YEN you have and the desired iron length. Then N lines follow. Each line represents one iron rod and consists of 3 integers, Ai, Bi, and Pi. [Ai, Bi] is the inclusive range of lengths that the iron rod can expand to, and Pi is the price of the rod in YEN.
Constraints:-
1 ≤ T ≤ 100.
1 ≤ Pi ≤ M.
1 ≤ L ≤ 10000.
1 ≤ Ai ≤ Bi ≤ 10000.
Subtask 1: 20 points
1 ≤ N ≤ 10.
1 ≤ M ≤ 100.
Subtask 2: 80 points
1 ≤ N ≤ 1000.
1 ≤ M ≤ 1000000000.
In Case1, none of the iron rod in the shop are long enough on their own. It will not work to buy the two cheapest iron rods and join them together, because the new rod would have a range of [7, 9], which does not include 6. (Remember, the iron rod must be able to expand to a length of exactly L.) The optimal solution is to buy the iron rods costing 2 and 5 and join them together; the new rod has a range of [4, 7], which does include 6. You have 8 Yen, so you can afford the total cost of 7 Yen.
In Case2, Dekisugi need to buy all of the iron rods to be able to expand to length 14. That would cost 12 Yen, but he only have 11, so this case is IMPOSSIBLE.