22848번 - 조화로운 마법 농구 게임

오랜만에 마법 놀이공원에 놀러간 마법사 루나는 본인이 제일 좋아하는 마법 농구 게임을 발견했다.

마법 농구 게임은 $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_j, R_j, S_j$ 가 공백으로 구분되어 차례로 주어진다. 

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

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