题目描述

农夫约翰的农场迎来了有史以来最热的夏天，他需要一种方法来给奶牛降温。因此，他决定购买一些空调。

农夫约翰的$N$头奶牛（$1 \le N \le 20$）住在一个畜棚里，畜棚里有一排畜栏，编号为1-100。奶牛$i$占据了这些牛棚的范围，从牛棚$si$开始​ 以牛棚$ti$结束​. 不同奶牛所占据的牛棚范围都是相互分离的。奶牛有不同的冷却要求。奶牛$i$必须冷却$ci$​, 这意味着奶牛$i$占用的每个牛棚的温度必须至少降低$ci​$ 单位。

谷仓装有$M$台空调，标记$1-M$（$1 \le M \le 10$）。第$i$台空调的花费$mi$块钱（$1 \le mi \le 1000$），并冷却从牛棚$ai$开始到牛棚$bi$​. 如果运行，第$i$台空调将此范围内所有牛棚的温度降低$pi​$（$1 \le pi \le 106$ ) . 空调覆盖的牛棚范围可能会重叠。

经营农场不是一件容易的事，所以FJ的预算很紧。请确定他至少需要花多少钱才能满足所有奶牛的要求。这是保证，如果FJ使用他的所有空调，那么所有的奶牛都会感到舒适。

输入格式

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

接下来的$N$行描述奶牛。这些行的第二行包含$si​, ti ​, 和ci$​.

接下来的$M$行描述空调。这些行的第二行包含$ai​, bi, pi​$, 还有$mi​$.

输出格式

输出一个整数，说明FJ运行足够的空调以满足所有奶牛（满足上述条件）所需的最低金额。

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

提示

导致花费最少的一个可能的解决方案是选择那些冷却间隔[2,9],[1,2]和[6,9]的间隔，成本为3+2+5=10。