题目描述

炎炎夏日，酷热难耐，农夫约翰计划打开牛棚中的空调给奶牛降温。

约翰的牛棚中一共有 $N$ 头奶牛，编号 $1∼N$。

牛棚中有 $100$ 个牛栏排成一排，编号依次为 $1∼100$。

每头奶牛都占据着连续若干个牛栏，同一个牛栏最多被一头奶牛占据。

第 $i$ 头奶牛占据的牛栏范围是 $[s_i,t_i]$。

不同奶牛的降温需求不同，第 $i$ 头奶牛的降温需求为 $c_i$，这意味着它占据的每个牛栏都至少需要降温 $c_i$。

牛棚中一共有 $M$ 台空调，编号 $1∼M$。

第 $i$ 台空调的运行成本为 $m_i$，开启这台空调可以让 $[a_i,b_i]$ 范围内的每个牛栏降温 $p_i$。

不同空调的覆盖范围可能重叠，降温效果也可以叠加。

约翰希望在让所有奶牛的降温需求都得到满足的前提下，花费的总成本尽可能小。

输出所需总成本的最小可能值。

输入格式

第一行包含 $N,M$。

接下来 $N$ 行，每行包含三个整数 $s_i,t_i,c_i$。

接下来$M$ 行，每行包含四个整数 $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≤N≤20,$
$1≤M≤10,$
$1≤s_i≤t_i≤100,$
$1≤c_i≤10^6,$
$1≤a_i≤b_i≤100,$
$1≤p_i≤10^6,$
$1≤m_i≤1000$

样例解释

一种满足条件的最佳方案为运行第 1,3,4 个空调，所需成本为 3+2+5=10。