题目描述

农夫约翰的 $N$ 头奶牛 $(1\le N\le 20)$ 住在一个谷仓里，谷仓里有连续的牛栏，编号为 $1-100$ 。 奶牛 $i$ 占据了编号 $[s_{i},t_{i}]$ 的牛栏。 不同奶牛占据的牛栏范围是互不相交的。 奶牛有不同的冷却要求，奶牛 $i$ 占用的每个牛栏的温度必须至少降低 $c_{i}$ 单位。

谷仓包含 $M$ 台空调，标记为 $1-M$ $(1\le M\le 10)$。第 $i$ 台空调需要花费 $m_{i}$ 单位的金钱来运行 $(1\le m_{i}\le 1000)$ ，如果运行，第 $i$ 台空调将牛栏 $[a_{i},b_{i}]$ 所有牛栏的温度降低 $p_{i}$（$1\le p_{i}\le 10^{6}$）。 空调覆盖的牛栏范围可能会重叠。

请帮助农夫约翰求出满足所有奶牛需求要花费的最少金钱。

输入格式

第一行两个整数，分别为 $N$ 和 $M$。

第 $2$ 至 $(N+1)$ 行，每行三个整数，分别为 $s_{i}$、$t_{i}$ 和 $c_{i}$ 。

第 $(N+2)$ 至 $(M+N+1)$ 行，每行四个整数， 分别为 $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

提示

对于 $100$ 的数据，$1\le N\le 20$， $1\le M\le 10$, $1\le a_{i},b_{i},s_{i},t_{i}\le 100$, $1\le c_{i},p_{i}\le 10^{6}$， $1\le m_{i}\le 1000$。

【样例解释#1】

一种花费最少的可能方案是选择冷却区间为 $[2,9]$、$[1,2]$ 和 $[6,9]$ 的空调，成本为 $3+2+5=10$。

2 2
1 1 14
3 3 16
4 4 10 664
1 4 16 299

299

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

3 3
1 1 37
3 3 37
5 5 17
6 6 24 566
1 4 19 509
1 6 37 865

865