#J3026. 时间管理大师

时间管理大师

题目描述

小紫最近突然抽风,想学习lzx成为下一代时间管理大师。于是,他为自己准备了一道难题来提高自己的时间管理能力:现在小紫的身边有m名工具人和n项作业,已知每项作业有m道题目,且每道题目都需由不同的工具人完成。每项作业的每道题目都有指定的耗时。
我们称每项作业的每道题目为一个操作,我们用i-j表示一个操作,其中i是1到n的某个数字,是作业编号;j是1到m的某个数字,是题目编号,如1-3表示第1项作业第3道题目的这个操作。在本题中,出题人给定了对于各操作的一个安排顺序。
例如,当n=3, m=2时,1-1,1-2,2-1,3-1,3-2,2-2就是一个给定的安排顺序,即先安排第一项作业的第一道题目,再安排第一项作业的第二个题目,然后再安排第二项作业的第一道题目,等等。
一方面,安排每一个操作都需要满足如下两个约束条件:
1. 对于同一项作业,每道题必须在它前面的那道题完成后才能开始写。
2. 同一时刻每个工具人最多只能写一项作业。
另一方面,在安排后面的操作时,不能改动前面已安排的操作。
由于同一项作业都是按题目顺序安排的,因此,只按原顺序给出作业编号,仍可得到同样的安排顺序,于是,在输入数据中,我们将这个安排顺序简写为"112332"。
还要注意,“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各工具人的实际写作业顺序。在具体实施时,有可能排在后面的某个操作比前面的某个操作先完成。
例如,取n=3, m=2, 已知数据如下(工具人编号/耗时): 

作业编号
题目1
题目2
1 1/3 2/2
2
1/2 2/5
3 2/2 1/4
则对于安排顺序"112332",下图中两个实施方案都是正确的。但总耗时分别是10和12. 


当一个操作插入到某个工具人的某个空档时(工具人最后尚未安排的部分也可以看做一个空档),可以靠前插入,也可以居中或靠后插入。简单起见,我们约定:在保证前述的两个约束条件的条件下,尽量靠前插入。并且,我们约定如果有多个空档可以插入,就在保证前述约束条件的条件下,插入最前的空档。于是,在这些约定下,上述例子中的方案1是正确的,方案2不正确。
显然,在这些约定下,对于给定的安排顺序,符合该安排顺序的实施方案是唯一的。请你计算出该方案完成所有作业的总耗时。 

输入格式

第1行是两个正整数m和n,数字之间使用空格隔开。 
第2行是m*n个正整数,是给定的安排顺序,数字之间使用空格隔开。 
接下来的2n行,每行有m个正整数ai,数字之间均用空格隔开。 
其中前n行依次表示每项作业的每道题由哪个工具人写。如第1行第1个数是负责写第1项作业第1道题的工具人编号,第1行第2个数是负责写第1项作业第2道题的工具人编号,第2行第1个数是负责写第2项作业第1道题的工具人编号,等等。 
后n行依次表示每项作业每道题的耗时。例如,从后n行的第1行开始,第1行的第1个数表示第1项作业第1道题的耗时,第1行的第2个数表示第1项作业第2道题的耗时,等等。 

输出格式

1个正整数,表示最小的总耗时。
2 3
1 1 2 3 3 2
1 2
1 2
2 1
3 2
2 5
2 4
10

提示

0 < m, n < 20,其中m表示工具人数量,n表示作业数量
0 < ai ≤ 20