小强的Linux

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在Linux操作系统中,软件包的安装是有依赖关系的,假设你要安装A软件包,如果A软件包依赖于B软件包,那么你必须先安装B软件包,否则安装A软件包时会出现异常情况,当然也存在一些软件包不依赖于其他软件包便可安装。小强最近要入门Linux系统,于是要安装许多软件包,每个软件包需要花费一定的安装时间,所以这成为一件头疼的事儿。

小强有N个软件要安装分别以一个整数表示1,2,3...N。正如上面所说,这些软件是存在依赖关系的,现在给出这N个软件包的依赖关系(保证不会出现相互依赖的非法情况,即不会出现A依赖于B,B依赖于C,C又依赖于A。),N个软件包的安装时间,你的任务就是帮助小强算出安装这些软件包至少需要多长时间。

Sample的关系图如下:
\"\"

Input

 

第一行:一个整数N表示有N个软件包需要安装(1 ≤ N ≤ 1000),接下来的一行有N个整数,第i个整数ti表示i软件包的安装时间(1 ≤ ti ≤ 1000)。

第三行:一个整数M(M ≤ 499,500)表示这N个软件包有M对依赖关系,接下来M行每行分别为两个整数r1 r2表示r1软件包需要在r2软件包安装完成后才可以安装(1 <= r1, r2 <= N)。

Output

 

一个整数t表示至少需要t时间才可以完成所有软件包的安装。

Sample Input

3
2 3 1
2
1 2
1 3

Sample Output

5

Hint

 

系统支持同时安装多个软件包。

Source