题目描述

强哥 的牧场遇到了有史以来最炎热的夏季，他需要一种方法来给奶牛们降温。因此，他决定采购一些空调。

强哥 的谷仓里有一排牛棚，编号为 $1 \dots 100$ ，其中住着 $N$ 头奶牛（ $1 \le N \le 20$ ）。奶牛 $i$ 占据了从牛棚 $s_i$ 到牛棚 $t_i$ 的所有牛棚，不同奶牛占据的牛棚区间是互不相交的。每头奶牛都有不同的降温需求，奶牛 $i$ 需要降温 $c_i$ 个单位，意味着奶牛 $i$ 所占据的每个牛棚都必须降温至少 $c_i$ 个单位。

谷仓里有 $M$ 台空调，编号为 $1 \dots M$ （ $1 ≤ M ≤ 10$ ）。使用第 $i$ 台空调的费用为 $m_i$ 个单位（ $1 ≤ m_i ≤ 1000$ ），并且会对牛棚 $a_i$ 到 牛棚 $b_i$ 范围内的牛棚进行降温。如果使用第 $i$ 台空调，它会将范围内所有牛棚的温度都减少 $p_i$ 个单位（ $1 ≤ p_i ≤ 10^6$ ）。空调所覆盖的牛棚范围可能会有重叠。

经营牧场是件不容易的事，所以 强哥 的预算很紧张。请计算出他为了让所有奶牛都满意所需要花费的最少费用。保证如果 强哥 使用全部空调，所有奶牛都会满意。

输入格式

输入的第一行包含整数 $N$ 和 $M$ 。

接下来 $N$ 行描述奶牛，其中第 $i$ 行包含 $s_i$ 、 $t_i$ 和 $c_i$ 。

接下来 $M$ 行描述空调，其中第 $i$ 行包含 $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

提示

样例解释

一个可能的花费费用最少的方案是，选择包含了牛棚区间 $[2, 9]$ 、 $[1, 2]$ 和 $[6, 9]$ 的三台空调，总费用为 $3 + 2 + 5 = 10$ 。

数据范围

样例之外的每个输入都可以假定 $M = 10$ 。