infO(1)Cup 2025 Day 1 - Mirror | SkiCircuit

After leaving Los Angeles, Little AD arrived in the InfO(1)Cup Ski Resort, the largest ski resort in the InfO(1)Cup Kingdom. The ski resort is made of $N+1$ points numbered from $0$ to $N$. The height of point $i$ is $H_i$, and $H_0 = 0$. There are no two points that have the same height.

For any two points $i$ and $j$ with $H_i \lt H_j$, there exists one chairlift that takes skiers from point $i$ to point $j$ and one slope that takes skiers from point $j$ to point $i$. Taking the slope from point $j$ to point $i$ takes exactly $H_j - H_i$ seconds. Please note that when taking the slope from point $j$ to point $i$, skiers are not required to visit all points $p$ with $H_i \lt H_p \lt H_j$. Moreover, when taking a chairlift from point $i$ to point $j$, skiers cannot stop at any point $p \neq j$.

It takes a skier $U_i$ seconds to get on a chairlift at point $i$ (regardless of where the chairlift goes) and $C_i$ seconds to get off a chairlift at point $i$ (regardless of where that chairlift comes from). $U_0 = C_0 = 0$.

Little AD wants to make a $K$-second circuit. That is, he wants to start from point $0$, visit all other $N$ points exactly once, and then return to point $0$, and he wants to spent at least $K$ seconds on the slopes.

Little AD hates (as much as any proven skier) to stay in one point for too long. Therefore, let $W_i$ be the total time Little AD spends at point $i$, and let $M$ be the maximum value along all $W_i$. Note that $W_0 = 0$ and, for all $1 \leq i \leq N$:

• $W_i = 0$, if Little AD reaches point $i$ on a slope and leaves point $i$ on a slope;
• $W_i = C_i$, if Little AD reaches point $i$ with a chairlift and leaves point $i$ on a slope;
• $W_i = U_i$, if Little AD reaches point $i$ on a slope and leaves point $i$ with a chairlift;
• $W_i = U_i + C_i$, if Little AD reaches point $i$ with a chairlift and leaves point $i$ with a chairlift.

Task

Now Little AD wonders: how much time does he need to spend in a single point so that he skis for a total of at least $K$ seconds? That is, what is the minimum value of $M$ he could achieve in order to spend at least $K$ seconds on the slopes?

Little AD needs your help! For $T$ given scenarios, you must find the minimum value of $M$ and help Little AD enjoy his well deserved ski holiday!

Input data

The first line of input contains $T$, the number of scenarios your program will have to solve. For each of the $T$ scenarios, the first line will contain $N$ and $K$. The $i$-th following $N$ lines will contain three values $H_i$, $U_i$, $C_i$. Please note that the input does not contain the values $H_0$, $U_0$ and $C_0$, since $H_0 = U_0 = C_0 = 0$.

Output data

There should be exactly $T$ lines of output, with the $i$-th line of output containing the answer for the $i$-th scenario.

Constraints and clarifications

• It is guaranteed that Little AD can ski at least $K$ seconds;
• $1 \leq T \leq 200$;
• Let $\sum N$ denote the sum of the values of $N$ for all scenarios.
• $1 \leq \sum N \leq 200 \ 000$;
• $1 \leq K \leq 10^{12}$;
• $1 \leq H_i, U_i, C_i \leq 10^6$, for all $1 \leq i \leq N$.

Example

stdin

2
3 5
1 8 6
5 3 2
2 6 8
3 6
1 8 6
5 3 2
2 6 8

stdout

2
8

Explanation

First scenario. Little AD gets on the chairlift at point $0$, then he gets off at point $2$ and skies down to point $3$. There he skies down to point $1$, where he skies back to point $0$.

Second scenario. Little AD gets on the chairlift at point $0$ and goes up to point $2$, where he gets off. Then he skies down to point $1$. There he gets on the chairlift and goes up to point $3$, where he gets down and skies back to point $0$.