题目描述

电网系统已经非常普遍的应用于生活，现在有一种新型的电网需要投入使用，希望你 能帮助它，是它获得最大的电力。

我们有以下的约定：

$\red{1.}$所有的城市都需要有电网覆盖，但电网可以不连通。

$\red{2.}$一个城市最多只有一个发电站。

$\red{3.}$两个城市之间最多有一条输电线路

$\red{4.}$电网中可能存在环，但是环只可能是三元环。

$\red{5.}$为了确保安全，相邻两个城市只能有一个发电。

$\red{6.}$考虑到环保的需要，每个城市的发电站都有自己的饱和发电量。你的任务就是要计算出这个电网能够获得的最大电量。

输入格式

第一行一个整数 $\red{n（}$$\red{1<=n<=100）}$表示城市的数量。

第二行为 $\red{n }$个整数，分别表示 $\red{1-n }$号城市的发电饱和量。都不超过 $\red{10000 }$

第三行为一个整数 $\red{m，}$表示输电线路的总数。

第 $\red{4 }$行到第 $\red{3+m }$行，每行两个整数

输出格式

一个整数，表示这个电网所能获得的最大电量。

样例

输入样例

2
1 2
1
1 2

输出样例

2