A6266. 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$）。空调区间可重叠、可覆盖多个奶牛区间。
请计算：为了满足**所有**奶牛在其各自区间内的降温要求，最少需要花费多少金钱。
谷仓里有 $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$。
- 接下来 $N$ 行：每行三个整数 $s_i,t_i,c_i$。
- 再接下来 $M$ 行：每行四个整数 $a_i,b_i,p_i,m_i$。
输出格式
- 一行一个整数：满足所有需求的**最小总花费**。
输入输出样例
输入 #1
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$，可满足两段奶牛区间的降温需求。
## 数据范围
- $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$
选择冷却区间为 $[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$