东方博宜3035

题目描述

工厂有 NN 个零件需要加工，零件编号为 1 \sim N1∼N，编号为 ii 的零件加工需要的时间为 T_iTi ​ 。

某零件加工时，需要使用其他的零件，因此需要等待其所依赖的零件加工完，该零件才能加工。

比如，XX 零件依赖 Y,ZY,Z 两个零件，YY 零件依赖 ZZ 零件，那么必须先生产 ZZ 零件，再产生 YY 零件，最后生产 XX 零件。

工厂有足够的加工师傅，只要某零件可以加工（其所依赖的零件已经加工完毕），会立刻有师傅来加工该零件，加工不同零件切换过程不消耗时间。

请编程计算出，所有的零件加工完，最短需要多长时间。

输入

第 11 行读入 N,MN,M，表示需要加工的零件数量和零件之间依赖关系的数量。

接下来 NN 行，依次读入每个零件加工所需要的时间。

接下来 MM 行，每行有 22 个整数 X_i,Y_iX i ​ ,Y i ​ ，表示编号为 Y_iY i ​ 的零件加工，需要依赖编号为 X_iX i ​ 的零件。

数据保证不会出现环形依赖关系。

输出

输出所有零件加工完毕的最少时间。