Echoing Tunnels

# Echoing Tunnels ## Problem Bessie has discovered a network of underground tunnels connecting `N` grazing pastures. Each pasture contains an "echo chamber" that produces a certain amount of milk when visited. The pastures are connected by one-way tunnels, forming a directed graph with `M` edges. The echo value in each pasture can propagate through cycles—if you traverse a cycle of tunnels and return, the echo amplifies. However, no matter how many times you traverse the cycle, you only collect the milk **once** when you're in that cycle system. Bessie wants to find the maximum amount of milk she can collect by traveling through some path of tunnels. She starts at some pasture and can travel as long as she wants, collecting milk from each pasture she visits. She only collects milk from each **strongly connected component** of pastures once. ## Input The first line contains two integers `N` and `M` (1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000). The next line contains `N` integers `V_1, V_2, ..., V_N`, where `V_i` (1 ≤ V_i ≤ 10^6) is the milk value of pasture `i`. The next `M` lines each contain two integers `u` and `v` (1 ≤ u, v ≤ N, u ≠ v), representing a tunnel from pasture `u` to pasture `v`. ## Output Print a single integer: the maximum total milk Bessie can collect from any valid path. ## Constraints - 1 ≤ N ≤ 5000 - 0 ≤ M ≤ 10000 - 1 ≤ V_i ≤ 10^6 - The graph is a DAG after contracting strongly connected components ## Sample Input ``` 5 5 2 3 5 7 11 1 2 2 1 2 3 3 4 4 5 ``` ## Sample Output ``` 28 ``` ## Explanation The graph has pastures 1, 2, 3, 4, 5 with milk values 2, 3, 5, 7, 11 respectively. Pastures 1 and 2 form a cycle (1→2→1), so they are in the same strongly connected component with total value 2 + 3 = 5. Pastures 3, 4, 5 are each in their own SCC with values 5, 7, 11 respectively. After contracting the SCCs, the graph becomes a DAG: SCC{1,2} → SCC{3} → SCC{4} → SCC{5}. The optimal path visits all four SCCs in order, collecting 5 + 5 + 7 + 11 = **28** milk.