Maximum Mines Collection

You are given a map containing (N\ (N \leq 20)) caves. Each cave (i) contains a certain number of mines. Additionally, there are directed paths connecting some of the caves. After the data about caves and their connections is provided, a person can start mining from any cave. From the starting cave, the person can proceed to mine along one of the outgoing paths. The mining process continues along the chosen single path until there is no outgoing connection from the current cave. Note that each cave can only be visited once.


Your task is to design a mining plan so that the person collects the maximum number of mines possible. Formally, if you denote the mining gain at cave (i) by (a_i) and the directed edge from cave (u) to cave (v) exists, you must find a simple path (no repeated vertices) that maximizes (\sum_{i \in path} a_i).

inputFormat

The first line contains an integer (N) representing the number of caves. The second line contains (N) integers, where the (i)-th integer represents the number of mines in cave (i). The third line contains an integer (M) indicating the number of directed connections. Each of the next (M) lines contains two integers (u) and (v), representing a directed edge from cave (u) to cave (v).

Note: Caves are numbered from 1 to (N).

outputFormat

Output a single integer which is the maximum number of mines that can be collected following the rules.

sample

3
1 2 3
2
1 2
2 3

6