空气调节 II
Description
农夫约翰的 N 头奶牛 (1≤N≤20) 住在一个谷仓里，谷仓里有连续的牛栏，编号为1-100 。 奶牛 i 占据了编号[si,ti] 的牛栏。 不同奶牛占据的牛栏范围是互不相交的。 奶牛有不同的冷却要求，奶牛 i 占用的每个牛栏的温度必须至少降低 ci 单位。
谷仓包含 M 台空调，标记为 1−M (1≤M≤10)。第 i 台空调需要花费 mi 单位的金钱来运行 (1≤mi≤1000) ，如果运行，第 i 台空调将牛栏 [ai,bi] 所有牛栏的温度降低 pi（1≤pi≤106）。 空调覆盖的牛栏范围可能会重叠。
请帮助农夫约翰求出满足所有奶牛需求要花费的最少金钱。
Input Format
第一行两个整数，分别为 N 和 M。
第2 至 (N+1) 行，每行三个整数，分别为 si、ti 和 ci 。
第 (N+2) 至 (M+N+1) 行，每行四个整数， 分别为 ai、bi、pi 和 mi。
样例解释 1
一种花费最少的可能解决方案是选择那些冷却区间为 [2,9] 、[1,2] 和 [6,9] 的空调，成本为 3+2+5=10 .
【数据范围】
对于 100% 的数据，1≤N≤20， 1≤M≤10, 1≤ai,bi,si,ti≤100, 1≤ci,pi≤106， 1≤mi≤1000。
</div>
</div>
</div>
Output Format
一个整数，表示最少花费的金钱。2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 510Hint
样例解释 1
一种花费最少的可能解决方案是选择那些冷却区间为 [2,9] 、[1,2] 和 [6,9] 的空调，成本为 3+2+5=10 .
【数据范围】
对于 100% 的数据，1≤N≤20， 1≤M≤10, 1≤ai,bi,si,ti≤100, 1≤ci,pi≤106， 1≤mi≤1000。
