题目描述

在Farmer John's农场里，经历了有史以来最热的夏天，他需要一种方法来给他的奶牛降温。因此，他决定投资一些空调。

Farmer John的N头奶牛（$1≤N≤20$）生活在一个包含一排连续牛栏的谷仓中，这些牛栏编号为1到100。奶牛$i$占据了这些牛栏中的一部分，范围从牛栏$s_i$开始到牛栏$t_i$结束。不同奶牛占据的牛栏范围是彼此不重叠的。奶牛有不同的降温需求。奶牛i需要降温的量为$c_i$，意味着每一个奶牛i占据的牛栏的温度都必须至少降低$c_i$个单位。

谷仓里有M台空调，编号为1到M（$1≤M≤10$）。第i台空调的运行成本为mi单位的金钱（$1≤m_i≤1000$），它能为从牛栏$a_i$到牛栏$b_i$的范围内的所有牛栏降温。如果开启，第i台空调会把这个范围内的所有牛栏的温度降低pi个单位（$1≤p_i≤10^6$）。空调覆盖的牛栏范围可能会重叠。

经营一个农场并非易事，因此FJ的预算很紧张。请确定他需要花费的最少金钱以确保所有奶牛都感到舒适（在满足上述条件的前提下）。可以保证，如果FJ使用了所有的空调，那么所有的奶牛都会感到舒适。

输入格式

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

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

再接下来的M行描述空调。第i行包含$a_i$，$b_i$，$p_i$和$m_i$。

对于除样例外的每一个输入，你可以假设$M=10$。

输出格式​

输出一个整数，表示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

​样例输出​：

10

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