Los alienígenas del espacio exterior han invadido la Tierra (¡por fin!). ¡Defiéndete o serás desintegrado! O asimilado. O devorado. Todavía no estamos seguros.
Los alienígenas siguen un patrón de ataque conocido. Hay $n$ atacantes; el $i$-ésimo aparece en el instante $a_i$, a una distancia $d_i$ de ti. Debe ser destruido a más tardar en el instante $b_i$; de lo contrario, disparará su arma, lo que sin duda pondrá fin a la lucha.
Tu arma es un cañón de área que puede ajustarse a cualquier potencia. Al disparar con potencia $R$, destruye instantáneamente a todos los alienígenas a una distancia menor o igual que $R$. También consume $R$ celdas de combustible.
Determina el coste mínimo (medido en celdas de combustible) de destruir a todos los alienígenas sin que te maten.
El tamaño del archivo de entrada no supera 0.1 MiB.
Entrada
La primera línea de la entrada contiene el número de casos de prueba $T$. A continuación se describen los casos:
Cada caso comienza con una línea que contiene el número de alienígenas $n$ ($1 \le n \le 300$). De las siguientes $n$ líneas, la $i$-ésima contiene tres enteros $a_i$, $b_i$, $d_i$ ($1 \le a_i < b_i \le 10\,000$; $1 \le d_i \le 10\,000$). El $i$-ésimo alienígena aparece en el instante $a_i$, permanece inactivo hasta $b_i$ y está a una distancia $d_i$ de ti.
Salida
Para cada caso de prueba, escribe una línea con el número mínimo de celdas necesarias para destruir a todos los alienígenas.
Ejemplos
Entrada 1
1 3 1 4 4 4 7 5 3 4 7
Salida 1
7