Destroying the Graph

Alice and Bob play the following game. First, Alice draws a directed graph with $N$ vertices and $M$ arcs. Then Bob tries to destroy it by removing every arc. In one move Bob picks any vertex and removes either all arcs coming into that vertex or all arcs going out of that vertex.

Alice assigns two costs to each vertex $i$: $W_i^{+}$ and $W_i^{-}$. If Bob removes all arcs incoming into vertex $i$ he pays Alice $W_i^{+}$ dollars, and if he removes all arcs outgoing from vertex $i$ he pays $W_i^{-}$ dollars. Determine the minimum total amount Bob must pay to remove all arcs from the graph.

The first line contains two integers $N$ and $M$ ($1 \le N \le 100$, $1 \le M \le 5000$). The second line contains $N$ integers $W_1^{+}, \dots, W_N^{+}$. The third line contains $W_1^{-}, \dots, W_N^{-}$ in the same way. All costs are positive integers not exceeding $10^6$. Each of the following $M$ lines contains two integers $a$ and $b$, describing an arc from vertex $a$ to vertex $b$. The graph may contain loops and parallel arcs.

Print a single integer $W$ — the minimum total amount Bob must pay to remove all arcs from the graph.