题目内容

调度器上有一组待调度的任务（job），大部分任务之间存在亲和关系，需要优先把具有亲和关系的任务调度到同一个核上面，不亲和的任务不能运行在同一个核上面。

给定一组待调度的任务（任务编号和任务执行时间），同时会给出任务之间不存在亲和关系的列表（未给出的默认是亲和关系）。请设计一个调度器，按照如下要求：

1. 找出一组包含亲和任务数量最多的亲和调度任务组；
2. 如果规则1有多个解，给出所有任务执行时间之和最小的，并输出该亲和调度任务组的所有任务执行时间之和。

亲和调度任务组定义：一组可以在同一核上面执行的亲和任务集合。

解答要求

时间限制：C/C++ 1000ms，其他语言2000ms
内存限制：C/C++ 256MB，其他语言512MB

输入描述

• 第一行：一个整数jobNum，表示任务数量，任务编号[1, jobNum]，取值范围[1, 30]
• 第二行：jobNum个整数，表示每个任务的执行时间
• 第三行：一个整数mutexNum，表示不存在亲和关系的列表个数
• 接下来mutexNum行：每一行表示1对不亲和的任务编号（任务编号范围[1, job Num]）

输出描述

• 一个整数，表示所有任务的最短执行时间。

样例1

输入

3
2 3 10
1
1 2

输出

12

解释
有3个待调度任务，任务1和任务2不亲和，不能在一个核上执行；

1. 亲和调度任务组有："任务1"、"任务2"、"任务3"、"任务1+任务3"、"任务2+任务3"；
2. 包含任务数量最多的亲和调度任务组合有两种："任务1+任务3"，或"任务2+任务3"；
3. 两个任务的执行时间分别为12和13，选择执行时间较小的"任务1+任务3"，输出12。

样例2

输入

1
1
0

输出

1

解释
只有一个任务，返回这个任务的执行时间。

样例3

输入

3
2 3 10
3
1 2
2 3
1 3

输出

2

解释
有3个待调度任务，任务1和任务2、任务2和任务3、任务1和任务3不亲和，不能在一个核上执行；

1. 亲和调度任务组有："任务1"、"任务2"、"任务3"；
2. 包含任务数量最多的亲和调度任务组合有3种："任务1"、"任务2"、"任务3"；
3. 3个场景的执行时间分别为2、3、10，选择执行时间较小的"任务1"，输出2。