题目描述

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

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

1、找出一组包含亲和任务数量最多的亲和调度任务组；

2、如果规则$1$有多个解，给出所有任务执行时间之和最小的。并输出该亲和调度任务组的所有任务执行时间之和。

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

输入描述

第一行是一个整数$n(1\le n\le 30)$，表示任务数量

第二行$n$个整数，表示每个任务的执行时间$t_1,t_2,...t_n(1\le t_i\le 1000)$

第三行是一个整数$m(1\le m\le \frac{n\times (n-1)}{2})$，表示不存在亲和关系的列表个数

接下来$m$行，每一行表示$1$对不亲和的任务编号$u,v(1\le u,v\le n)$

输出描述

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

样例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

样例解释

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