A91468.Welcome24ever 和奶牛

Welcome24ever 的 $N$ 头奶牛（$1\le N\le 20$）住在一个谷仓里，谷仓有连续的牛栏，编号 $1\sim 100$。奶牛 $i$ 占据牛栏区间 $[s_i,t_i]$，且不同奶牛的区间互不相交。奶牛 $i$ 占据的每个牛栏都要求温度至少降低 $c_i$ 单位。

谷仓里有 $M$ 台空调（$1\le M\le 10$）。若开启第 $i$ 台空调，需要花费 $m_i$ 金钱（$1\le m_i\le 1000$），它会使区间 $[a_i,b_i]$ 内每个牛栏的温度降低 $p_i$（$1\le p_i\le 10^6$）。空调区间可重叠、可覆盖多个奶牛区间。

请计算：为了满足所有奶牛在其各自区间内的降温要求，最少需要花费多少金钱。

• 第一行：两个整数 $N,M$。
• 接下来 $N$ 行：每行三个整数 $s_i,t_i,c_i$。
• 再接下来 $M$ 行：每行四个整数 $a_i,b_i,p_i,m_i$。

• 一行一个整数：满足所有需求的最小总花费。

样例解释

选择冷却区间为 $[2,9]$、$[1,2]$、$[6,9]$ 的三台空调，费用 $3+2+5=10$，可满足两段奶牛区间的降温需求。

数据范围

• $1\le N\le 20,\;1\le M\le 10$
• $1\le a_i,b_i,s_i,t_i\le 100$
• $1\le c_i,p_i\le 10^6,\;1\le m_i\le 1000$