Given a directed weakly connected graph with $n$ vertices and $m$ edges, each vertex $i$ has a weight $d_i$ and a modification cost $w_i$. Each modification operation costs $w_i$ and allows you to increase or decrease $d_i$ by $1$. Find the minimum total cost required such that for all $(u, v) \in E$, $d_u \le d_v$.

Input

The input consists of $m+3$ lines.

The first line contains two integers $n$ and $m$, representing the number of vertices and edges.

The second line contains $n$ integers, where the $i$-th integer represents the weight $d_i$ of the $i$-th vertex.

The third line contains $n$ integers, where the $i$-th integer represents the modification cost $w_i$ of the $i$-th vertex.

The next $m$ lines (from line 4 to $m+3$) each contain two integers $u_i, v_i$, representing a directed edge from $u_i$ to $v_i$ in the graph.

Output

Output a single integer representing the minimum total cost.

Examples

Input 1

3 3
5 9 8
1 2 3
1 2
2 3
3 1

Output 1

5

Note 1

The constraints are $d_1 \le d_2$, $d_2 \le d_3$, and $d_3 \le d_1$, which implies $d_1 = d_2 = d_3$. The optimal strategy is to increase $d_1$ by $3$ to $8$ and decrease $d_2$ by $1$ to $8$. The minimum cost is $1 \times |5-8| + 2 \times |9-8| + 3 \times |8-8| = 5$.

Input 2

3 2
5 9 8
1 2 3
1 2
2 3

Output 2

2

Subtasks