2595: 搜索算法练习之 - USACO2023Jan - BronzeP2-AirCownditioning
[Creator : ]
Description
农夫约翰的农场迎来了有记录以来最热的夏天，他需要一种方法来给奶牛降温。因此，他决定投资买一些空调。
农夫约翰的N头奶牛（1≤N≤20)住在一个谷仓里，谷仓里有一排排摊位，编号为1…100 奶牛i 占据了一系列这样的摊位，从摊位si开始到ti结束
不同奶牛占据的摊位范围都是相互不连接的。奶牛有不同的冷却要求。奶牛i必须冷却一定量ci，也就是说每一个被奶牛占据的摊位必须使其温度至少降低ci单位。
谷仓里有M架空调，标记为1…M（1≤M≤10). 第i台空调价格mi货币单位（1≤mi≤1000) 并从ai开始冷却至bi结束。
如果运行这些空调，空调将这个范围内所有摊位的温度降低pi（1≤pi≤1000000). 注意：空调覆盖的摊位范围可能会重叠。
经营农场不是一件容易的事，所以FJ的预算很紧。请确定他需要花多少钱才能让所有的奶牛都舒服。可以保证的是，如果FJ使用了他所有的空调，那么所有的奶牛都会感到舒适。
农夫约翰的N头奶牛（1≤N≤20)住在一个谷仓里，谷仓里有一排排摊位，编号为1…100 奶牛i 占据了一系列这样的摊位，从摊位si开始到ti结束
不同奶牛占据的摊位范围都是相互不连接的。奶牛有不同的冷却要求。奶牛i必须冷却一定量ci，也就是说每一个被奶牛占据的摊位必须使其温度至少降低ci单位。
谷仓里有M架空调，标记为1…M（1≤M≤10). 第i台空调价格mi货币单位（1≤mi≤1000) 并从ai开始冷却至bi结束。
如果运行这些空调，空调将这个范围内所有摊位的温度降低pi（1≤pi≤1000000). 注意：空调覆盖的摊位范围可能会重叠。
经营农场不是一件容易的事，所以FJ的预算很紧。请确定他需要花多少钱才能让所有的奶牛都舒服。可以保证的是，如果FJ使用了他所有的空调，那么所有的奶牛都会感到舒适。
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