您有 $$$n$$$ 个赌场,编号从 $$$1$$$ 到 $$$n$$$。每个赌场由三个整数描述:$$$l_i$$$、$$$r_i$$$ 和 $$$real_i$$$ ($$$l_i \le real_i \le r_i$$$)。您最初拥有 $$$k$$$ 硬币。
只有当当前硬币数量 $$$x$$$ 满足 $$$l_i \le x \le r_i$$$ 时,您才可以在赌场 $$$i$$$ 玩。玩完后,您的硬币数量将变为$$$real_i$$$。
您可以按任意顺序参观赌场,无需参观所有赌场。每个赌场只能参观一次。
你的任务是找到你能获得的最大金币数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le k \le 10^9$$$) — 赌场数量和初始硬币数量。
接下来是 $$$n$$$ 行。在第 $$$i$$$ 行中,有三个整数 $$$l_i$$$、$$$r_i$$$、$$$real_i$$$ ($$$0 \le l_i \le real_i \le r_i \le 10^9$$$) — 第 $$$i$$$ 赌场的参数。
保证所有测试用例中所有 $$$n$$$ 的总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一个整数 - 在最佳选择访问赌场的顺序后可以获得的最大硬币数量。
示例
输入复制
53 12 3 31 2 23 10 101 01 2 21 21 2 22 21 3 22 4 42 51 10 53 6 5
输出复制
10 0 2 4 5
注意
在第一个测试用例中,您可以首先在 $$$2$$$-nd 赌场玩。之后,您将获得 $$$2$$$ 硬币。然后你就可以在$$$1$$$-st赌场玩,金币数量将增加到$$$3$$$。最后,在 $$$3$$$-rd 赌场玩完后,您将获得 $$$10$$$ 硬币 — 这是可能的最大金额。
在第二个测试用例中,你没有钱,所以你不能赚更多。
在第四个测试用例中,立即在 $$$2$$$-nd 赌场玩并赚取 $$$4$$$ 硬币是有益的。