조화로운 마법 농구 게임

마법사 루나는 오랜만에 마법 놀이공원에 놀러 갔다가 자신이 가장 좋아하는 마법 농구 게임을 발견했다.

마법 농구 게임은 $K$개의 라운드로 진행된다. 각 라운드마다 골대는 1번 상태에서 시작해 $N$번 상태까지 차례대로 변하며, 루나는 각 상태에서 공을 한 번씩 던진다. $j$번 상태는 $(L_j, R_j, S_j)$로 나타낼 수 있고, 공을 던진 위치 $x$가 $L_j \leq x \leq R_j$를 만족하면 $S_j$점을 얻는다.

골대의 상태는 다음 두 조건을 만족한다.

• $j$가 홀수일 때, $j$번 상태에서 $j+1$번 상태로 변하는 동안 마법 농구 골대는 늘어난다. 이는 $L_{j+1} \leq L_j$, $R_j \leq R_{j+1}$을 의미한다.
• $j$가 짝수일 때, $j$번 상태에서 $j+1$번 상태로 변하는 동안 마법 농구 골대는 줄어든다. 또한 $j+1$번째 상태와 $j-1$번째 상태는 겹치지 않는다. 이는 $L_j \leq L_{j+1}$, $R_{j+1} \leq R_j$, $[L_{j-1}, R_{j-1}] \cap [L_{j+1}, R_{j+1}] = \varnothing$을 의미한다.

루나는 각 라운드에서 매번 같은 위치에 공을 던진다. 구체적으로 $i$번째 라운드에서는 매번 위치 $i$에만 공을 던진다. 실수로 위치가 빗나가는 경우는 없다.

루나는 공을 던지기 직전에 자신의 마법을 사용해 공에 축복을 부여할 수 있다. 축복을 받은 공이 골대에 들어가면 두 배의 점수를 얻는다. 하지만 마법에는 대기 시간이 있어서 한 라운드에서 연속한 두 번의 시도에는 축복을 부여할 수 없다.

루나는 $K$라운드에 걸쳐 얻은 점수를 최대로 만들고자 한다. 하지만 루나는 자신의 또 다른 자아인 흑마법사 리나가 이를 방해하려 한다는 사실을 꿈에도 모른다.

리나는 자아의 이면에서 잠자코 있다가 갑자기 $a$라운드가 시작하기 직전에 나타나 $b$라운드가 끝날 때까지 공을 던진 뒤 다시 자아의 이면으로 돌아간다. 리나는 모든 공에 축복 대신 저주를 걸어 던지므로, 공이 들어가면 얻어야 할 점수만큼 오히려 감점된다. 루나는 $1$라운드부터 $a-1$라운드까지는 리나의 개입을 모른 채 게임을 하다가, $b+1$라운드가 시작하기 전에야 리나가 다녀간 사실을 알아차리고, 기왕 이렇게 된 거 자신의 철학에 따라 점수의 절댓값이라도 최대화하기 위해 게임을 이어 간다.

이 사실을 잘 아는 리나는 점수의 절댓값이 최소가 되도록 최선을 다해 플레이하고, 자신이 등장할 첫 라운드와 마지막 라운드인 $a$, $b$를 모두 루나가 모르게 미리 정할 수 있다. 이때 게임의 결과로 얻게 될 점수의 절댓값을 구해보자!

첫째 줄에는 두 개의 정수 $N, K$가 주어진다.

이후 두 번째 줄부터 $N+1$번째 줄까지, $i+1$번째 줄에는 $i$번 상태를 나타내는 정수 $L_i, R_i, S_i$가 공백으로 구분되어 차례로 주어진다.

게임의 결과로 얻게 될 점수의 절댓값을 출력한다.

• $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$는 지문의 조건을 만족한다.