Most Rewarding Paths

[pranavdv]

Description

You are given a directed graph G with N vertices and M edges. Each vertex has a positive reward associated with it that you can collect the first time you visit that vertex. What are the maximum total rewards you can collect if you are free to choose your starting vertex, can visit each vertex as many times as you want and can end at any reachable vertex?

Input

The first line contains N and M. The next line contains N positive space separated integers and ith integer is the reward at vertex i. The next M lines contain a pair of integers each, say a and b, such that there is a directed edge from vertex a to b.

Output

Print the maximum total rewards that can be collected

Constraints

• 1<=N<=1e5
• 1<=M<=2e5
• 1<=a, b<=n
• 1<= reward at a vertex <= 1e9

Example

Input 4 4 4 5 2 7 1 2 2 1 1 3 2 4

Output 16

Details

• Technical Specifications: C,C++,Python
• Type of issue: Single
• Time Limit: 24 hours after the issue is assigned

Directory Structure

Create a folder called rewardingPath under the Algorithms folder and add your code there. Name the file rewardingPath.cpp

Note

1. Please claim the issue first by commenting here before starting to work on it.
2. Once you are done with the task and have created a Pull Request, please tag @pranavdv to request a review.