暂无测试数据。

With the hottest recorded summer ever at Farmer John's farm, he needs a way to cool down his cows. Thus, he decides to invest in some air conditioners.

Farmer John's N cows (1≤N≤20) live in a barn that contains a sequence of stalls in a row, numbered 1…100. Cow i occupies a range of these stalls, starting from stall si and ending with stall ti. The ranges of stalls occupied by different cows are all disjoint from each-other. Cows have different cooling requirements. Cow i must be cooled by an amount ci, meaning every stall occupied by cow i must have its temperature reduced by at least ci units.

The barn contains M air conditioners, labeled 1…M (1≤M≤10). The ith air conditioner costs mi units of money to operate (1≤mi≤1000) and cools the range of stalls starting from stall ai and ending with stall bi. If running, the ith air conditioner reduces the temperature of all the stalls in this range by pi (1≤pi≤106). Ranges of stalls covered by air conditioners may potentially overlap.

Running a farm is no easy business, so FJ has a tight budget. Please determine the minimum amount of money he needs to spend to keep all of his cows comfortable. It is guaranteed that if FJ uses all of his conditioners, then all cows will be comfortable.

农夫约翰的农场迎来了有记录以来最热的夏天，他需要一种方法给他的奶牛降温。因此，他决定投资一些空调。

农民约翰的 $N$ 头奶牛 $(1\leq N\leq 20)$ 生活在一个谷仓里，谷仓里有一排一排的牛棚，编号为 $1\cdots 100$。奶牛 $i$ 占据了这些牛棚，从 $s_i$ 牛棚开始，到 $t_i$ 牛棚结束。不同奶牛所占据的牛棚范围都是互不相连的。奶牛有不同的温度要求。奶牛 $i$ 必须冷却一个 $c_i$ 的量，这意味着奶牛 $i$ 所占据的每个牛棚必须至少降低 $c_i$ 单位的温度。

仓内空调数量为 $M$ 台，编号为 $1\cdots M(1\leq M\leq 10)$。第 $i$ 台空调的运行成本为 $m_i$ 单位 $(1\leq m_i \leq 1000)$，为从 $a_i$ 牛棚到 $b_i$ 牛棚的范围内降温。如果运行，第 $i$ 空调将该范围内所有牛棚的温度降低 $p_i(1\leq p_i\leq 10^6)$。空调覆盖的牛棚范围可能会重叠。

经营农场不是一件容易的事，所以 FJ 的预算很紧张。请确定他最少要花多少钱才能让他所有的奶牛都舒服。可以保证，如果 FJ 使用了他所有的空调，那么所有的奶牛都会很舒服。

输入格式

The first line of input contains N and M.

The next N lines describe cows. The ith of these lines contains si, ti, and ci.

The next M lines describe air conditioners. The ith of these lines contains ai, bi, pi, and mi.

For every input other than the sample, you can assume that M=10.

第一行输入包含 $N$ 和 $M$。

接下来的N行描述奶牛。第 $i$ 行包含 $s_i$, $t_i$ 和 $c_i$。

接下来的 $M$ 行描述的是空调。第 $i$ 行包含 $a_i, b_i, p_i, m_i$。

对于样本以外的每个输入，可以假设 $M=10$。

输出格式

Output a single integer telling the minimum amount of money FJ needs to spend to operate enough air conditioners to satisfy all his cows (with the conditions listed above).

输出一个整数，告诉FJ运行足够多的空调以满足他所有奶牛的需求所需的最小金额(满足上面列出的条件)。

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

10