P7071: 空调II
传统题
1.000s
时间限制
256MB
内存限制
2 提交
1 解决
【题目描述】
【题目描述】
农夫约翰的农场正在经历有史以来最热的夏天，他需要一种方法来给奶牛降温。因此，他决定安装一些空调。
农夫约翰的N头牛（1≤N≤20）住在一个牛棚里，牛棚里有一排牛
栏，编号为1…100。奶牛i占据了一系列这些位置，从位置
si开始到ti，不同奶牛占据的牛
栏范围都是彼此不相交的。奶牛有不同的冷却要求。奶牛i必须冷却一定量的ci，这意味着奶牛i占用的每个位置
的温度必须至少降低ci单位。
谷仓里有M台空调，标有1…M（1≤M≤10）。第i台空调的运行成本为mi单位（1≤mi≤1000），可冷却从ai档开始到bi档结束的档位范围。如果运行，第i台空调将此范围内所有档位的温度降低pi（1≤pi≤10^6）。空调覆盖的位置范围可能会重叠。
经营农场不是一件容易的事，所以农夫约翰的预算很紧。请确定他至少
需要花多少钱才能让所有奶牛都舒服。这是保证，如果FJ使用他的所有空调，那么所有的奶牛都会感到舒适。
【输入格式】
（输入来自终端/stdin）：
第一行输入包含N和M。
接下来的N行描述奶牛。第i行包含si、ti和ci。
接下来的M行描述空调。第i行包含ai、bi、pi和mi。
对于样本以外的每个输入，可以假设M=10。
【输出格式】
（输出格式）（将输出打印到终端/标准输出）：
输出一个整数，说明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
导致花费最少的一个可能的解决方案是选择那些冷却时间间隔的方法[2，9]，[1,2]和[6,9]，成本为3+2+5=10。