炎炎夏日，酷热难耐，农夫约翰计划打开牛棚中的空调给奶牛降温。
约翰的牛棚中一共有 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。
一个整数，表示所需总成本的最小可能值。
1 \le N \le 20,
1 \le M \le 10,
1 \le s_i \le t_i \le 100,
1 \le c_i \le 10^6,
1 \le a_i \le b_i \le 100,
1 \le p_i \le 10^6,
1 \le m_i \le 1000
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 个空调，所需成本为 3+2+5=10。
USACO 2023 January Contest Bronze