선분 제거

좌표축 위에 점 $1, 2, \ldots, x$가 있다. 시작점과 끝점이 모두 이 점들 위에 있는 선분들이 주어진다. 각 선분에는 가중치 $w_i$와 페널티 $p_i$가 정해져 있다.

처음 점수는 $0$이다. 각 이동에서는 주어진 선분 중 하나를 골라 집합에서 제거한다. 이때 점수는 그 선분의 페널티만큼 줄어든다. 대신 점수는 선분의 가중치에 곱한 값만큼 늘어난다. 곱하는 값은 이 순간 그 선분이 집합에서 유일하게 덮고 있는 정수 좌표 점의 개수이다. 선분은 양 끝점도 덮는 것으로 본다.

이동마다 얻은 점수의 합이 총점이다. 얻을 수 있는 총점의 최댓값을 구하라.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 2 \cdot 10^5$)가 주어진다. 이후 테스트 케이스들이 이어진다.

각 테스트 케이스의 첫 줄에는 선분의 개수 $n$ ($1 \le n \le 2 \cdot 10^5$)과 최대 좌표 $x$ ($1 \le x \le 5 \cdot 10^5$)가 주어진다.

다음 $n$개의 줄에는 선분 정보가 주어진다. 각 줄에는 정수 네 개가 있으며, 순서대로 선분의 시작점 $\ell_i$, 끝점 $r_i$ ($1 \le \ell_i \le r_i \le x$), 가중치 $w_i$ ($1 \le w_i \le 10^9$), 페널티 $p_i$ ($1 \le p_i \le 10^9$)이다.

모든 테스트 케이스에서 $n$의 합은 $2 \cdot 10^5$를 넘지 않는다. $x$의 합은 $5 \cdot 10^5$를 넘지 않는다.

각 테스트 케이스마다 얻을 수 있는 최대 점수를 한 줄에 정수 하나로 출력한다.