#P3265. 志愿者招募加强版

志愿者招募加强版

志愿者招募加强版

题目描述

APIO 比赛持续 NN 天。第 ii 天至少需要 AiA_i 名志愿者。XHL 可以招募 MM 类志愿者,每类可招募的人数不限。

每一类志愿者都有一份工作日程,由若干个连续的日期区间组成。若招募一名这类志愿者,她会在该类给出的日期区间内工作。每个区间包括起止的两天。同一名志愿者在同一天计为一人。

招募一名第 ii 类志愿者需要支付 CiC_i 点魅力值。请安排每天都有足够的志愿者,并使总开销最小。

输入格式

第一行包含两个整数 N,MN,M,分别表示比赛天数和志愿者的种类数。

第二行包含 NN 个非负整数 A1,…,ANA_1,\ldots,A_N。

接下来 MM 行,第 ii 行描述一类志愿者。行首的整数 kk 表示这类志愿者可工作的区间数。随后是 kk 对整数 Sj,TjS_j,T_j,其中 1≤Sj≤Tj≤N1\le S_j\le T_j\le N,表示每段的起止日期。行末的整数 CiC_i 表示招募一个人的开销。

输出格式

输出一个整数,表示最小总开销。

样例

3 3
2 3 4
1 1 2 2
1 2 3 5
1 3 3 2
14

数据规模与约定

1≤N≤10001\le N\le1000,1≤M≤100001\le M\le10000,其余输入数据合法且小于 10910^9。

保证存在满足每天人数要求的招募方案,且将每类招募人数放宽为非负实数后,所得线性规划存在一个所有招募人数均为整数的最优解。

保证存在满足每天人数要求的招募方案,且将每类招募人数放宽为非负实数后,所得线性规划存在一个所有招募人数均为整数的最优解。

保证存在满足每天人数要求的招募方案,且将每类招募人数放宽为非负实数后,所得线性规划存在一个所有招募人数均为整数的最优解。

保证存在满足每天人数要求的招募方案,且将每类招募人数放宽为非负实数后,所得线性规划存在一个所有招募人数均为整数的最优解。

保证存在满足每天人数要求的招募方案,且将每类招募人数放宽为非负实数后,所得线性规划存在一个所有招募人数均为整数的最优解。

保证存在满足每天人数要求的招募方案,且将每类招募人数放宽为非负实数后,所得线性规划存在一个所有招募人数均为整数的最优解。

保证存在满足每天人数要求的招募方案,且将每类招募人数放宽为非负实数后,所得线性规划存在一个所有招募人数均为整数的最优解。

BZOJ 归档题面