空调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\leq N\leq 20,1\leq M\leq 10,$ $1\leq s_{i}\leq t_{i}\leq 100,$ $1\leq c_{i}\leq 10^{6},$ $1\leq a_{i}\leq b_{i}\leq 100,$ $1\leq p_{i}\leq 10^{6},1\leq m_{i}\leq 1000$

样例解释

一种满足条件的最佳方案为运行第 $1,3,4$ 个空调，所需成本为 $3+2+5=10$。

来源

童程童美