6503: 牛栏空调
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
农夫约翰的 头奶牛 住在一个谷仓里,谷仓里有连续的牛栏,编号为 。 奶牛 占据了编号 的牛栏。 不同奶牛占据的牛栏范围是互不相交的。 奶牛有不同的冷却要求,奶牛 占用的每个牛栏的温度必须至少降低 单位。
谷仓包含 台空调,标记为 。第 台空调需要花费 单位的金钱来运行 ,如果运行,第 台空调将牛栏 所有牛栏的温度降低 (。 空调覆盖的牛栏范围可能会重叠。
请帮助农夫约翰求出满足所有奶牛需求要花费的最少金钱。
Input
第一行两个整数,分别为 和 。
第 至 行,每行三个整数,分别为 、 和 。
第 至 行,每行四个整数, 分别为 、、 和 。
Output
一个整数,表示最少花费的金钱。
Sample Input Copy
2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5
Sample Output Copy
10
HINT
样例解释
一种花费最少的可能解决方案是选择那些冷却区间为 、 和 的空调,成本为 。
数据范围
对于 的数据,, , , , 。
来源:USACO23JAN