G. Максимизация определителя
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Матрица $$$B$$$ размером $$$n \times n$$$ называется интервальной матрицей, если для каждой строки $$$i$$$ существует непрерывный диапазон столбцов $$$[l_i, r_i]$$$ ($$$1 \le l_i \le r_i \le n$$$), заполненный единицами, в то время как все остальные элементы в строке равны нулю. Формально, $$$B_{i, j} = 1$$$, если $$$l_i \le j \le r_i$$$, и $$$B_{i, j} = 0$$$ в противном случае.

Вам дано целое число $$$n$$$ и начальная интервальная матрица $$$A$$$, описанная $$$n$$$ тройками $$$(l_i, r_i, a_i)$$$. $$$i$$$-я строка матрицы $$$A$$$ соответствует интервалу $$$[l_i, r_i]$$$, а $$$a_i$$$ — это стоимость изменения этой строки.

Обозначим $$$\mathcal{S}$$$ как множество всех возможных интервальных матриц размером $$$n \times n$$$. Определим $$$X$$$ как максимальный возможный определитель среди них: $$$$$$ X = \max\limits_{B \in \mathcal{S}} \operatorname{det}(B). $$$$$$ (Обратите внимание, что $$$|\mathcal{S}| = \left(\frac{n(n + 1)}{2}\right)^n$$$, так как каждая строка может быть любым допустимым интервалом)

Ваша цель — преобразовать $$$A$$$ в матрицу $$$A'$$$, такую что $$$\operatorname{det}(A') = X$$$. Для достижения этой цели вы можете выполнять следующую операцию любое количество раз:

  • Выберите индекс строки $$$i$$$ ($$$1 \le i \le n$$$) и новый допустимый интервал $$$[L, R]$$$ ($$$1 \le L \le R \le n$$$).
  • Замените текущий интервал $$$i$$$-й строки на $$$[L, R]$$$.
  • Стоимость этой операции составляет $$$a_i$$$.

Найдите минимальную общую стоимость, необходимую для того, чтобы сделать определитель матрицы равным $$$X$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — размер матрицы.

Следующие $$$n$$$ строк описывают строки матрицы $$$A$$$. $$$i$$$-я из этих строк содержит три целых числа $$$l_i$$$, $$$r_i$$$ и $$$a_i$$$ ($$$1 \le l_i \le r_i \le n$$$, $$$1 \le a_i \le 10^9$$$) — границы интервала и стоимость изменения $$$i$$$-й строки.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальную общую стоимость, необходимую для того, чтобы сделать $$$\operatorname{det}(A) = X$$$.

Пример
Входные данные
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
Выходные данные
0
2
3
1000
4000000000
14
Примечание

В первом наборе входных данных $$$n = 2$$$, и можно показать, что $$$X = 1$$$. Матрица $$$A = \begin{bmatrix} 1 & 0\\0 & 1\end{bmatrix}$$$. Поскольку $$$\operatorname{det}(A) = 1$$$, операции не требуются.

Во втором наборе входных данных $$$X$$$ по-прежнему равен $$$1$$$, но матрица $$$A = \begin{bmatrix} 0 & 1\\1 & 0\end{bmatrix}$$$. Определитель равен $$$-1$$$, поэтому мы должны преобразовать матрицу.

Можно доказать, что невозможно достичь определителя $$$1$$$ с помощью одной операции. Поэтому мы должны изменить обе строки. Одна из возможных последовательностей операций:

$$$$$$ \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} $$$$$$

Конечная матрица имеет определитель $$$1$$$. Общая стоимость составляет $$$a_2 + a_1 = 1 + 1 = 2$$$, что и является ответом.