← 返回题单
题单练习 深度优先搜索
← 上一题 下一题 →

A6266 | Welcome24ever 和奶牛

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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$。

输出格式

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

输入输出样例

输入 #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
C++ 编辑器
输入
输出