2242: 空调降温

炎炎夏日，酷热难耐，农夫约翰计划打开牛棚中的空调给奶牛降温。约翰的牛棚中一共有 N头奶牛，编号 1∼N。

牛棚中有 100 个牛栏排成一排，编号依次为 1∼100。每头奶牛都占据着连续若干个牛栏，同一个牛栏最多被一头奶牛占据。第 i头奶牛占据的牛栏范围是 [si, ti]。

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

牛棚中一共有 M 台空调，编号 1∼M。第 i台空调的运行成本为 mi，开启这台空调可以让 [ai,bi] 范围内的每个牛栏降温 pi。不同空调的覆盖范围可能重叠，降温效果也可以叠加。

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

数据保证：至少存在一组方案满足所有奶牛的降温需求。

第一行包含 N,M。

接下来 N 行，每行包含三个整数 si,ti,ci。

接下来 M 行，每行包含四个整数 ai,bi,pi,mi。

一个整数，表示所需总成本的最小可能值。

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。

【数据范围】

1≤N≤20, 1≤M≤10, 1≤si≤ti≤100, 1≤ci≤10⁶
1≤ai≤bi≤100, 1≤pi≤10⁶, 1≤mi≤1000