#3147. [小云雀]Boss大作战

[小云雀]Boss大作战

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

“云雀村”常年受到一群叫Huhe的Boss的侵扰。 小Z忍无可忍决定对Huhe的巢穴发起反攻。因此,小Z决定购买一些火炮。

N\red{N}只Huhe1<=N<=20)\red{(1 <= N <= 20)}住在一个排列成一排的巢穴里,编号为1...100\red{1...100},第i\red{i}只Huhe会占据一系列的连续的巢穴,从巢穴si\red{s_i}开始,到巢穴ti\red{t_i}结束。不同的Huhe占据的巢穴范围互不重叠。若第i\red{i}只Huhe的血量值为ci\red{c_i},则其所住巢穴的防御值也为ci\red{c_i},仅当该Huhe所居住的所有巢穴受到至少ci\red{c_i}点攻击时,才能把它彻底消灭。

商店里有M\red{M}台火炮,标有1...M(1<=M<=10)\red{1...M(1 <= M <= 10)}。第i\red{i}台火炮的购买成本为mi\red{m_i}单位的费用,可以攻击从巢穴ai\red{a_i}开始到巢穴bi\red{b_i}结束的一系列的巢穴,并使得这一范围内的巢穴受到pi\red{p_i}点攻击,(1<=pi<=106)\red{(1<=p_i<=10^6)}。火炮的攻击范围可能重叠。

由于“云雀村”的预算有限,小Z希望花最少的钱购买火炮,并且使得所有的Huhe的巢穴被摧毁。

输入格式

第一行输入N\red{N}M\red{M}

接下来的N\red{N}行描述Huhe。其中第i\red{i}行包含si\red{s_i},ti\red{t_i}​和ci\red{c_i}

接下来的M\red{M}行描述火炮。其中第i\red{i}行包含ai\red{a_i}bi\red{b_i}​、pi\red{p_i}mi\red{m_i}

输出格式

输出一个整数,表示小Z需要花费的最少金额来购买火炮,满足摧毁所有Huhe的巢穴。

样例

输入数据

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

提示

数据范围与提示

一种可能的最省钱的解决方案是选择攻击区间[2, 9]、[1,2]和[6,9],花费3 + 2 + 5 = 10。

第三届小云雀杯入门组比赛

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-6-1 11:00
结束于
2024-6-1 13:00
持续时间
2 小时
主持人
参赛人数
147