USACO Air Conditioners（空调）

题目描述

炎热的夏天，Farmer John 需要给牛棚里的奶牛降温。

共有 $N$ 头奶牛（$1 \leq N \leq 20$），牛棚有编号为 $1 \ldots 100$ 的一排牛栏。第 $i$ 头奶牛占用从 $s_i$ 到 $t_i$ 的连续牛栏（不同奶牛的占用范围互不重叠）。每头奶牛有不同的降温需求：奶牛 $i$ 需要至少降低 $c_i$ 单位的温度，即牠占用的每个牛栏温度都要至少降低 $c_i$。

共有 $M$ 台空调（$1 \leq M \leq 10$），编号 $1 \ldots M$。第 $i$ 台空调运行费用为 $m_i$（$1 \leq m_i \leq 1000$），可以冷却从 $a_i$ 到 $b_i$ 的连续牛栏范围，运行后将该范围内所有牛栏的温度降低 $p_i$（$1 \leq p_i \leq 10^6$）。不同空调的冷却范围可能重叠。

Farmer John 预算紧张。请计算满足所有奶牛所需的最小费用。题目保证：若使用所有空调，所有奶牛都能降温成功。

输入格式

第一行包含 $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

样例解释

一种最小费用的方案是选择第 $1、3、4$ 台空调（分别覆盖区间 $[2,9]$、$[1,2]$、$[6,9]$），费用 $3 + 2 + 5 = 10$。

数据范围

• $1 \leq N \leq 20$
• $1 \leq M \leq 10$（除样例外，保证 $M = 10$）
• $1 \leq s_i, t_i, a_i, b_i \leq 100$
• $1 \leq c_i, p_i \leq 10^6$
• $1 \leq m_i \leq 1000$

提示

可以用状态压缩 DP 或暴力枚举空调子集求解。