题目描述

$N(1\leq N \leq 20)$ 位小朋友在游乐场玩，游乐场活动空间编号为 $1-100$. 第 $i$ 位小朋友活动空间为 $[s_i,t_i]$，小朋友活动空间不会相互交叉。夏天到了， 每位小朋友都要求自己所在的活动空间降温，第 $i$ 个小朋友要求自己的所有活动空间必须至少减低 $c_i$ 单位。

现在仓库里有 $M$ 台空调，标记 $1-M（1 \leq M \leq 10）$，第 $i$ 台空调需要 $m_i（1\leq m_i \leq 1000）$ 单位的经费来运行，如果运行，这台空调将把 $[a_i,b_i]$ 所有的活动空间温度降低 $p_i(1\leq p_i \leq 10^6)$。空调覆盖的活动空间范围可能会重叠。

请帮助管理员计算如何选择空调，满足所有小朋友降温需求的情况下需要花的最少金钱。

输入格式

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

接下来 $N$ 行，每行三个整数，分别为 $s_i,t_i,c_i$

接下来 $M$ 行，每行 $4$ 个整数，分别为 $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解释

可以选择第 $1,3,4$台空调，冷却区间是 $[2,9]、[1,2]、[6,9]$，成本为 $3+2+5=10$

数据规模与约定

$1 \leq N \leq 20,1 \leq M \leq 10$

$1\leq a_i,b_i,s_i,t_i \leq 100,1\leq c_i,p_i\leq10^6,1\leq m_i \leq 1000 $