Harmonious Magic Basketball Game

Magician Luna visited a magic amusement park after a long time and found her favorite game, the magic basketball game.

The magic basketball game has $K$ rounds. In each round the hoop keeps changing shape. Specifically, in every round the hoop starts at state 1 and changes in order through state $N$, and Luna throws the ball once for each state. State $j$ is represented by $(L_j, R_j, S_j)$: if the thrown position $x$ satisfies $L_j \leq x \leq R_j$, she earns $S_j$ points.

The hoop states satisfy the following two conditions.

• When $j$ is odd, the magic basketball hoop expands from state $j$ to state $j+1$. This means $L_{j+1} \leq L_j$ and $R_j \leq R_{j+1}$.
• When $j$ is even, the hoop shrinks from state $j$ to state $j+1$. Also, state $j+1$ and state $j-1$ do not overlap. This means $L_j \leq L_{j+1}$, $R_{j+1} \leq R_j$, and $[L_{j-1},R_{j-1}] \cap [L_{j+1},R_{j+1}] = \varnothing$.

Luna decides to throw the ball at the same position every time in each round. Specifically, in round $i$ she throws the ball only at position $i$ every time. She never misses the position by mistake.

Just before throwing a ball, Luna can use her magic to put a blessing on it. If a blessed ball enters the hoop, she earns double points. However, the magic has a cooldown, so she cannot bless two consecutive attempts in one round.

Luna wants to maximize the total score earned over $K$ rounds. But she does not know at all that her other self, the dark magician Lina, wants to interfere.

Lina waits quietly behind her other self, then suddenly appears just before round $a$ begins. She throws balls until the end of round $b$ and returns behind her other self. Lina throws every ball with a curse instead of a blessing, so a successful shot subtracts the points she would have earned. Luna plays rounds $1$ through $a-1$ without knowing about Lina's intervention. Only before round $b+1$ begins does she notice that Lina was there. Now that things have turned out this way, she continues the game according to her philosophy, aiming to maximize the absolute value of the score.

Lina knows this as well. She will do her best to minimize the absolute value of the score, and she can choose in advance, without Luna knowing, both the first and last rounds of her appearance, $a$ and $b$. Find the absolute value of the score obtained as the result of the game.

The first line contains two integers $N$ and $K$.

For each $i$ from $1$ to $N$, the $(i+1)$-th line contains the integers $L_i$, $R_i$, and $S_i$ that represent state $i$, separated by spaces.

Print the absolute value of the score obtained as the result of the game.

• $1 \leq N,K \leq 10^6$
• $1 \leq L_j \leq R_j \leq 10^6$
• $1 \leq S_j \leq 10^6$
• $L_j, R_j, S_j$ satisfy the conditions in the statement.