题意

班级花园里有 $N$ 种不同的花，它们被种植在编号从 $1$ 到 $\max t_i$ 的一段连续的花坛上。
第 $i$ 种花占据了编号为 $[s_i,t_i]$ 的花坛区间。不同花占据的花坛区间互不相交。
每种花有不同的肥料需求，第 $i$ 种花占据的每个花坛上至少需要施加 $c_i$ 单位的肥料。

花园管理员准备了编号为 $1-M$ 的 $M$ 种不同的肥料包。 第 $i$ 种肥料包购买需要花费 $m_i$ 元，如果购买并使用，该肥料包可以在花坛区间 $[a_i,b_i]$ 的每个花坛上施加 $p_i$ 单位的肥料 $(1\le p_i\le10^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$。

输出格式

一个整数，表示满足所有肥料需求的最少花费。

样例

输入 #1

2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5

输出 #1

10

样例解释 1

一种花费最少的解决方案是购买以下三种肥料包：

• 覆盖区间 $[2,9]$ 的肥料包，花费 $3$ 元
• 覆盖区间 $[1,2]$ 的肥料包，花费 $2$ 元
• 覆盖区间 $[6,9]$ 的肥料包，花费 $5$ 元

总花费为 $3+2+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$

本题所有测试点捆绑测试。你只有通过所有测试点才能得分。