#535. Air Cownditioning II B

Air Cownditioning II B

题目描述

农夫约翰的 NN 头奶牛 (1N20)(1≤N≤20) 住在一个谷仓里,谷仓里有连续的牛栏,编号为 11001-100 。 奶牛 ii 占据了编号 [si,ti][s_i,t_i] 的牛栏。 不同奶牛占据的牛栏范围是互不相交的。 奶牛有不同的冷却要求,奶牛 ii 占用的每个牛栏的温度必须至少降低 cic_i 单位。

谷仓包含 MM 台空调,标记为 1M1-M (1M10)(1\le M\le10)。第 ii 台空调需要花费 mim_i 单位的金钱来运行 (1mi1000)(1\le m_i \le 1000) ,如果运行,第 ii 台空调将牛栏 [ai,bi][a_i,b_i] 所有牛栏的温度降低 pip_i1pi1061\le p_i\le10^6)。 空调覆盖的牛栏范围可能会重叠。

请帮助农夫约翰求出满足所有奶牛需求要花费的最少金钱。

输入格式

第一行两个整数,分别为 NNMM

22(N+1)(N+1) 行,每行三个整数,分别为 sis_itit_icic_i

(N+2)(N+2)(M+N+1)(M+N+1) 行,每行四个整数, 分别为 aia_ibib_ipip_imim_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

一种花费最少的可能解决方案是选择那些冷却区间为 [2,9][2,9][1,2][1,2][6,9][6,9] 的空调,成本为 3+2+5=10 3+2+5=10 .

数据范围

对于 100%100\% 的数据,1N201 \le N \le 201M101 \le M \le 10, 1ai,bi,si,ti100 1 \le a_i, b_i, s_i, t_i \le 100, 1ci,pi1061 \le c_i, p_i \le 10^61mi10001 \le m_i \le 1000