#P2488. [SDOI2011] 工作安排
[SDOI2011] 工作安排
题目描述
你的公司接到了一批订单。订单要求你的公司提供 类产品,产品被编号为 ,其中第 类产品共需要 件。公司共有 名员工,员工被编号为 员工能够制造的产品种类有所区别。一件产品必须完整地由一名员工制造,不可以由某名员工制造一部分配件后,再转交给另外一名员工继续进行制造。
我们用一个由 和 组成的 的矩阵 来描述每名员工能够制造哪些产品。矩阵的行和列分别被编号为 和 , 为 表示员工 能够制造产品 ,为 表示员工 不能制造产品 。
如果公司分配了过多工作给一名员工,这名员工会变得不高兴。我们用愤怒值来描述某名员工的心情状态。愤怒值越高,表示这名员工心情越不爽,愤怒值越低,表示这名员工心情越愉快。员工的愤怒值与他被安排制造的产品数量存在某函数关系,鉴于员工们的承受能力不同,不同员工之间的函数关系也是有所区别的。
对于员工 ,他的愤怒值与产品数量之间的函数是一个 段的分段函数。当他制造第 件产品时,每件产品会使他的愤怒值增加 ,当他制造第 件产品时,每件产品会使他的愤怒值增加 ……为描述方便,设 ,那么当他制造第 件产品时,每件产品会使他的愤怒值增加 ,。
你的任务是制定出一个产品的分配方案,使得订单条件被满足,并且所有员工的愤怒值之和最小。由于我们并不想使用Special Judge,也为了使选手有更多的时间研究其他两道题目,你只需要输出最小的愤怒值之和就可以了。
输入格式
https://cdn.luogu.com.cn/upload/pic/1608.png
第一行包含两个正整数 和 ,分别表示员工数量和产品的种类数;
第二行包含 个正整数,第 个正整数为 ;
以下 行每行 个整数描述矩阵 ;
下面 个部分,第 部分描述员工 的愤怒值与产品数量的函数关系。每一部分由三行组成:第一行为一个非负整数 ,第二行包含 个正整数,其中第 个正整数为 ,如果 那么输入将不会留空行(即这一部分只由两行组成)。第三行包含 个正整数,其中第 个正整数为 。
输出格式
仅输出一个整数,表示最小的愤怒值之和。
2 3
2 2 2
1 1 0
0 0 1
1
2
1 10
1
2
1 6
24
提示
数据范围及约定
- 存在 的数据,保证 ;
- 均匀分布着约 的数据,满足 ;
- 均匀分布着约 的数据,满足 (不包含上述 的数据)。
对于全部数据,满足 ,,,,。所有数据均不大于 。