Leonardo está fundando Bytecomp, una compañía que ofrece poder de cómputo en la nube. Empresas con este perfil generalmente tiene muchas computadoras rápidas en las que los clientes pueden realizar sus cálculos.

Leonardo todavía no ha comprado ninguna máquina. Fue a una tienda de computadoras y recibió una lista de todos los ~n~ ordenadores disponibles. Cada computadora está especificada por el número de núcleos (procesador) ~c_i~, la velocidad de reloj ~f_i~ y el precio ~v_i~. Dicha computadora contiene ~c_i~ núcleos separados que no interfieren entre sí, por lo que pueden asignarse a diferentes tareas.

Cuando un cliente realiza un pedido de recursos, ella especifica el número requerido de núcleos ~C_j~ y la velocidad mínima necesaria del reloj ~F_j~. Un pedido también contiene el precio ~V_j~ que el cliente está dispuesto a pagar. Si se acepta un pedido, Bytecomp debe proporcionar acceso exclusivo a la potencia de cómputo requerida por el cliente. Leonardo debe elegir los núcleos ~C_j~ (posiblemente de diferentes computadoras), cada uno con velocidad de reloj al menos ~F_j~. Esos núcleos no pueden ser asignados a ningún otro orden.

Tarea

Ayude a Leonardo a ganar tanto como sea posible: elija un subconjunto óptimo de órdenes para aceptar y un subconjunto de Ordenadores de la tienda para satisfacer todos los pedidos aceptados. Su objetivo es maximizar el beneficio total, que es decir, la diferencia entre las ganancias por proporcionar potencia de cálculo a los clientes y el costo de comprar los ordenadores.

Entrada

La primera línea de la entrada estándar contiene un entero ~n~ ~(1 \le n \le 2000)~, el número de computadoras que están disponibles en la tienda. Cada una de las siguientes ~n~ líneas contiene una descripción de una computadora. Consta de tres enteros separados por espacios ~c_i~, ~f_i~, y ~v_i~ ~(1 \le c i \le 50, 1 \le f_i \le 10^9, 1 \le v_i \le 10^9)~ que representan el número de núcleos, la velocidad de reloj, y el precio, respectivamente.

La siguiente línea contiene un número entero ~m~ ~(1 \le m \le 2000)~, el número de órdenes. Cada una de las siguientes ~m~ lineas contiene una descripción de un pedido. Consta de tres enteros separados por espacios ~C_j~, ~F_j~ y ~V_j~ ~(1 \le C_j \le 50, 1 \le F_j \le 10^9, 1 \le V_j \le 10^9)~ que representan el número de núcleos necesarios, la velocidad de reloj mínima permitida y la capacidad del cliente presupuesto, respectivamente.

Salida

La única línea de la salida estándar debe contener un entero, la ganancia total máxima que se puede lograr.

Ejemplo de Entrada

4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550

Ejemplo de Salida

350

Explicación del ejemplo:

Hay cuatro computadoras disponibles y tres órdenes. Es óptimo comprar dos computadoras de cuatro núcleos que cuestan 700 y 750 (1450 en total) y luego aceptan las dos primeras órdenes para ganar 300 + 1500 = 1800 en total. Luego tenemos cuatro núcleos con velocidad de reloj 2000 y cuatro núcleos con velocidad de reloj 2200.

Podemos asignar seis de ellos al segundo pedido (se necesita 1900) y uno al primer pedido (reloj tasa 1500 necesaria). No se utilizará un núcleo, lo que está permitido.

El beneficio total es 1800 - 1450 = 350.

Calificacion

El conjunto de prueba se divide en las siguientes subtareas con restricciones adicionales. Pruebas en cada una de las subtareas, consisten en uno o más grupos de prueba separados. Cada grupo de prueba puede contener uno o más casos de prueba.

Subtarea 1 Restricciones: n ≤ 15; Puntos: 18

Subtarea 2 Restricciones: m ≤ 15; Puntos: 18

Subtarea 3 Restricciones: ~n~, ~m \le 250,~ ~c_i = C_j = 1~; Puntos: 18

Subtarea 4 Restricciones: ~f_i = F_j = 1~; Puntos: 18

Subtarea 5 Restricciones: ~v_i = V_j = 1~; Puntos: 18

Subtarea 6 sin restricciones adicionales Puntos: 10