Polygon Running Track

A polygon with n vertices (maximum 20) is given. The vertices are labeled with English uppercase letters in order. The polygon has n sides, and the length of each side is provided in order. In addition, there are k internal roads (or chords) connecting two (not necessarily non-adjacent) vertices inside the polygon.

All roads (both polygon edges and internal roads) are bidirectional. However, if there are multiple direct roads connecting the same two vertices, the runner (ChangShen Niu) will always choose the longest one. For example, if there are two direct roads between A and B with lengths 3 and 7, the distance between A and B is considered as 7. Note that if a road connects a vertex to itself, then the distance from that vertex to itself is the length of that loop (and is not 0).

Given the starting and ending vertices, calculate the minimum total distance to run from the start to the end, using the available roads with the rule described above. It is guaranteed that a path exists. Note that the input may have the same vertex as both start and end, and duplicate roads might appear.

Input and Output: See below.

inputFormat

The input consists of several parts:

1. An integer n representing the number of vertices (and sides) of the polygon. The vertices are labeled sequentially from 'A'.
2. A line with n integers, representing the lengths of the polygon's sides in order. The i-th number corresponds to the side between vertex chr(65 + i - 1) and chr(65 + i mod n). (For example, for n=5, the sides are A-B, B-C, C-D, D-E, and E-A.)
3. An integer k representing the number of internal roads inside the polygon.
4. k lines follow, each containing two uppercase letters (the endpoints) and an integer (the length of that road).
5. A line containing two uppercase letters, representing the starting and ending vertices.

outputFormat

Output a single integer: the length of the shortest path from the starting vertex to the ending vertex, considering that if two vertices are connected by multiple roads, the effective distance is the longest of the direct connections.

sample

5
2 3 4 5 6
3
A C 10
A D 3
B E 7
A D

3