3861. [USACO23 Jan Bronze] Air Cownditioning II

【题目描述】

炎炎夏日，酷热难耐，农夫约翰计划打开牛棚中的空调给奶牛降温。

约翰的牛棚中一共有 $N$ 头奶牛，编号 $1 \sim N$。

牛棚中有 $100$ 个牛栏排成一排，编号依次为 $1 \sim 100$。

每头奶牛都占据着连续若干个牛栏，同一个牛栏最多被一头奶牛占据。

第 $i$ 头奶牛占据的牛栏范围是 $[s_i,t_i]$。

不同奶牛的降温需求不同，第 $i$ 头奶牛的降温需求为 $c_i$，这意味着它占据的每个牛栏都至少需要降温 $c_i$。

牛棚中一共有 $M$ 台空调，编号 $1 \sim M$。

第 $i$ 台空调的运行成本为 $m_i$，开启这台空调可以让 $[a_i,b_i]$ 范围内的每个牛栏降温 $p_i$。

不同空调的覆盖范围可能重叠，降温效果也可以叠加。

约翰希望在让所有奶牛的降温需求都得到满足的前提下，花费的总成本尽可能小。

输出所需总成本的最小可能值。

【输入格式】

第一行包含 $N,M$。

接下来 $N$ 行，每行包含三个整数 $s_i,t_i,c_i$。

接下来 $M$ 行，每行包含四个整数 $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,3,4$ 个空调，冷却牛栏范围：$[2，9]、[1，2]$ 和 $[6，9]$，所需成本为 $3+2+5=10$。

【数据规模与约定】

对于 $100\%$ 的数据，$1≤N≤20,1≤M≤10,1≤s_i≤t_i≤100,1≤c_i≤10^6,$

$1≤a_i≤b_i≤100,1≤p_i≤10^6,1≤m_i≤1000$.