Cooling the Cows

Farmer John has encountered an extremely hot summer at his farm and needs to cool down his cows. The barn contains 100 consecutive stalls, and his N cows (1≤N≤20) each occupies a contiguous set of stalls. Specifically, cow i occupies the stalls from s_i to t_i (with the ranges for different cows disjoint), and requires that every stall in its range gets a cooling effect of at least c_i units.

The barn is equipped with M air conditioners (1≤M≤10). The j-th air conditioner, if turned on, will cool every stall in the range from a_j to b_j by p_j units and costs m_j money to operate. Note that the ranges covered by different air conditioners may overlap, summing their cooling effects on overlapping stalls.

The goal is to help Farmer John determine the minimum amount of money he must spend so that for every cow, every stall in its range receives a total cooling amount of at least c_i units. Formally, if you denote by T(k) the total cooling at stall k from the set of activated air conditioners, then for every cow i with range [s_i, t_i], you must have:

It is guaranteed that if all the air conditioners are used, then all cows will be comfortable.

inputFormat

The first line contains two integers N and M.

The following N lines each contain three integers s_i, t_i, and c_i, representing the starting stall, ending stall, and cooling requirement for cow i.

The next M lines each contain four integers a_j, b_j, p_j, and m_j, describing the range, cooling power, and operating cost of the j-th air conditioner.

Note: Stalls are numbered from 1 to 100.

outputFormat

Output a single integer representing the minimum cost needed to satisfy the cooling requirement for every cow.

sample

2 2
1 50 10
51 100 5
1 100 10 100
1 100 5 50

100