Problem
全国有N个城市，其中一些有公路相连。在一条路上行驶需要一箱汽油。此外，您还有一个煤气罐，其容量与煤气罐的燃料量相同。
在每个城市，一箱汽油的成本不同。你需要从第一个城市到第 N 个城市，花尽可能少的钱。
在每个城市，您可以加满油箱，加满油箱和罐，或者将罐中的汽油倒入油箱。这可以让你在那些更便宜的城市买汽油省钱，但罐子只够加一箱！
输入
第一行包含数字N（1<=N<=100），下一行包含N个数字，其中第i个设置第i个城市的汽油成本（所有这些都是整数来自范围从 0 到 100 ）。然后是数字 M –该国的道路数量，然后是道路本身的描述。每条道路由两个数字给出——它连接的城市数量。所有的道路都是双向的（也就是说，它们既可以在一个方向上行驶，也可以在另一个方向上行驶），两个城市之间总是只有一条道路，没有从城市通往城市本身的道路。
输出
要求输出单个数字 –路线的总成本，如果不可能到达那里，则为 -1。
例子
<头>
<日>#
| 输入 |
输出 |
<正文>
| 1 |
4
1 10 2 15
4
1 2
1 3
4 2
4 3
|
2 |