G. Maximize Determinant
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

An $$$n \times n$$$ matrix $$$B$$$ is called an interval matrix if for each row $$$i$$$, there exists a contiguous range of columns $$$[l_i, r_i]$$$ ($$$1 \le l_i \le r_i \le n$$$) filled with ones, while all other elements in the row are zero. Formally, $$$B_{i, j} = 1$$$ if $$$l_i \le j \le r_i$$$, and $$$B_{i, j} = 0$$$ otherwise.

You are given an integer $$$n$$$ and an initial interval matrix $$$A$$$, described by $$$n$$$ triples $$$(l_i, r_i, a_i)$$$. The $$$i$$$-th row of $$$A$$$ corresponds to the interval $$$[l_i, r_i]$$$, and $$$a_i$$$ is the cost associated with modifying this row.

Let $$$\mathcal{S}$$$ be the set of all possible $$$n \times n$$$ interval matrices. We define $$$X$$$ as the maximum possible determinant among them: $$$$$$ X = \max\limits_{B \in \mathcal{S}} \operatorname{det}(B). $$$$$$ (Note that $$$|\mathcal{S}| = \left(\frac{n(n + 1)}{2}\right)^n$$$, as each row can be any valid interval)

Your goal is to transform $$$A$$$ into a matrix $$$A'$$$ such that $$$\operatorname{det}(A') = X$$$. To achieve this, you can perform the following operation any number of times:

  • Choose a row index $$$i$$$ ($$$1 \le i \le n$$$) and a new valid interval $$$[L, R]$$$ ($$$1 \le L \le R \le n$$$).
  • Replace the current interval of the $$$i$$$-th row with $$$[L, R]$$$.
  • The cost of this operation is $$$a_i$$$.

Find the minimum total cost required to make the determinant of the matrix equal to $$$X$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the size of the matrix.

The next $$$n$$$ lines describe the rows of the matrix $$$A$$$. The $$$i$$$-th of these lines contains three integers $$$l_i$$$, $$$r_i$$$, and $$$a_i$$$ ($$$1 \le l_i \le r_i \le n$$$, $$$1 \le a_i \le 10^9$$$) — the interval boundaries and the cost of modifying the $$$i$$$-th row.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer — the minimum total cost required to make $$$\operatorname{det}(A) = X$$$.

Example
Input
6
2
1 1 1
2 2 1
2
2 2 1
1 1 1
4
1 4 4
2 2 3
4 4 6
2 4 5
6
1 6 1
5 5 1000
2 4 1000
6 6 1000
3 3 1000
4 4 1000
5
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
5
1 4 15
4 4 14
2 3 16
2 2 14
3 5 15
Output
0
2
3
1000
4000000000
14
Note

In the first example, $$$n = 2$$$ and it can be shown that $$$X = 1$$$. The matrix is $$$A = \begin{bmatrix} 1 & 0\\0 & 1\end{bmatrix}$$$. Since $$$\operatorname{det}(A) = 1$$$, no operations are needed.

In the second example, $$$X$$$ is still $$$1$$$, but the matrix is $$$A = \begin{bmatrix} 0 & 1\\1 & 0\end{bmatrix}$$$. The determinant is $$$-1$$$, so we must transform the matrix.

It can be proven that it is impossible to reach a determinant of $$$1$$$ with a single operation. Therefore, we must modify both rows. One possible sequence of operations is:

$$$$$$ \begin{bmatrix} 0 & 1\\1 & 0\end{bmatrix} \xrightarrow{i = 2, \, L = 2, \, R = 2} \begin{bmatrix} 0 & 1\\0 & 1\end{bmatrix} \xrightarrow{i = 1, \, L = 1, \, R = 2} \begin{bmatrix} 1 & 1\\0 & 1\end{bmatrix} $$$$$$

The final matrix has a determinant of $$$1$$$. The total cost is $$$a_2 + a_1 = 1 + 1 = 2$$$, which is the answer.