大鱼吃小鱼

题目背景

吞食鱼，又被称为大鱼吃小鱼，作为一款已经凉凉的公司宝开旗下的经典小游戏，它陪伴了很多人的童年。

现在让我们重温这一经典游戏。

题目描述

游戏一共有T关，每一关中，你操控的小鱼的初始得分为0，大海中有n种鱼类，其中追捕一只i类鱼需要花

费你t；的时间，然后你将顺利吃掉它，并获得pi的分数。

但当然，你是无法吃掉比你大的鱼的，所以对于第i类鱼，你只有得分大于等于a；时，你才可以去追捕这类鱼。

大海毕竟很大，所以每种鱼都有无限条。

当你的分数大于等于k时，游戏立即结束，进入结算（此时往往会有一条美人鱼飘过给你送星星吃）。

当然，你想要挑战游戏的极限一—速通！所以你想知道，对于每一关，通关最少需要的时间为多少。

输入格式

第一行一个整数T，表示关卡数。

对于每一个关卡，第一行两个整数n，k，含义如题所示。

接下来的n行，每行三个整数a；，pi，t，含义如题所示。

输出格式对于每一个关卡，输出一行一个整数，表示最速通关所需的时间。

保证每一关都存在通关方法。

【样例输入】 2

2 10

0 2 3

5 3 5

2 9

0 2 3

5 3 5

【样例输出】

15

14