Un equipo de tres estudiantes participa en una olimpiada de programación poco común. Cada miembro del equipo tiene su propia computadora, así que el equipo puede trabajar en tres problemas simultáneamente.
La olimpiada tiene problemas. El problema se puede resolver solo si un participante trabaja en él sin interrupción desde el minuto l_i hasta el minuto r_i inclusive. Durante un minuto, un participante puede trabajar en un solo problema, y un problema no se puede repartir entre varios participantes. Por ejemplo, un participante puede resolver problemas que necesitan los minutos – y –, pero no problemas que necesitan los minutos – y –, porque ambos necesitan el minuto .
Por resolver el problema , el equipo recibe w_i puntos. Encuentra la mayor cantidad total de puntos que puede obtener el equipo.
La primera línea contiene un único entero (1 \le t \le 2 \cdot 10^5) — el número de casos de prueba.
La primera línea de cada caso de prueba contiene un único entero (1 \le n \le 2 \cdot 10^5) — el número de problemas.
Cada una de las siguientes líneas contiene tres enteros l_i, r_i y w_i (1 \le l_i \le r_i \le 10^9, 1 \le w_i \le 10^9) — el primer y el último minuto del problema y la cantidad de puntos que otorga.
Se garantiza que la suma de sobre todos los casos de prueba no supera 2 \cdot 10^5.
Para cada caso de prueba, imprime en una línea separada un único entero — la mayor cantidad total de puntos.
Ejemplo 1
En el primer caso de prueba, los cuatro problemas necesitan los minutos y , por lo que a lo sumo se pueden resolver tres de ellos. Lo más conveniente es renunciar al problema que vale puntos y obtener 3 + 4 + 5 = 12 puntos.
En el segundo caso de prueba, los primeros cuatro problemas necesitan el minuto , por lo que hay que renunciar a uno de ellos. Lo más conveniente es renunciar al tercer problema. Los otros cuatro problemas se pueden resolver: el primer participante resuelve los problemas (minutos –) y (minutos –), el segundo resuelve el problema , y el tercero resuelve el problema . En total, 10 + 1 + 10 + 7 = 28 puntos.
En el tercer caso de prueba, el único problema se puede resolver.