问题 D：清凉猪舍未启用
题目描述
在小猪佩奇的家中，夏天格外炎热，猪妈妈希望为她的孩子们提供更加凉爽的环境。于是，她决定在家中安装空调。
小猪佩奇的家里住着 N 头猪（1 ≤ N ≤ 20），他们居住在一个由一排编号为 1 . . . 100 的猪栏中。第 i 头猪占用一定范围的猪栏，起始编号为 s_i ，结束编号为t_i。不同猪占用的猪栏范围互不重叠。
每头猪需要的冷却量不同。第 i 头猪需要的冷却量为c_i，也就是它占用的所有猪栏都需要降温至少 c_i 个单位。
猪栏中安装了 M 个空调，编号为 1 . . . 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 <= N <= 20， 1 <= M <= 10, 1 <= a_i, b_i, s_i, t_i <= 100, 1 <= c_i, p_i <= 10^6， 1 <= m_i <= 1000。