题目描述

“云雀村”常年受到一群叫Huhe的Boss的侵扰。 小Z忍无可忍决定对Huhe的巢穴发起反攻。因此，小Z决定购买一些火炮。

有$\red{N}$只Huhe$\red{（1 <= N <= 20)}$住在一个排列成一排的巢穴里，编号为$\red{1...100}$,第$\red{i}$只Huhe会占据一系列的连续的巢穴，从巢穴$\red{s_i}$开始，到巢穴$\red{t_i}$结束。不同的Huhe占据的巢穴范围互不重叠。若第$\red{i}$只Huhe的血量值为$\red{c_i}$,则其所住巢穴的防御值也为$\red{c_i}$，仅当该Huhe所居住的所有巢穴受到至少$\red{c_i}$点攻击时，才能把它彻底消灭。

商店里有$\red{M}$台火炮，标有$\red{1...M(1 <= M <= 10)}$。第$\red{i}$台火炮的购买成本为$\red{m_i}$单位的费用，可以攻击从巢穴$\red{a_i}$开始到巢穴$\red{b_i}$结束的一系列的巢穴，并使得这一范围内的巢穴受到$\red{p_i}$点攻击,$\red{(1<=p_i<=10^6)}$。火炮的攻击范围可能重叠。

由于“云雀村”的预算有限，小Z希望花最少的钱购买火炮，并且使得所有的Huhe的巢穴被摧毁。

输入格式

第一行输入$\red{N}$和$\red{M}$。

接下来的$\red{N}$行描述Huhe。其中第$\red{i}$行包含$\red{s_i}$,$\red{t_i}$​和$\red{c_i}$。

接下来的$\red{M}$行描述火炮。其中第$\red{i}$行包含$\red{a_i}$、$\red{b_i}$​、$\red{p_i}$和$\red{m_i}$

输出格式

输出一个整数，表示小Z需要花费的最少金额来购买火炮，满足摧毁所有Huhe的巢穴。

样例

输入数据

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

提示

数据范围与提示

一种可能的最省钱的解决方案是选择攻击区间[2, 9]、[1,2]和[6,9],花费3 + 2 + 5 = 10。