← 返回题目列表

Codeforces · 2126/D

D. 这是最后一次

中文机器翻译题面 查看原题

您有 $$$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$$$。

输出

对于每个测试用例,输出一个整数 - 在最佳选择访问赌场的顺序后可以获得的最大硬币数量。

示例

输入
复制

5
3 1
2 3 3
1 2 2
3 10 10
1 0
1 2 2
1 2
1 2 2
2 2
1 3 2
2 4 4
2 5
1 10 5
3 6 5

输出
复制

10
0
2
4
5

注意

在第一个测试用例中,您可以首先在 $$$2$$$-nd 赌场玩。之后,您将获得 $$$2$$$ 硬币。然后你就可以在$$$1$$$-st赌场玩,金币数量将增加到$$$3$$$。最后,在 $$$3$$$-rd 赌场玩完后,您将获得 $$$10$$$ 硬币 — 这是可能的最大金额。

在第二个测试用例中,你没有钱,所以你不能赚更多。

在第四个测试用例中,立即在 $$$2$$$-nd 赌场玩并赚取 $$$4$$$ 硬币是有益的。