2126D.md (2066B)
1 Source: https://codeforces.com/problemset/problem/2126/D 2 3 D. This Is the Last Time 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given $n$ casinos, numbered from $1$ to $n$. Each casino is described by three integers: $l_i$, $r_i$, and $real_i$ ($l_i \le real_i \le r_i$). You initially have $k$ coins. 22 23 You can play at casino $i$ only if the current number of coins $x$ satisfies $l_i \le x \le r_i$. After playing, your number of coins becomes $real_i$. 24 25 You can visit the casinos in any order and are not required to visit all of them. Each casino can be visited no more than once. 26 27 Your task is to find the maximum final number of coins you can obtain. 28 29 Input 30 31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 32 33 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 10^5$, $0 \le k \le 10^9$) — the number of casinos and the initial number of coins. 34 35 This is followed by $n$ lines. In the $i$-th line, there are three integers $l_i$, $r_i$, $real_i$ ($0 \le l_i \le real_i \le r_i \le 10^9$) — the parameters of the $i$-th casino. 36 37 It is guaranteed that the sum of all $n$ across all test cases does not exceed $10^5$. 38 39 Output 40 41 For each test case, output a single integer — the maximum number of coins you can obtain after optimally choosing the order of visiting the casinos. 42 43 Example 44 45 Input 46 47 ``` 48 5 49 50 3 1 51 52 2 3 3 53 54 1 2 2 55 56 3 10 10 57 58 1 0 59 60 1 2 2 61 62 1 2 63 64 1 2 2 65 66 2 2 67 68 1 3 2 69 70 2 4 4 71 72 2 5 73 74 1 10 5 75 76 3 6 5 77 ``` 78 79 Output 80 81 ``` 82 10 83 0 84 2 85 4 86 5 87 ``` 88 89 Note 90 91 In the first test case, you can first play at the $2$-nd casino. After that, you will have $2$ coins. Then you can play at the $1$-st casino, and the number of coins will increase to $3$. Finally, after playing at the $3$-rd casino, you will have $10$ coins — this is the maximum possible amount. 92 93 In the second test case, you have no money, so you cannot earn more. 94 95 In the fourth test case, it is beneficial to play at the $2$-nd casino right away and earn $4$ coins.