The power transmission network of City K can be viewed as a directed acyclic graph with $N$ nodes and $M$ edges. Each node with an in-degree of 0 represents an operating thermal power plant; the remaining nodes with in-degree greater than 0 represent facilities that require power, where the $i$-th facility has a peak power load of $a_i$ amperes. As the operator of City K's power grid, Spark company plans to temporarily convert some thermal power plants into solar power plants for networked trial operation.

Let $S_y$ be the set of nodes that maintain their original thermal power plant output during the trial period, and $S_z$ be the set of nodes that Spark temporarily converts into solar power plants. Spark company had previously determined a temporary conversion plan, but during equipment configuration, it was discovered that this plan might easily lead to large-scale failures. Specifically, during the trial period, there may be some facilities directly or indirectly connected to both $S_y$ and $S_z$, receiving power from two disparate types of power plants simultaneously, which significantly increases the risk of sudden events such as power coupling anomalies. However, due to a tight schedule, Spark company cannot design the plan from scratch or redeploy equipment.

To minimize the impact on the production and life of City K during the trial period, Spark company hopes to develop an emergency conversion plan based on the original plan that isolates the two power supply types as much as possible, such that the total risk to City K's power grid is minimized. In other words, Spark needs to minimize the sum of the peak loads $a_i$ of power-consuming facilities that are connected to both $S_y$ and $S_z$, plus the power generation loss (also represented by $a_i$) incurred when urgently converting some power plants to another power generation type. To better determine whether an emergency conversion plan is needed, Spark tentatively allows $S_y$ or $S_z$ to be empty after the conversion.

Input

The first line contains two positive integers $N$ and $M$, representing the number of nodes in City K's power network and the number of directly connected transmission lines. It is guaranteed that $2 \le N \le 5,000$ and $1 \le M \le \min\{50,000, N(N - 1)/2\}$.

The second line contains $N$ integers $d_1, \dots, d_N$, representing the type of each node: if $d_i = -1$, then node $i$ is a power-consuming facility; otherwise, node $i$ is a power plant, where $d_i = 0$ if and only if node $i$ remains a thermal power plant in the original conversion plan ($i \in S_y$), and $d_i = 1$ if and only if node $i$ is temporarily converted to a solar power plant in the original conversion plan ($i \in S_z$). It is guaranteed that $-1 \le d_i \le 1$, and there is at least one $d_i = 1$ in the input.

The third line contains $N$ positive integers $a_1, \dots, a_N$, representing the peak power load of each power-consuming facility node, or the power generation loss incurred when each power plant urgently converts its power generation type (in amperes). It is guaranteed that $1 \le a_i \le 40$.

The next $M$ lines each contain two positive integers $u_i, v_i$, representing a transmission line in the power grid directly transmitting power from $u_i$ to $v_i$. It is guaranteed that $1 \le u_i, v_i \le N$, the input does not contain multiple edges, and the input graph is a directed acyclic graph with at least two nodes having an in-degree of 0.

Output

Output a non-negative integer representing the total risk of the optimal emergency conversion plan (in amperes).

Examples

Input 1

6 6
0 1 0 1 -1 -1
11 17 1 13 2 28
1 5
2 5
3 5
2 6
3 6
4 6

Output 1

3

Input 2

6 7
0 1 0 -1 -1 -1
11 17 1 13 2 28
1 4
2 4
2 5
2 6
3 5
4 6
5 6

Output 2

12