#P3265. 志愿者招募加强版
志愿者招募加强版
志愿者招募加强版
题目描述
APIO 比赛持续 天。第 天至少需要 名志愿者。XHL 可以招募 类志愿者,每类可招募的人数不限。
每一类志愿者都有一份工作日程,由若干个连续的日期区间组成。若招募一名这类志愿者,她会在该类给出的日期区间内工作。每个区间包括起止的两天。同一名志愿者在同一天计为一人。
招募一名第 类志愿者需要支付 点魅力值。请安排每天都有足够的志愿者,并使总开销最小。
输入格式
第一行包含两个整数 ,分别表示比赛天数和志愿者的种类数。
第二行包含 个非负整数 。
接下来 行,第 行描述一类志愿者。行首的整数 表示这类志愿者可工作的区间数。随后是 对整数 ,其中 ,表示每段的起止日期。行末的整数 表示招募一个人的开销。
输出格式
输出一个整数,表示最小总开销。
样例
3 3
2 3 4
1 1 2 2
1 2 3 5
1 3 3 2
14
数据规模与约定
,,其余输入数据合法且小于 。
保证存在满足每天人数要求的招募方案,且将每类招募人数放宽为非负实数后,所得线性规划存在一个所有招募人数均为整数的最优解。
保证存在满足每天人数要求的招募方案,且将每类招募人数放宽为非负实数后,所得线性规划存在一个所有招募人数均为整数的最优解。
保证存在满足每天人数要求的招募方案,且将每类招募人数放宽为非负实数后,所得线性规划存在一个所有招募人数均为整数的最优解。
保证存在满足每天人数要求的招募方案,且将每类招募人数放宽为非负实数后,所得线性规划存在一个所有招募人数均为整数的最优解。
保证存在满足每天人数要求的招募方案,且将每类招募人数放宽为非负实数后,所得线性规划存在一个所有招募人数均为整数的最优解。
保证存在满足每天人数要求的招募方案,且将每类招募人数放宽为非负实数后,所得线性规划存在一个所有招募人数均为整数的最优解。
保证存在满足每天人数要求的招募方案,且将每类招募人数放宽为非负实数后,所得线性规划存在一个所有招募人数均为整数的最优解。