3007 - 清凉猪舍
在小猪佩奇的家中，夏天格外炎热，猪妈妈希望为她的孩子们提供更加凉爽的环境。于是，她决定在家中安装空调。
小猪佩奇的家里住着 N 头猪（1 ≤ N ≤ 20），他们居住在一个由一排编号为 1 \dots 100 的猪栏中。第 i 头猪占用一定范围的猪栏，起始编号为 s_i ，结束编号为t_i。不同猪占用的猪栏范围互不重叠。
每头猪需要的冷却量不同。第 i 头猪需要的冷却量为c_i，也就是它占用的所有猪栏都需要降温至少 c_i 个单位。
猪栏中安装了 M 个空调，编号为 1\dots M（1 ≤ M ≤ 10）。第 i 个空调需要花费 m_i 个单位的费用（1 ≤ m_i ≤ 10^3），并且它会对编号为 a_i 到 b_i 的猪栏进行降温，每个猪栏的降温量为 p_i 个单位（1 ≤ p_i ≤ 10^6）。空调所覆盖的猪栏范围可能会重叠。
家庭的经营并不容易，所以猪妈妈需要在紧张的预算内解决这个问题。请确定她需要花费的最少费用，以确保所有的猪都能感到舒适。
保证如果所有空调都运行，所有猪都能感到舒适。
第一行输入 N 和 M 。
接下来的 N 行描述每头猪，第 i 行包含 s_i，t_i 和 c_i 。
接下来的 M 行描述每个空调，第i行包含 a_i，b_i， p_i 和 m_i。
输出一个整数，表示猪妈妈需要花费的最少费用。
输入
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
输入
1 1 1 100 1 1 100 1 1
输出
1
【样例 1 解释】
选择 1 号、3 号、4 号空调，涵盖范围分别为 [2,9]、[1,2] 和 [6,9]，花费分别为 3、2 和 5 元，共计 10 元。
【样例 2 解释】
选择 1 号空调，花费 1 元。
【数据范围】
对于 100\% 的数据，1 \le N \le 20， 1 \le M \le 10, 1 \le a_i, b_i, s_i, t_i \le 100, 1 \le c_i, p_i \le 10^6， 1 \le m_i \le 1000。
东方博宜OJ
