Siruseri ATM Bank Robbery

In the city of Siruseri, every intersection is equipped with an ATM of the Siruseri Bank, and many intersections also host a bar. The city roads are all one-way, and intersections are connected by these one‐way roads.

Banditji plans to execute the most audacious ATM robbery in Siruseri’s history. He will depart from the city center at intersection 1, travel along one‐way roads, and rob every ATM he passes (each ATM can only be robbed once). His heist ends when he reaches an intersection with a bar, where he will celebrate his victory.

You are given the amount of cash available at each ATM and the road network. Compute the maximum total cash Banditji can rob if he starts at intersection 1 and ends at any intersection that has a bar. He is allowed to traverse any intersection or road multiple times; however, once an ATM is robbed, it will no longer yield any money.

Note : If an intersection is visited multiple times, the ATM is robbed only on the first visit.

Hint: Consider condensing the graph into strongly connected components.

The problem can be modeled as follows. You are given a directed graph with n intersections (nodes) labeled from 1 to n and m one-way roads (directed edges). Each intersection i has an ATM with A_i dollars, and a flag that indicates whether a bar is present (1 for bar, 0 for no bar). Starting at node 1, compute the maximum sum of dollars that can be collected along a path that ends at any node having a bar. The input guarantees that each ATM's money can be collected at most once.

The route may traverse cycles, but note that money from an ATM is only collected the first time that intersection is visited. If there is no valid path ending at a bar, the answer should be considered as 0.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2×10⁵), representing the number of intersections and roads respectively.

The second line contains n integers A₁, A₂, ..., A_n, where A_i is the amount of money at the ATM located at intersection i (0 ≤ A_i ≤ 10⁹).

The third line contains n integers, each is either 0 or 1. The i-th integer is 1 if there is a bar at intersection i, and 0 otherwise.

The following m lines each contain two integers u and v (1 ≤ u, v ≤ n), indicating there is a one-way road from intersection u to intersection v.

outputFormat

Output a single integer, the maximum amount of cash that can be robbed under the given conditions.

sample

6 7
5 10 8 7 17 6
0 0 0 0 1 0
1 2
2 4
4 1
2 3
3 5
2 6
6 5

47