Вам даны $$$n$$$ казино, пронумерованных от $$$1$$$ до $$$n$$$. Каждое казино описывается тремя целыми числами: $$$l_i$$$, $$$r_i$$$ и $$$real_i$$$ ($$$l_i \le real_i \le r_i$$$). У вас изначально есть $$$k$$$ монет.
Вы можете сыграть в казино $$$i$$$, только если для текущего количества монет $$$x$$$ верно $$$l_i \le x \le r_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$$$-е казино. После этого у вас будет $$$2$$$ монеты. Затем можно сыграть в $$$1$$$-е казино, и количество монет увеличится до $$$3$$$. Наконец, после игры в $$$3$$$-м казино, у вас становится $$$10$$$ монет — это и есть максимальное возможное количество.
Во втором примере у вас нет денег, так что вы не сможете заработать больше.
В четвертом примере вам выгодно сразу сыграть во $$$2$$$-е казино и заработать $$$4$$$ монеты.
| Codeforces Round 1037 (Div. 3) |
|---|
| Закончено |
