Con los registros más altos de calor en el verano en la granja del Granjero Juan, él necesita enfriar a sus vacas. Por lo tanto, el decide invertir en algunos acondicionadores de aire.

Las N vacas del Granjero Juan ~(1 \leq N \leq 20)~ viven en un establo que contiene una sucesión de pesbreras en una fila, numeradas ~1...100~. La vaca ~i~ ocupa un rango de esas pesebreras, comenzando en la pesebrera ~s_i~ y terminando en la pesebrera ~t_i~. Los rangos depesebreras ocupadas por vacas diferentes son todos disjuntos uno de los otros. Las vacas tienen diferentes requirimientos de enfriamento. La vaca i debe ser enfriada en una cantidad c_i, indicando que cada pesebrera ocupada por la vaca i debe tener su temperatura reducida en almenos ~c_i~ unidades.

El establo contiene M acondicionares de aire, rotulados ~1....M (1 \leq M \leq 10)~.El acondicionador de aire i cuesta ~m_i~ unidades de dinero para funcionar ~(1 \leq m_i \leq 1000)~ y enfria en el rango de pesebreras comenzando en la pesebrera ~a_i~ y terminando con la pesebrera ~b_i~. Si funciona, el acondicionador de aire i reduce la temperatura de todas las pesebreras en este rango por ~p_i (1 \leq p_i \leq 10^6)~. Los rangos de pesebreras cubiertos por acondicionadores de aire pueden sobrelaparse potencialmente.

Manejar una granja no es un negocio facil, entonces GJ tiene un presupuesto apretado. Por favor, determina la cantidad mínima de dinero que necesita gastar para tener a todas sus vacas confortables. Se garantiza que si GJ usa todos sus acondicionadores de aire, entonces todas sus vacas estarán confortables.

Entrada

La primera línea contiene ~N~ y ~M~. Las N líneas siguientes describen a las vacas. La i-esima de esas líneas contiene ~s_i~, ~t_i~, y ~c_i~. Las siguientes ~M~ líneas describen a los acondicionares de aire. La i-esima de esas líneas contiene ~a_i~, ~b_i~, ~p_i~, y ~m_i~.

Para cada entrada diferente al ejemplo, usted puede asumir que ~M = 10~.

Salida

Da un solo entero diciendo la cantidad mínima de dinero que GJ necesita gastar para manejar suficientes acondicionares de aire para satisfacer a todas sus vacas (con los acondicionares antes listados).

Ejemplo de Entrada

2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5

Ejemplo de Salida

10

Una solución posible que restula en la menor cantidad de dinero gastada es seleccionar aquellos que enfrien los intervalos ~[2,9]~ , ~[1,2]~, y ~[6,9]~, para un costo de ~3 + 2 + 5 = 10~.