Two Histograms

당신에게 $10^6\times 10^6$ 크기의 정사각형 모양의 격자판 세 개가 주어진다. 각 칸은 $x$좌표와 $y$좌표로 번호가 매겨져 있다. $x$좌표는 맨 왼쪽에서부터 맨 오른쪽까지 $1$부터 $10^6$으로 매겨져 있고, $y$좌표는 맨 아래에서부터 맨 위까지 $1$에서 $10^6$으로 매겨져 있다. 당신은 각 칸을 검은색 혹은 흰색으로 칠해야 한다.

세 격자의 격자칸을 색칠하는 예시.

첫 번째 격자판은 아래에서부터 올라오는 히스토그램의 형태를 띄어야 한다. 즉, 어떤 격자칸이 검은색으로 칠해져 있다면, 그 아래의 칸도 검은색으로 칠해져 있어야 한다.

두 번째 격자판은 왼쪽에서부터 오른쪽으로 진행하는 히스토그램의 형태를 띄어야 한다. 즉, 어떤 격자칸이 검은색으로 칠해져 있다면, 그 왼쪽 칸도 검은색으로 칠해져 있어야 한다.

세 번째 격자판은 앞의 두 격자판을 이용해 색칠한다. 어떤 칸 $(x,y)$가 첫 두 격자판에서 모두 검은색으로 색칠되어 있다면, 세 번째 격자판의 칸 $(x,y)$ 역시 검은색으로 색칠한다. 그렇지 않다면, 해당 칸을 흰색으로 색칠한다. 이 세 번째 격자판이 최종 그림이 된다.

당신이 그린 그림을 $N$명이 심사위원에게 심사할 예정이다. 각 심사위원은 그림 내의 특정한 $K\times 1$ 직사각형 영역을 심사에 이용한다. $i$번째 심사위원이 이용하는 직사각형 영역은 $[x_i,x_i+K-1]\times[y_i , y_i]$이다. 각 심사위원들이 심사에 이용하는 직사각형 영역은 겹치지 않는다.

$i$번째 심사위원은 칸 $(x_i,y_i)$와 칸 $(x_i+K-1,y_i)$가 같은 색으로 칠해진 경우 불합격으로 판정한다. 두 칸의 색이 다른 경우에는 합격으로 판정하고, 칸 $(x_i,y_i)$가 흰색으로 칠해진 경우에 $a_i$점을, 검은색으로 칠해진 경우에 $b_i$점을 준다.

심사를 통과하기 위해서는 모든 심사위원에게 합격 판정을 받아야 한다. 이때 그림의 점수는 모든 심사위원들에게 받은 점수의 합이 된다. 심사를 통과하는 가능한 모든 그림에 대해서 받을 수 있는 점수의 최댓값을 구해 보자.

첫 번째 줄에는 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다.

다음 $N$개의 줄 중 $i$번째 줄에는 네 정수 $x_i$, $y_i$, $a_i$, $b_i$가 공백으로 구분되어 주어진다.

심사를 통과하는 그림이 없다면, $-1$을 출력한다.

심사를 통과하는 그림이 있다면, 가능한 그림의 최대 점수를 출력한다.

• $1\leq N\leq 3\times 10^5$
• $2\leq K\leq 10^6$
• $1\leq x_i\leq 10^6-K+1$ ($1\leq i\leq N$)
• $1\leq y_i\leq 10^6$ ($1\leq i\leq N$)
• $1\leq a_i,b_i\leq 10^9$ ($1\leq i\leq N$)
• $N$개의 직사각형 영역 $[x_i,x_i+K-1]\times[y_i , y_i]$ ($1\leq i\leq N$)는 서로 겹치지 않는다.

$[x_l,x_r]\times[y_l , y_r]$ 직사각형 영역은 $x_l\le x\le x_r$이고 $y_l\le y\le y_r$인 영역을 의미한다.